Content deleted Content added
removed promotional material: LEDA |
|||
Line 50:
*Define a line segment to be a [[closed set]], containing its endpoints. Therefore, two line segments that share an endpoint, or a line segment that contains an endpoint of another segment, both count as an intersection of two line segments.
*When multiple line segments intersect at the same point, create and process a single event point for that intersection. The updates to the binary search tree caused by this event may involve removing any line segments for which this is the right endpoint, inserting new line segments for which this is the left endpoint, and reversing the order of the remaining line segments containing this event point. The output from the version of the algorithm described by {{harvtxt|de Berg|van Kreveld|Overmars|Schwarzkopf|2000}} consists of the set of intersection points of line segments, labeled by the segments they belong to, rather than the set of pairs of line segments that intersect.
A similar approach to degeneracies was used in the [[Library of Efficient Data types and Algorithms|LEDA]] implementation of the Bentley–Ottmann algorithm.<ref name="LEDA">{{harvtxt|Bartuschka|Mehlhorn|Náher|1997}}.</ref>
For the correctness of the algorithm, it is necessary to determine without approximation the above-below relations between a line segment endpoint and other line segments, and to correctly prioritize different event points. For this reason it is standard to use integer coordinates for the endpoints of the input line segments, and to represent the [[rational number]] coordinates of the intersection points of two segments exactly, using [[arbitrary-precision arithmetic]]. However, it may be possible to speed up the calculations and comparisons of these coordinates by using [[floating point]] calculations and testing whether the values calculated in this way are sufficiently far from zero that they may be used without any possibility of error.<ref name="LEDA"/> The exact arithmetic calculations required by a naïve implementation of the Bentley–Ottmann algorithm may require five times as many bits of precision as the input coordinates, but {{harvtxt|Boissonat|Preparata|2000}} describe modifications to the algorithm that reduce the needed amount of precision to twice the number of bits as the input coordinates.
==Faster algorithms==
| |||