Content deleted Content added
m Dating maintenance tags: {{Clarify}} |
|||
Line 19:
In order to efficiently maintain the intersection points of the sweep line ''L'' with the input line segments and the sequence of future events, the Bentley–Ottmann algorithm maintains two [[data structure]]s:
*A [[binary search tree]], containing the set of input line segments that cross ''L'', ordered by the ''y''-coordinates of the points where these segments cross ''L''. The crossing points themselves are ''not'' represented explicitly in the binary search tree. The Bentley–Ottmann algorithm will insert a new segment ''s'' into this data structure when the sweep line ''L'' crosses the left endpoint ''p'' (i.e. the one with the smallest ''x''-coordinate) of this segment; the correct position of ''s'' in the binary search tree may be determined by a binary search, each step of which tests whether ''p'' is above or below some other segment that is crossed by ''L''. Thus, an insertion may be performed in logarithmic time. The Bentley–Ottmann algorithm will also delete segments from the binary search tree, and use the binary search tree to determine the segments that are immediately above or below other segments; these operations may be performed using only the tree structure itself without reference to the underlying geometry of the segments.
*A [[priority queue]] (the "event queue"), used to maintain a sequence of potential future events in the Bentley–Ottmann algorithm. Each event is associated with a point ''p'' in the plane, either a segment endpoint or a crossing point, and the event happens when line ''L'' sweeps over ''p''. Thus, the events may be prioritized by the ''x''-coordinates of the points associated with each event. In the Bentley–Ottmann algorithm, the potential future events consist of line segment endpoints that have not yet been swept over, and the points of intersection of pairs of lines containing pairs of segments that are immediately above or below each other.
| |||