逐行(列)扫描判定点集是否在多边形内部的算法  

A Row(column) scanning based Algorithm for Deciding whether a Point Set Is Inside a Polygon

作　　者：潘日红[1] 

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

出　　处：《福建师范大学学报（自然科学版）》2000年第4期17-21,共5页Journal of Fujian Normal University：Natural Science Edition

摘　　要：提出一种基于点集排序 ,逐行 (或逐列 )扫描平面点集 S,判定点集 S中的点是否在多边形 L内部的算法 .该算法的时间复杂性在最坏情况下为 :max( O( n log n) ,O( km log m) )次比较和 O( km)次乘法 .其中 n为点集 S的点数 ,m为多边形 L的顶点数 ,k=min( u,v) ,其中 u,v分别为点集 S中的点分布的行数和列数 .该算法思路简单 ,易实现 ,且在一般情况下 。A row(column) scanning based algorithm is presented for deciding whether a point set is inside a polygon. The sort to the point set is used in this algorithm. In the worst cases, the algorithm requires  max (O(n log n),O(km log m)) comparisons and O(km) multiplications, where n is the number of points in the point set, m is the number of vertices of the polygon, and k= min (u,v),where u,v are numbers of rows and columns in which the point set are distributed respectively. In the general cases, this algorithm is more efficient than the existing algorithms.

关 键 词：点集 多边形 排序 逐行扫描 时间复杂性 点分布 判定算法 行数 列数 凸包 逐列扫描 

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