| 逐行(列)扫描判定点集是否在多边形内部的算法 |
| |
| 引用本文： | 潘日红.逐行(列)扫描判定点集是否在多边形内部的算法[J].福建师范大学学报(自然科学版),2000,16(4):17-21. |
| |
| 作者姓名： | 潘日红 |
| |
| 作者单位： | 福建师范大学计算机科学系,福建,福州,350007 |
| |
| 摘 要： | 提出一种基于点集排序，逐行（或逐列）扫描平面点集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 for Deciding whether a Point Set Is Inside a Polygon |
| |
| PAN Ri-hong.A Row(column)- scanning- based Algorithm for Deciding whether a Point Set Is Inside a Polygon[J].Journal of Fujian Teachers University(Natural Science),2000,16(4):17-21. |
| |
| Authors: | PAN Ri-hong |
| |
| Abstract: | |
| |
| Keywords: | point set polygon sort row sc |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
