Sweep Line
Move a line across the plane, processing events in order and maintaining an active set.
Decision · step 2 of 4Plane Geometry: Sweep finds a crossing at the second event
x = 0: AB begins. It enters the active order by its height here, giving AB. It has no neighbour yet, so there is nothing to test.
What you will see
The line moves between event points; segments enter and leave the active set.
Cost
| Best | O(n log n) |
|---|---|
| Average | O((n + k) log n) |
| Worst | O((n + k) log n) |
| Space | O(n) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Points announce coordinates and role; each step announces the geometric test and its result in words (left turn, intersects).
Reduced motion: Shapes appear in place; the sweep line jumps between events.
Before this
Related
Taught by the same lesson
Plane Geometry covers these too, in the same run.