Content deleted Content added
Split a section into two smaller subsections |
|||
Line 48:
{{harvtxt|Chen|Chan|2003}} described a highly space-efficient version of the Bentley–Ottmann algorithm that encodes most of its information in the ordering of the segments in an array representing the input, requiring only <math>\mathcal{O}(\log^2 n)</math> additional memory cells. However, in order to access the encoded information, the algorithm is slowed by a logarithmic factor.
== Special position
The algorithm description above assumes that line segments are not vertical, that line segment endpoints do not lie on other line segments, that crossings are formed by only two line segments, and that no two event points have the same ''x''-coordinate. In other words, it doesn't take into account corner cases, i.e. it assumes [[general position]] of the endpoints of the input segments. However, these general position assumptions are not reasonable for most applications of line segment intersection. {{harvtxt|Bentley|Ottmann|1979}} suggested perturbing the input slightly to avoid these kinds of numerical coincidences, but did not describe in detail how to perform these perturbations. {{harvtxt|de Berg|van Kreveld|Overmars|Schwarzkopf|2000}} describe in more detail the following measures for handling special-position inputs:
*Break ties between event points with the same ''x''-coordinate by using the ''y''-coordinate. Events with different ''y''-coordinates are handled as before. This modification handles both the problem of multiple event points with the same ''x''-coordinate, and the problem of vertical line segments: the left endpoint of a vertical segment is defined to be the one with the lower ''y''-coordinate, and the steps needed to process such a segment are essentially the same as those needed to process a non-vertical segment with a very high slope.
*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>
== Numerical precision issues ==
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.
| |||