Reliable line segment intersection testing

doi:10.1016/S0010-4485(00)00050-6

Return

Reliable line segment intersection testing

2000-10-01

PRE

Marina L. Gavrilova

Rokne, JG *

DOI：10.1016/S0010-4485(00)00050-6

Original

Original request for help

Save

Abstract

En 中文

The main result of this paper is a new algorithm that tests whether two line segments in the plane intersect. If the segments are defined using the coordinates of the endpoints in single-precision floating-point arithmetic, then the result of the test is exact. The equations of the segments are given in parametric form using the endpoint coordinates, and an equation whose solution would provide the coordinates of the intersection is developed. Interval arithmetic is then used to compute an inclusion of the coordinates of the intersection point. This inclusion is often sufficient to decide the intersection test. When it is not, a method for determining the exact sign of a sum is applied to the equations at an earlier stage of the solution process. Experimental results are presented that show that the number of intersections that cannot be resolved using interval tools is Fairly large in close to degenerate configurations of the segments and that the algorithm is significantly faster than an algorithm implemented using exact arithmetic. (C) 2000 Elsevier Science Ltd. All rights reserved.

Keywords:

intersection testing for line segments

floating-point arithmetic

exact computation

interval arithmetic

interval filter

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.