查找多义线之间交点的算法

Question

Bentley-Ottmann算法适用于查找一组直线的交点。但我有很多的折线：

有没有办法找到一组折线的交叉点？

我在搞清楚，但同时，如果有人可以提供一些指引或想法，那将会有所帮助。谢谢阅读。顺便说一句，我使用的是WPF/C＃，所有的折线都是PathGeometry。

的图片来源：http://www.sitepen.com/blog/wp-content/uploads/2007/07/gfx-curve-1.png

Answer 1

的扫描线算法有一个很好的理论，但很难实现强劲。您需要处理垂直线段，并且可能会出现两个以上线段在单个点中相交（甚至共用一条公共线段）的情况。

我会使用R-Tree存储折线线段的边界框，然后使用R-Tree来查找可能相交的元素。只有这些需要交叉测试。优点是您可以为每条多段线使用单独的R-Tree，并因此避免检测到自相互关系（如果需要）。

考虑使用CGAL的确切谓词内核来获得可靠的结果。

Answer 2

添加到的Geom的建议（R树是要走的路），进一步的性能提升可以通过执行来获得如下：

简化折线 - 点的折线数可以减少，同时保持折线的一般形状。这可以通过使用角度阈值并处理每个点或使用the Ramer-Douglas-Peucker algorithm来完成。根据您正在做的事情，您可能需要跟踪原始多段线中的哪些点被用作简化多段线的每个段的起点/终点（原始多段线点的索引需要存储在某处）。

在this example中，您可以看到折线的点数可以如何减少。红色点表示未使用原始多段线的点，绿色点表示保留用于构建简化多段线的点。

2.将简化多段线存储在R树中，并确定每条多段线的每个段之间的交集（比较段的边界以减少计算对性能有利）。在完成之后，原始多段线段的旧索引将存储为与每个检测到的交叉点有关的信息，以及与哪些多段线相交（可使用某种标识符）。这基本上为您提供了原始多段线中各交点与其他多段线存在位置的每个线段的起点和终点。

3.只有交点位置必须与原多段线的交点的确切位置相匹配时才执行此步骤。您需要返回并使用原始的非简化折线，以及步骤2中获得的交点信息中的数据。每个交点应具有与其相关的开始和结束索引，并且这些索引可用于确定哪些特定需要处理原始多段线的段。这将允许您仅处理必要的细分（由与交叉点信息一起存储的开始和结束索引给出）。另一种方法是使用点本身并向外扩展边界框，然后处理与边界框相交的多边形折线段（尽管这可能需要更长的时间）。

4.由于简化过程可能会淘汰某些端点交点，因此可能需要采取额外步骤检查每条多段线的端点与其他多段线的段。 （这通常很快）。

该算法可以通过使用the Bentley-Ottmann algorithm（这是Geom所指的扫描线算法）进一步改进。还要注意，取决于所使用的简化算法和用于这些算法的参数（例如，角度公差），可能会在性能和精度之间进行权衡（根据多义线的简单程度，某些相交结果可能会丢失）。

显然，有些图书馆可能是可行的，但如果由于您所工作的公司或您正在开发的产品而受到许可条款的限制，第三方图书馆可能不是一种选择。此外，其他库可能无法满足需求。