Bentley–Ottmann algorithm: Difference between revisions

Revision as of 09:24, 28 March 2014

Revision as of 12:00, 1 July 2014

Line 34:

#*If ''p'' is the left endpoint of a line segment ''s'', insert ''s'' into ''T''. Find the segments ''r'' and ''t'' that are immediately below and above ''s'' in ''T'' (if they exist) and 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'') 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 ''st'' and ''ts'' respectively. 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.

==Analysis==