Plan Sweep Algorithm
- Status of l: the particular pair of segments intersecting l
- Event points: wherever changes are essential.
At an event point: update the particular status with the sweep line and execute intersection tests.
Upper: a new segment will be included with the particular status of l and it’s tested against the rest.
Lower: it’s deleted from the status associated with l
- Only testing pairs associated with segments for that there's a horizontal line intersects both segments.
- But, it might be inefficient, O(n2) for many instances. (ex) a set of segments all intersect along with x-axis.
To include the idea of being close in the horizontal direction, only test segments that are adjacent in the horizontal direction --
- Only test every along with ones to its left and right
- New ‘status’: ordered sequence associated with segments
- New ‘event points’: endpoints as well as intersects