基于二分法判定点集是否在多边形内部的算法  

An Algorithm for Deciding Whether a Point Set Is Inside a Polygon Based on Binary Search

作　　者：潘日红[1] 

机构地区：[1]福建师范大学计算机科学系,福建福州350007

出　　处：《福建师范大学学报（自然科学版）》2001年第3期18-24,共7页Journal of Fujian Normal University：Natural Science Edition

摘　　要：提出一种基于二分法判定点集是否在多边形内部的算法 ,根据多边形 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.

关 键 词：点集 多连形 平面区域 二分法 判定 计算机算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]