我有一张 CAD 绘图，我需要找到所有周长或边界边，以根据它们创建封闭的折线。 我使用了一些强力技术，但它们需要在编辑器（AutoCAD）中打开图形文件才能使用选择工具等，如果可以的话，我想通过使用 BSP 树、KD-Tree 之类的东西来避免这种情况， R-Tree 或类似的。我还想让它独立于任何特定的 CAD 系统。 KD 和 R 树似乎是迄今为止最有希望的。 我可以考虑任何特定的图形算法或其他树结构吗？
有 2 个警告，但没有显示塞子，一些边缘可能会交叉，如果它们构成最终周长的一部分，我需要选择并可能打破/分割这些边缘。由于转换软件的原因，端点处也存在一些间隙，但这些间隙可以通过给定的公差来处理。
基本上，我需要从绘图文件中获取所有线条（任何曲线都已分割成线条），创建“边缘”并将它们放入树/图中，然后处理/遍历它以找到边界边缘。 然后我可以使用生成的边缘来创建边界线条。
感谢您的任何建议。
完成此操作的基本方法是将线视为将平面划分为多个区域，在交叉点处分割边缘，以确保每条边缘正好界定两个区域（或者，在边缘具有裸露端点的情况下，界定一个区域）。我通常会使用类似于 Vatti 裁剪算法 的扫描线算法来完成此操作。 kD 树和 R 树等加速结构可以帮助加快速度（不是扫描线，而是其他剪切/分区算法），但它们不是最重要的部分。完成分区后，只需保留与无界区域接壤的那些边缘即可。
我不建议从头开始编码。 CGAL 应该有你需要的一切。