Line segment intersection testing | |
Zhu, YK ; Yong, JH ; Zheng, GQ | |
2010-05-07 ; 2010-05-07 | |
关键词 | intersection testing for line segments floating-point arithmetic rounding error dot product summation FLOATING-POINT SUMMATION ALGORITHM ACCURATE Computer Science, Theory & Methods |
中文摘要 | A method 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 3x3 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. |
语种 | 英语 ; 英语 |
出版者 | SPRINGER WIEN ; VIENNA ; SACHSENPLATZ 4-6, PO BOX 89, A-1201 VIENNA, AUSTRIA |
内容类型 | 期刊论文 |
源URL | [http://hdl.handle.net/123456789/16740] ![]() |
专题 | 清华大学 |
推荐引用方式 GB/T 7714 | Zhu, YK,Yong, JH,Zheng, GQ. Line segment intersection testing[J],2010, 2010. |
APA | Zhu, YK,Yong, JH,&Zheng, GQ.(2010).Line segment intersection testing.. |
MLA | Zhu, YK,et al."Line segment intersection testing".(2010). |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论