Line Segment Intersection Testing

Abstract : 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.
Type de document :
Article dans une revue
Computing, Springer Verlag, 2005
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger
Contributeur : Thss Tsinghua <>
Soumis le : mercredi 15 septembre 2010 - 09:01:50
Dernière modification le : mercredi 26 janvier 2011 - 02:02:16
Document(s) archivé(s) le : jeudi 1 décembre 2016 - 23:36:32


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00517614, version 1


Yong-Kang Zhu, Jun-Hai Yong, Guo-Qin Zheng. Line Segment Intersection Testing. Computing, Springer Verlag, 2005. 〈inria-00517614〉



Consultations de la notice


Téléchargements de fichiers