查找Path2D是否自相交 [英] Finding if Path2D self-intersects

问题描述

我需要找到Path2D是否相交。现在，我只需从路径中提取一系列行，然后查找是否存在任何这些行相交。但它具有O（n ^ 2）的复杂性，所以它非常慢。有没有更快的方法来做到这一点？

I need to find if Path2D intersects itself. For now, I do it by simply extracting an array of lines from path, and finding if any of these intersect. But it has O(n^2) complexity, and so it is very slow. Is there a faster way to do it?

推荐答案

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

You can do this faster using the sweep-line algorithm: http://en.wikipedia.org/wiki/Sweep_line_algorithm

伪代码：

Pseudocode:

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）

The worst case is still O(N^2), but the average case is O(NlogN)

这篇关于查找Path2D是否自相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！