找出Path2D是否自相交

Question

我需要找到Path2D是否与自身相交.现在,我通过简单地从路径中提取一行数据,然后查找是否有任何相交来实现.但它具有O(n ^ 2)复杂度,因此它非常慢.有更快的方法吗？

Answer 1

您可以使用扫描线算法更快地完成此操作：http://en.wikipedia.org/wiki/Sweep_line_algorithm

伪代码：

Each line has a start point and an end point. Say that `start_x` <= `end_x` for all the lines.
Create an empty bucket of lines.
Sort all the points by their x coordinates, and then iterate through the sorted list.
If the current point is a start point, test its line against all the lines in the bucket, and then add its line to the 
bucket.
if the current point is an end point, remove its line from the bucket.

最坏的情况仍然是O(N^2)，但平均的情况是O(NlogN)