Content deleted Content added
m ISBNs (Build KH) |
|||
Line 40:
==Special position and numerical precision issues==
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. 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.
| |||