Bentley–Ottmann algorithm: Difference between revisions

Revision as of 14:35, 20 May 2018

Revision as of 14:41, 20 May 2018

Line 37:

#*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 above and below ''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''. FindAfter the swap, 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'' (i.e. the crossing points between ''r'' and ''s'' or between ''t'' and ''u'') from the event queue, and, if ''r'' and ''t'' cross or ''s'' and ''u'' cross, add those crossing points to the event queue.

==Analysis==