从线段中搜寻提取闭合轮廓（二）
接上篇文章从线段中搜寻闭合轮廓_多线段搜索区域集合 快速-CSDN博客
1. 前言
调试了上篇文章中参考代码修了一些问题，优化了显示，但是由于算法逻辑存在一些问题，有很多不必要的性能损耗，且逻辑不是最优的，于是博主找时间重新实现了下该算法，新算法的健壮性和性能均较好，将一些点记录如下。
2. 步骤
- 前处理：在提取轮廓前进行线段归并，剔除重合冗余部分，当然需要设定处理容差；
- 进行线段切割，从交点位置进行分割，将线段集处理为基本线段单元集合，基本线段单元的定义为不与其他线段重合、穿越相交；
- 构建半边集合，即每条线段（Edge）分为2个半边（halfEdge），具体原因参考上篇文章；
- 收集节点和线段关系，建立点和线段列表的映射；
- 进行节点归并：在容差范围内的节点，如果之间没有线相连，那就进行归并；
- 搜索提取闭合轮廓：依据极值夹角进行路径搜索（详见下文内容），提取闭合轮廓；
- 后处理：对轮廓进行归并：只保留最小单元轮廓（逆时针），其他轮廓（最大外轮廓以及其他的“冗余的”顺时针轮廓）筛除；
3. 路径搜索时的优先逻辑
因为这里我们求的是最小单元轮廓（逆时针），在搜索下一条路径时按与当前线（currentHalfEdge）夹角在[PI,0]、(2*PI, PI)优先顺序所搜下一条边（nextHalfEdge）。
最后提取到的轮廓就是所有的最小单元轮廓（逆时针）+ 最大外包围轮廓（顺时针），如果只想保留最小单元轮廓，可以按照上述后处理步骤将顺时针轮廓去掉即可。
欢迎交流：公众号：geometrylib
原文地址：https://blog.csdn.net/baidu_38621657/article/details/140854751
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！