Improved Judgment Algorithm of Point In-out Polygon
Keyan Xiao · Jisuanji gongcheng · 2012
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.