Find the Intersection Points of All the Line Segments

Question

Given a list of line segments, the easiest way to find the intersection points is to loop through the line segment list, check whether they are intersecting and record the intersection point if they do.

But the runtime of this method is O(n^2), which is very inefficient. Is there any other algorithm that could speed up this process?

Answer 1

The Bentley-Ottmann Algorithm may be what you are looking for.