提取平面点云轮廓
一. 基于凸包的凹点挖掘算法:
1. 提取点云的凸包
2. 计算凸包每条边的顶点的点密度(即该点 K 个临近点到该点的距离平均值)
3. 如果顶点点密度大于所在边的长度的 X 倍,则删除该边,并从内部点中选择出一个满足夹角最大的点,插入边界边,形成两条新的边界边
4. 迭代 2 和 3,一直到全部边界边的 X 倍小于其端点的点密度,算法结束
二. 基于 Delaunay 三角网的轮廓提取算法:
A. 不使用辅助点:
1. 首先对点云进行 Delaunay 三角构网
2. 同上,判断每条网格边长度的X倍和其端点的点密度之间的大小关系,并删除长的网格边
3. 提取只属于一个三角形的边界,作为边界边
4. 分类排序,得到有顺序关系的内外轮廓
B. 使用辅助点:
1. 手动在点云的边界附近选点
2. Delaunay构网
3. 判断每个三角形,如果其中一个点是辅助点,而另外两个点是点云中的点,则连接这两个点做为边界边
4. 分类排序,得到有顺序关系的内外轮廓
总体来说,由于构网算法的时间复杂度较高,因此可以有选择的使用上面两种算法,比如只有在确定要提取内轮廓的情况下,可以选择第二种轮廓提取算法