Content deleted Content added
No edit summary |
|||
Line 12:
In such a case, ''L'' will always intersect the input line segments in a set of points whose vertical ordering changes only at a finite set of discrete ''events''. Thus, the continuous motion of ''L'' can be broken down into a finite sequence of steps, and simulated by an algorithm that runs in a finite amount of time.
There are two types of events that may happen during the course of this simulation. When ''L'' sweeps across an endpoint of a line segment ''s'', the intersection of ''L'' with ''s'' is added to or removed from the vertically ordered set of intersection points. These events are easy to predict, as the endpoints are known already from the input to the algorithm. The remaining events occur when ''L'' sweeps across a crossing between (or intersection of) two line segments ''s'' and ''t''. These events may also be predicted from the fact that, just prior to the event, the points of intersection of ''L'' with ''s'' and ''t'' are adjacent in the vertical ordering of the intersection points.
The Bentley–Ottmann algorithm itself maintains data structures representing the current vertical ordering of the intersection points of the sweep line with the input line segments, and a collection of potential future events formed by adjacent pairs of intersection points. It processes each event in turn, updating its data structures to represent the new set of intersection points.
| |||