The sweep idea
Many geometry problems become simple if you imagine a vertical line moving across the plane from left to right. Events happen at specific coordinates: a segment starts, a segment ends, two segments might cross. Processing these events in order replaces a two dimensional problem with a sequence of one dimensional snapshots.
The active set in a balanced tree
At any moment the line touches a set of currently relevant items, the active set. Keep them in a balanced search tree ordered by their position along the sweep line. The tree gives fast insert, fast delete, and fast access to neighbors.
- When a segment begins, insert it and check it against its immediate neighbors.
- When a segment ends, remove it and let its former neighbors become adjacent, checking them.
- When two segments swap order at a crossing, update the tree and check the new neighbors.
Only neighboring items in the tree can interact next, which is why the tree's ordered neighbor access is the heart of the method.
What it buys
Sorting the events once plus logarithmic tree operations per event yields an efficient solution to problems like detecting segment intersections or finding the closest pair, far better than comparing every pair.
Key idea
Sweep a line through sorted events while a balanced tree holds the active set in order, so only neighbors need checking.