Avoiding all pairs
To report all intersections among many segments, comparing every pair is wasteful. The Bentley Ottmann sweep instead moves an imaginary vertical line across the plane and only considers segments that are vertically adjacent.
Events and status
The sweep processes events ordered by x coordinate, stored in a priority queue.
- A left endpoint inserts a segment into the active set.
- A right endpoint removes it.
- An intersection swaps the order of two segments.
The active segments are kept in a balanced structure ordered by their height at the current sweep position, called the status structure.
The key insight
Two segments can only cross if they become adjacent in the status order at some point. So after each insertion, deletion, or swap, you only test the newly neighboring pairs for future intersections and schedule any you find as new events.
Why it pays off
Because work is proportional to the segments plus the intersections actually reported, the sweep is dramatically faster than the all pairs approach when crossings are sparse.
Key idea
The sweep line orders events by x and keeps active segments sorted by height, testing only newly adjacent pairs, so the cost scales with segments plus reported intersections instead of all pairs.