Bentley–Ottmann algorithm: Difference between revisions

Revision as of 18:20, 5 March 2018

Revision as of 18:22, 5 March 2018

Line 36:

#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 their crossing forms a potential future event in the event queue, remove it. 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 were (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.