摘要
本文提出了判定ｎ个点的点集Ｓ是否落入多边形Ｌ内部的算法，该算法的复杂性为：ｍａｘ（Ｏ（ｍｎ），Ｏ（ｌｎｌｏｇｎ））次比较和Ｏ（ｌｎ）次乘法，其中ｍ是Ｌ的顶点数，ｌ为Ｓ的凸包层数．
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.
出处
《计算机研究与发展》
EI
CSCD
北大核心
1997年第9期672-674,共3页
Journal of Computer Research and Development
关键词
点集
多边形
凸包
算法
set of points, polygon, convex hullClass number\ TP391.4
TP301.6
