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

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

本文介绍了算法找到折线之间的交叉点的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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

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.

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

08-20 01:19