逐行(列)扫描判定点集是否在多边形内部的算法

• 作者: 潘日红
• 来源期刊: 福建师范大学学报（自然科学版）
• 学科: 数学
• 关键词: 点集 多边形 排序 逐行扫描
• 年，卷（期）: 2000,（4）
• 页码范围: 17-21
• 页数: 5页
• 分类号: O241
• 字数: 2497字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-5277.2000.04.004

摘要

提出一种基于点集排序,逐行(或逐列)扫描平面点集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中的点分布的行数和列数.该算法思路简单,易实现,且在一般情况下,效率比已有的算法高.

作者信息

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