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

Improved Judgment Algorithm of Point In-out Polygon

作　　者：李楠[1] 肖克炎[1] 

机构地区：[1]中国地质科学院矿产资源研究所,北京100037

出　　处：《计算机工程》2012年第5期30-34,共5页Computer Engineering

基　　金：国家自然科学基金资助项目(41002119);国家"863"计划基金资助项目(2006AA06Z114);国家科技支撑计划基金资助项目(2006BAB01A01);中央级公益性科研院所基本科研业务费专项基金资助项目

摘　　要：为解决多边形内外算法中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.

关 键 词：BSP树 平衡二叉树 任意简单多边形 二分查找 快排序 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]