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

摘要

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