| 基于二分法判定点集是否在多边形内部的算法 |
| |
| 引用本文： | 潘日红. 基于二分法判定点集是否在多边形内部的算法[J]. 福建师范大学学报(自然科学版), 2001, 17(3): 18-24 |
| |
| 作者姓名： | 潘日红 |
| |
| 作者单位： | 福建师范大学计算机科学系 |
| |
| 摘 要： | 提出一种基于二分法判定点集是否在多边形内部的算法，根据多边形L的顶点和边分布的情况，分割平面的一组平面区域的有序集合R，判定R中每个区域是否在多边形L内部；对于点集S中的点p，用二分法搜索R，找到点p所属的平面区域，从而判定出点p是否在多边形内部。该算法在最坏情况下的时间复杂性为max(O(n log m),O(tm log m)，其中n为点集S的点数，m为多边形L的顶点数，t为多边形L所有顶点的X坐标的不同取值个数，在一般情况下该算法比已有的算法效率更高。
|
| 关 键 词： | 点集 多连形 平面区域 二分法 判定 计算机算法 |
| 文章编号： | 1000-5277(2001)03-0018-07 |
| 修稿时间： | 2001-04-18 |
An Algorithm for Deciding Whether a Point Set Is Inside a Polygon Based on Binary Search |
| |
| PAN Ri hong. An Algorithm for Deciding Whether a Point Set Is Inside a Polygon Based on Binary Search[J]. Journal of Fujian Teachers University(Natural Science), 2001, 17(3): 18-24 |
| |
| Authors: | PAN Ri hong |
| |
| Abstract: | |
| |
| Keywords: | point set polygon planar area binary search |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
