算法找到折线之间的交叉点 [英] Algorithm to find intersections between polylines

问题描述

宾利奥特曼算法的工作寻找一套直线的交点。但我有很多的折线的：

Bentley-Ottmann algorithm works for finding intersections of set of straight lines. But I have lot of polylines:

有没有办法找到一套多段线的交叉点？

Is there a way to find intersections of the set of polylines?

我搞清楚，但在此同时，如果有人可以提供一些指针或想法，那将是有益的。感谢您的阅读。顺便说一句，我使用WPF / C＃和所有的多段线的PathGeometry。

I'm figuring out, but in the meanwhile, if someone can give some pointers or ideas, that would be helpful. Thanks for reading. By the way, I'm using WPF/C# and all the polylines are PathGeometry.

来源： HTTP ：//www.sitepen.com/blog/wp-content/uploads/2007/07/gfx-curve-1.png

推荐答案

在扫描线算法有一个很好的理论，但很难实现强劲。需要治疗垂直段，并且可能有情况下，两个以上的线段在一个单一的点相交（或者甚至共享一个共同的线段）。

The sweep line algorithm has a nice theory but is hard to implement robustly. You need to treat vertical segments, and there might be cases where more than two line segments intersect in a single point (or even share a common line segment).

我会使用R树存储多段线的线段包围盒，然后使用R-树找到可能相交的元素。只有这些需要的相交进行测试。它的优点是你可以用一个单独的R树的每个折线，从而避免检测selfintersections的，如果需要的话。

I'd use an R-Tree to store bounding boxes of the line segments of the polyline and then use the R-Tree to find possibly intersecting elements. Only these need to be tested for intersection. The advantage is that you can use a separate R-Tree for each polyline and thus avoid detection of selfintersections, if needed.

考虑使用CGAL的确切predicates内核以获得可靠的结果。

Consider using CGAL's exact predicates kernel to get reliable results.

这篇关于算法找到折线之间的交叉点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！