Bentley–Ottmann algorithm: Difference between revisions

Revision as of 17:30, 5 March 2018

Revision as of 17:30, 5 March 2018

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'' 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). of this segment; theThe 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.