基于二分法判定点集是否在多边形内部的算法

• 作者: 潘日红
• 来源期刊: 福建师范大学学报(自然科学版)
• 学科: 数学
• 关键词: 点集 多边形 平面区域 二分法
• 年，卷（期）: 2001,（3）
• 页码范围: 18-24
• 页数: 7页
• 分类号: O241
• 字数: 4278字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-5277.2001.03.005

摘要

提出一种基于二分法判定点集是否在多边形内部的算法,根据多边形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坐标的不同取值个数.在一般情况下该算法比已有的算法效率更高.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	潘日红	福建师范大学计算机科学系	9	68	5.0	8.0