Finding if Path2D self-intersects?

Question

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?

Answer 1

While those "intersects" methods in the Path2D class look promising, I'm sure you've discovered that they actually refer to the area bounded by the lines in the path, not the lines themselves. We'll have to do it ourselves.

While your N^2 method works great, there IS in fact a more efficient way to discover if any of these lines intersect. It's not built into Java, but you can get N*LOG(N) performance by using a Sweep Line Algorithm.

Here's the gist: By sorting our line endpoints by x value, we can effectively "sweep" a virtual vertical line across all of our points from left to right. When we encounter a new line, we only need to check if it intersects with the line segments that hit our vertical line. How do we know WHICH points hit our vertical line? Well, once we sort our endpoints, we can iterate across them. If we're hitting the left point of a line, we add it to a list of "active" lines. When we hit the right point of a line, we remove it.

But we can be even faster! When we see a new left line segment, we don't have to actually check intersection with ALL active lines - just the active ones with y coordinate immediately above and below the new left segment. I won't prove that claim here, but you can convince yourself of this by drawing our some lines and walking through the algorithm.

This adds the additional complexity that we also need some structure with our lines sorted by y coordinate to be able to efficiently find those neighbor segments. We also need to be able to efficiently add and remove from this structure as we iterate through our endpoints. A good candidate is a Self Balancing Binary Search Tree. Java happens to have one handy - it's implemented as a Red-Black tree and it's called TreeMap. As for the list sorted by X coordinates, a simple ArrayList will do.

To summarize, we add each endpoint (marked with whether it's a left or right point) to an ArrayList and sort it. We create a TreeMap sorted by y coordinate that's empty at first. We then iterate across our points. For a "left" segment, we add the new line to our "active" tree and check for intersection with the segments immediately above and below our new line segment (by consulting the y coordinates from our "active" tree). We return if we find an intersection. Otherwise, continue. If we see a "right" endpoint, we remove that line from our "active" tree and continue.

For more, check out these slides from an MIT course with some visuals and bullet points:

http://courses.csail.mit.edu/6.006/spring11/lectures/lec24.pdf