| 判定点集是否在多边形内部的算法 |
| |
| 引用本文： | 周培德.判定点集是否在多边形内部的算法[J].计算机研究与发展,1997,34(9):672-674. |
| |
| 作者姓名： | 周培德 |
| |
| 作者单位： | 北京理工大学计算机系 |
| |
| 摘 要： | 本文提出了判定ｎ个点的点集Ｓ是否落入多边形Ｌ内部的算法，该算法的复杂性为：ｍａｘ（Ｏ（ｍｎ），Ｏ（ｌｎ ｌｏｇ ｎ））比比较和Ｏ（ｌｎ）次乘法，其中ｍ是Ｌ的顶点数，ｌ为Ｓ的凸包层数。
|
| 关 键 词： | 点集 多边形 凸包 算法 |
AN AlGORITHM FOR DECIDING WHETHER THE SET OF POINTS IS IN THE POLYGON |
| |
| ZHOU Pei De.AN AlGORITHM FOR DECIDING WHETHER THE SET OF POINTS IS IN THE POLYGON[J].Journal of Computer Research and Development,1997,34(9):672-674. |
| |
| Authors: | ZHOU Pei De |
| |
| 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. |
| |
| Keywords: | set of points polygon convex hullClass number\ TP391 4 TP301 6 |
| 本文献已被 CNKI 维普 等数据库收录！ |
