wpf - 寻找折线之间交点的算法

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-Tree 是要走的路），可以通过执行以下操作来获得进一步的性能改进：

1.简化折线 - 可以减少折线中的点数，同时保持折线的大致形状。这可以使用角度阈值并处理每个点或使用Ramer-Douglas-Peucker 算法来完成。根据您正在执行的操作，您可能需要跟踪原始折线中的哪些点被用作简化折线的每一段的起点/终点（原始折线点的索引需要存储在某处）。

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

2.将简化的折线存储在R-Tree中，并确定每条折线的每个线段之间的交点（比较线段的边界以减少计算量有利于性能）。在执行此操作时，来自原始折线段的旧索引被存储为与每个检测到的交叉点相关的信息，以及与哪些折线相交的信息（可以使用某种标识符）。这实质上为您提供了原始多段线中每个段的开始和结束边界，其中交叉点与其他多段线存在。

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

4.可能需要采取额外的步骤来检查每条折线的端点与其他每条折线的线段，因为简化过程可能会剔除一些端点相交。（这通常很快）。

该算法可以通过使用Bentley-Ottmann 算法（这是 Geom 所指的扫描线算法）进一步改进。另请注意，根据使用的简化算法和用于此类算法的参数（例如角度公差），可能需要在性能和准确性之间进行权衡（根据折线的简单程度，可能会丢失一些相交结果）。

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