Content deleted Content added
Line 35:
#Initialize a [[self-balancing binary search tree]] ''T'' of the line segments that cross the sweep line ''L'', ordered by the ''y''-coordinates of the crossing points. Initially, ''T'' is empty. (Even though the line sweep ''L'' is not explicitly represented, it may be helpful to imagine it as a vertical line which, initially, is at the left of all input segments.)
#While ''Q'' is nonempty, find and remove the event from ''Q'' associated with a point ''p'' with minimum ''x''-coordinate. Determine what type of event this is and process it according to the following case analysis:
#*If ''p'' is the left endpoint of a line segment ''s'', insert ''s'' into ''T''. Find the segments ''r'' and ''t'' that are respectively immediately below and above ''s'' in ''T'' (if they exist)
#*If ''p'' is the right endpoint of a line segment ''s'', remove ''s'' from ''T''. Find the segments ''r'' and ''t'' that were (prior to the removal of ''s'') immediately above and below it in ''T'' (if they exist). If ''r'' and ''t'' cross, add that crossing point as a potential future event in the event queue.
#*If ''p'' is the crossing point of two segments ''s'' and ''t'' (with ''s'' below ''t'' to the left of the crossing), swap the positions of ''s'' and ''t'' in ''T''. Find the segments ''r'' and ''u'' (if they exist) that are immediately below and above ''t'' and ''s'' respectively (after the swap). Remove any crossing points ''rs'' and ''tu'' from the event queue, and, if ''r'' and ''t'' cross or ''s'' and ''u'' cross, add those crossing points to the event queue.
| |||