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

Question

Bentley-Ottmann 算法适用于查找直线集的交点。但是我有很多折线:

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

我正在弄清楚，但与此同时，如果有人可以提供一些指示或想法，那将很有帮助。谢谢阅读。顺便说一下，我使用的是 WPF/C#，所有折线都是 PathGeometry。

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

Answer 1

扫描线算法有一个很好的理论，但很难稳健地实现。您需要处理垂直线段，并且可能会出现两条以上的线段在一个点上相交(甚至共享一条公共(public)线段)的情况。

我会使用 R-Tree 存储折线线段的边界框，然后使用 R-Tree 查找可能相交的元素。只有这些需要进行交集测试。优点是您可以为每条折线使用单独的 R 树，从而避免检测自相交(如果需要)。

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