平面线段相交问题的渐缩规整包围盒过滤规则
Shrinking Regular Bounding Box Filter for Line Segment Intersection Problem
-
摘要: 平面线段相交是计算几何的基本问题之一,通常采用基于包围盒过滤规则的平面扫描方法求解.但这些过滤规则没有利用算法执行过程中线段有效部分逐渐缩短的性质,导致候选集和冗余计算增加.通过量化包围盒的主对角线斜率,并使量化后的包围盒逐渐缩小,提出更加严格的渐缩规整包围盒过滤规则.实验数据表明,相比于包围盒过滤规则,文中提出过滤规则的候选集和计算量平均分别减少16%和14%.Abstract: Line segment intersection is one of the most important problems in computational geometry.Plane sweep algorithm is commonly used for this problem with bounding box(BB) filter.However,it is ignored in this filter that the effective part of segment will be shrunk with sweep line moving,so both candidate segment pairs and computational costs are increased.A shrinking regular BB filter is proposed as a strict one,in which the BB is shrunk after the slope of main diagonal of BB is quantified.Experimental results show that the quantities of candidate segment pairs and computation are reduced by on average 16% and 14% respectively.
下载: