摘要
提出一种基于二分法判定点集是否在多边形内部的算法 ,根据多边形 L的顶点和边分布的情况 ,分割平面为一组平面区域的有序集合 R,判定 R中每个区域是否在多边形 L内部 ;对于点集 S中的点 p,用二分法搜索 R,找到点 p所属的平面区域 ,从而判定出点 p是否在多边形内部 .该算法在最坏情况下的时间复杂性为 max(O(n log m) ,O(tm log m) ) ,其中 n为点集 S的点数 ,m为多边形 L的顶点数 ,t为多边形 L所有顶点的 X坐标的不同取值个数 .在一般情况下该算法比已有的算法效率更高 .
An algorithm for deciding whether a point set is inside a polygon is given on the basis of binary search method. This algorithm first splits the plane to generate an ordered set R of planar areas, and determines whether it is inside a given polygon L for each area in R . With those preprocessing steps, this algorithm then decides whether it is inside polygon L by binary search in R for each point in a given point set S . The time complexity of the algorithm in the worst case is max (O(n log m) ,O(tm log m)), where n is the number of points in set S , m is the number of vertexes of polygon L , and t is the number of different X ordinate values of all polygon L vertexes. In general cases, this algorithm is more efficient than the existing algorithms.
出处
《福建师范大学学报（自然科学版）》
CAS
CSCD
2001年第3期18-24,共7页
Journal of Fujian Normal University：Natural Science Edition
