寻求非CAD依赖的CAD图纸边界边提取技术方案

核心需求回顾 #

提取CAD图纸中所有线段（曲线已转为线段），将其转化为「边」存入树/图结构，通过遍历处理筛选出外围边界边，最终生成闭合多段线，且不依赖AutoCAD等特定CAD系统，替代传统的手动选择暴力方法。

除KD-Tree、R-Tree外的可选方案 #

• BSP树（二叉空间分割树）：擅长平面空间的递归分割，能快速圈定可能属于边界的边所在的空间范围，尤其适合存在复杂交叉边的场景，通过逐层分割缩小候选边集合，提升检索效率。
• 平面扫线算法：将所有线段端点按坐标轴排序后，沿固定方向（如x轴）扫过整个平面，可高效检测线段的邻接关系、交叉情况，同时能结合公差阈值处理端点间隙，非常适合批量处理线段的拓扑关系。
• 图论欧拉路径/回路思路：把每条线段看作无向边，端点视为节点。内部边的端点度数通常为2（被其他边连接），而边界边的端点度数多为1（仅单侧有边）。通过统计节点度数可以快速筛选出候选边界边，再结合空间结构验证闭合性。
• Voronoi图：如果面对的是密集无序的线段集合，Voronoi图可以计算每条线段的邻域空间，通过邻域的外围边界反向推导原始图纸的轮廓边，适合处理大规模线段的轮廓提取。

针对两个问题的处理思路 #

交叉边处理 #

1. 先用空间结构（KD-Tree、空间哈希网格）快速定位疑似交叉的边对，减少不必要的几何计算；
2. 验证交叉点后，若该交叉边属于边界，将交叉点作为新端点拆分线段，更新图结构中的节点与边，再重新纳入边界遍历流程。

端点间隙处理 #

1. 设定合理的公差阈值，在空间结构（比如空间哈希网格的单元格）中，将距离小于阈值的端点合并为同一个节点；
2. 合并后同步更新关联边的端点信息，确保后续图遍历的连通性不受间隙影响。

关于空间哈希网格的补充 #

你提到的空间哈希网格确实是当前场景的最优选择之一，它的优势很贴合需求：

• 按单元格划分空间，能快速把相邻边归入同一或邻近单元格，大幅缩减邻接边的检索范围，比纯树结构更高效；
• 支持多级网格嵌套，大网格处理全局范围的边筛选，小网格精准匹配短边的端点邻接，适配不同尺度的线段；
• 配合方向筛选（比如优先找与当前边方向相近的边），能加速闭合多段线的拼接过程，减少无效遍历。

内容的提问来源于stack exchange，提问作者Mick Duprez