Content deleted Content added
Line 33:
The Bentley–Ottmann algorithm performs the following steps.
#Initialize a priority queue ''Q'' of potential future events, each associated with a point in the plane and prioritized by the ''x''-coordinate of the point. So, initially, ''Q'' contains an event for each of the endpoints of the input segments.
#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 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.
| |||