Bentley–Ottmann algorithm: Difference between revisions

Revision as of 14:33, 20 May 2018

Revision as of 14:35, 20 May 2018

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 line-segments ''r'' and ''t'' that are respectively immediately belowabove and abovebelow ''s'' in ''T'' (if they exist); if the crossing of ''r'' and ''t'' (the neighbours of ''s'' in the status data structure) forms a potential future event in the event queue, remove this possible future event from the event queue. If ''s'' crosses ''r'' or ''t'', add those crossing points as potential future events in the event queue.

#*If ''p'' is the right endpoint of a line segment ''s'', remove ''s'' from ''T''. Find the segments ''r'' and ''t'' that (prior to the removal of ''s'') were respectively 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.