Bentley–Ottmann algorithm: Difference between revisions

Revision as of 05:06, 11 December 2014

Revision as of 01:37, 8 October 2015

Line 21:

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 eventevents 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 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–Ottman 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.