Avoiding all pairs
Reporting every intersection among many segments by testing all pairs is wasteful when intersections are few. The sweep line algorithm of Bentley and Ottmann imagines a vertical line moving left to right across the plane, processing events as it goes.
Events and the active set
The sweep maintains an ordered status structure of segments currently crossing the line, sorted by their height there. It processes three kinds of events stored in a priority queue:
- A left endpoint inserts a segment into the status and checks it against its new neighbors.
- A right endpoint removes a segment and checks the neighbors it leaves behind.
- An intersection swaps the order of the two crossing segments and checks the new neighbors.
The crucial insight is that two segments can only cross if they become adjacent in the height ordering at some moment, so neighbor checks suffice.
Why it pays off
Because only adjacent segments are compared, the work scales with the number of segments plus the number of intersections actually found, rather than all pairs. Each event does a small amount of ordered structure work. Handling overlapping endpoints and vertical segments carefully is the main implementation challenge, but the neighbor only principle is what makes the algorithm output sensitive.
Key idea
A sweep line keeps segments ordered by height and checks only adjacent pairs, so cost scales with segments plus intersections found.