RDP直线圆弧分割算法
参考资料：https://blog.csdn.net/x454045816/article/details/52703628
介绍
RDP（Ramer-Douglas-Peucker）算法用来对连续的边缘点集进行多边形逼近。因此也用来对边缘进行直线和圆弧的分割。
关于直线和圆弧分割算法，在halcon中有一个算子，segment_contours_xld，
关于直线和圆弧的连接算法，halcon中有两个算子，
union_cocircular_contours_xld，union_collinear_contours_xld
这两个算法的实现都依赖于RDP算法。因此本文对RDP算法的原理和代码实现进行介绍。
后续会有边缘分割和共线共圆边缘聚合的相关算法原理与实现的介绍，其实早就实现了，只是平时太忙了，这次趁着国庆假期做一些总结。
原理
首先，在轮廓的起点和终点之间建立一条线段，然后计算所有轮廓控制点到线段的距离，并从中选出距离最大的控制点。如果此距离比指定的阈值大，那么在对应最大距离控制点处将当前线段再次细分成两段。在新得到的线段上重复进行上述处理。如下图所示：
编码实现
计算轮廓上任意一点到轮廓首尾连线的垂直距离最大值及取最大值时点的索引。
const std::pair<int, double> findMaximumDistance(const vector<PointF>& Points)const
{
auto firstpoint = Points[0];
auto lastpoint = Points[Points.size() - 1];
int index = 0; //index to be returned
double Mdist = -1; //the Maximum distance to be returned
//distance calculation
PointF p = lastpoint - firstpoint;
for (int i = 1; i < Points.size() - 1; i++)
{
//traverse through second point to second last point
PointF pp = Points[i] - firstpoint;
//formula for point-to-line distance
double Dist = fabs(pp * p) / p.Norm();
if (Dist > Mdist)
{
Mdist = Dist;
index = i;
}
}
return std::make_pair(index, Mdist);
}
采用递归的方式，将一条边缘化简为一个多边形逼近的顶点。显然，如果边缘很直，则化简后点数量很少，反之，如果边缘弯曲位置很多，比如圆弧的情况，则化简后点数量较多。
vector<PointF> simplifyWithRDP(vector<PointF>& Points, double epsilon)const
{
if (Points.size() < 3)
{
//终止情况1，点数少于3个
return Points;
}
std::pair<int, double> maxDistance = findMaximumDistance(Points);
if (maxDistance.second >= epsilon)
{
int index = maxDistance.first;
auto it = Points.begin();
vector<PointF> path1(Points.begin(), it + index + 1);
vector<PointF> path2(it + index, Points.end());
auto r1 = simplifyWithRDP(path1, epsilon);
auto r2 = simplifyWithRDP(path2, epsilon);
//Concat simplified path1 and path2 together
vector<PointF> rs(r1);
rs.pop_back();
rs.insert(rs.end(), r2.begin(), r2.end());
return rs;
}
else
{
//终止条件2: 中间的所有点都可以被拿掉
vector<PointF> r(1, Points[0]);
r.push_back(Points[Points.size() - 1]);
return r;
}
}
这个算法当前没有一个可视的效果，后续在写亚像素找边，边缘分割，边缘聚合相关算法时会有一个总体的demo，用来展示效果。