平面线段相交问题的渐缩规整包围盒过滤规则

摘要：

平面线段相交是计算几何的基本问题之一,通常采用基于包围盒过滤规则的平面扫描方法求解.但这些过滤规则没有利用算法执行过程中线段有效部分逐渐缩短的性质,导致候选集和冗余计算增加.通过量化包围盒的主对角线斜率,并使量化后的包围盒逐渐缩小,提出更加严格的渐缩规整包围盒过滤规则.实验数据表明,相比于包围盒过滤规则,文中提出过滤规则的候选集和计算量平均分别减少16%和14%.

关键词：线段相交、平面扫描、包围盒、渐缩规整包围盒、过滤规则

所属期刊栏目：20

分类号：TP391(计算技术、计算机技术)

资助基金：国家"九七三"重点基础研究发展规划项目2004CB318202

在线出版日期：2008-11-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：1345-1352