Given a set of 2D polylines such that each polyline:
- May have self-intersections;
- May intersect some of (or all) the other polylines,
How do I efficiently find all pairs of intersecting segments and the coordinates of each corresponding intersection point? (We may assume that no three segments intersect in the same point.)
In other words: is it possible to find all intersections more efficiently than using algorithms designed for finding intersections in a set of segments? If it is possible, how? If it isn't, why not?
Each polyline is represented as a sequential list/array of points corrensponding to the endpoints of the segments (so if there are N points, there are N-1 segments in a polyline).
- Using the Bentley-Ottmann sweep line algorithm. The problem is that it takes a set of segments as its input, which means we have to first convert our polylines into a set of segments which seems to eliminate the potentially useful information about the connected endpoints and increases the number of input points. This seems to be a waste of computing resources if there is a way to use the input polyline points directly instead.
- Sweep line algorithms rely on sorting the input points by one of the coordinates. Knowing that each of the input polylines is already a sequential list of points, perhaps this could help at least partially to eliminate the need for sorting?