Line Segment Intersection Testing - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Computing Année : 2005

Line Segment Intersection Testing

Résumé

Amethod for accurately determining whether two given line segments intersect is presented. This method uses the standard floating-point arithmetic that conforms to IEEE 754 standard. If three or four ending points of the two given line segments are on a same vertical or horizontal line, the intersection testing result is obtained directly. Otherwise, the ending points and their connections are mapped onto a 3 × 3 grid, and the intersection testing falls into one of the five testing classes. The intersection testing method is based on our method for floating-point dot product summation, whose error bound is 1ulp. Our method does not have the limitation in the method of Gavrilova and Rokne (2000) that the product of two floating-point numbers is calculated by a twice higher precision floating-point arithmetic than that of the multipliers. Furthermore, this method requires less than one-fifth of the running time used by the method of Gavrilova and Rokne (2000), and our new method for calculating the sign of a sum of n floating-point numbers requires less than one-fifteenth of the running time used by ESSA.
Fichier principal
Vignette du fichier
YongKangZhu2005a.pdf (384.85 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00517614 , version 1 (15-09-2010)

Identifiants

  • HAL Id : inria-00517614 , version 1

Citer

Yong-Kang Zhu, Jun-Hai Yong, Guo-Qin Zheng. Line Segment Intersection Testing. Computing, 2005. ⟨inria-00517614⟩
77 Consultations
1181 Téléchargements

Partager

Gmail Facebook X LinkedIn More