Java – find out if path2d is self intersecting

I need to find out if path2d intersects Now, I simply extract a row array from the path and find out if there are intersections in these rows But it has o (n ^ 2) complexity, so it is very slow Is there a faster way?

Solution

You can use the scanline algorithm: http://en.wikipedia.org/wiki/Sweep_line_algorithm Perform this operation faster

Pseudo code:

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.

The worst case is still o (n ^ 2), but the average case is O (nlogn)