Bentley–Ottmann algorithm: Difference between revisions

Revision as of 11:33, 20 May 2018

Revision as of 11:34, 20 May 2018

Line 10:

#No three line segments intersect at a single point.

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''. ASpecifically, a discrete event can either be associated with an endpoint (left or right) of a line-segment or intersection point of two line-segments. 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{{clarify|reason=It may not be easy to visualize this concept without a simple animation, unless you already know the algorithm.|date=March 2018}}.