Content deleted Content added
m →Data structures: Remove blank line(s) between list items per WP:LISTGAP to fix an accessibility issue for users of screen readers. Do WP:GENFIXES and cleanup if needed. Discuss this at... using AWB |
|||
Line 20:
*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–Ottman algorithm will insert a new segment ''s'' into this data structure when the sweep line ''L'' crosses the left endpoint ''p'' 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.
| |||