Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Thss Tsinghua Connect in order to contact the contributor
Submitted on : Wednesday, September 15, 2010 - 9:01:50 AM
Last modification on : Tuesday, June 1, 2021 - 2:34:07 PM
Long-term archiving on: : Thursday, December 1, 2016 - 11:36:32 PM


Files produced by the author(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⟩



Record views


Files downloads