https://hal.inria.fr/inria-00517614Zhu, Yong-KangYong-KangZhuTHSS - School of Software - THU - Tsinghua University [Beijing]Yong, Jun-HaiJun-HaiYongTHSS - School of Software - THU - Tsinghua University [Beijing]Zheng, Guo-QinGuo-QinZhengTHSS - School of Software - THU - Tsinghua University [Beijing]Line Segment Intersection TestingHAL CCSD2005[INFO.INFO-AO] Computer Science [cs]/Computer ArithmeticTsinghua, Thss2010-09-15 09:01:502021-06-01 14:34:072010-09-15 09:27:24enJournal articlesapplication/pdf1Amethod 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.