判定点集是否在多边形内部的算法
AN AlGORITHM FOR DECIDING WHETHER THE SET OF POINTS IS IN THE POLYGON
-
摘要: 本文提出了判定n个点的点集S是否落入多边形L内部的算法,该算法的复杂性为:max(O(mn),O(lnlogn))次比较和O(ln)次乘法,其中m是L的顶点数,l为S的凸包层数.Abstract: An algorithm for deciding whether the set of points is in the polygon is presented in this paper.The algorithm requires max (O(mn),O(ln log n )) comparisons and O(ln) multiplications,in which n is the number of points of the point set, m is the number of vertices of the polygon,and l is the number of layers in the convex hulls of the point set.
下载: