QQ客服 官方微博 反馈留言

	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).

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。