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(n²) 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