查找折线之间交叉点的算法

Question

Bentley-Ottmann算法用于寻找直线组的交点.但我有很多折线:

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

我正在搞清楚,但与此同时,如果有人可以给出一些指示或想法,那将会有所帮助.谢谢阅读.顺便说一下,我正在使用WPF/C#,所有折线都是PathGeometry.

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

Answer 1

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

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

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