一种改进的点在多边形内外判断算法

Improved Judgment Algorithm of Point In-out Polygon

为解决多边形内外算法中BSP树退化为链表的问题,提出一种改进的点在多边形内外的判断算法。在构建水平扫描线的BSP树之前,对水平扫描线按照Y值进行排序,将排好序的水平扫描线按照二分法的顺序插入到BSP树中,其查找时间复杂度为O(lbn)。实验结果表明,该算法在不增加BSP构建时间复杂度的前提下,能够保证BSP树的查找效果总是最优的,且简单易行,具有较好的通用性。

For settling a problem that Binary Space Partition（BSP） tree of in-out polygon algorithm degenerates into line list,this paper presents an improved judgment algorithm of point in-out polygon.The algorithm sorts Y value per node in polygon.It travels all horizon lines by way of binary.BSP tree is always balance binary tree.The time complexity of the BSP-Tree searching is O（lbn）.Experimental results show that the improved algorithm makes sure that time complexity for the query of binary space partition trees is always high efficient while time complexity for the construction of BSP trees does not increase.Meanwhile,it has good versatility.