Bentley–Ottmann algorithm: Difference between revisions

Revision as of 17:42, 5 March 2018

Revision as of 17:43, 5 March 2018

Line 24:

*A [[binary search tree]] (the "sweep line status 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'' of this segment (i.e. the endpoint of the segment with the smallest ''x''-coordinate, provided the sweep line ''L'' starts from the left, as explained above in this article). The correct position of segment ''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{{clarify|reason=What is an event, in the first place?}} 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.

The algorithm does not need to maintain explicitly a representation of the sweep line ''L'' or its position in the plane. Rather, the position of ''L'' is represented indirectly: it is the vertical line through the point associated with the most recently processed event.