Content deleted Content added
Line 32:
==Detailed algorithm==
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.
#Initialize a 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.
#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:
| |||