Algorithm to find intersections between polylines

Question

Bentley-Ottmann algorithm works for finding intersections of set of straight lines. But I have lot of polylines:

Is there a way to find intersections of the set of polylines?

I'm figuring out, but in the meanwhile, if someone can give some pointers or ideas, that would be helpful. Thanks for reading. By the way, I'm using WPF/C# and all the polylines are PathGeometry.

Source of the Image: http://www.sitepen.com/blog/wp-content/uploads/2007/07/gfx-curve-1.png

Answer 1

The sweep line algorithm has a nice theory but is hard to implement robustly. You need to treat vertical segments, and there might be cases where more than two line segments intersect in a single point (or even share a common line segment).

I'd use an R-Tree to store bounding boxes of the line segments of the polyline and then use the R-Tree to find possibly intersecting elements. Only these need to be tested for intersection. The advantage is that you can use a separate R-Tree for each polyline and thus avoid detection of selfintersections, if needed.

Consider using CGAL's exact predicates kernel to get reliable results.