加强局部简便计算的点在多边形内的高效判定

• 作者: 李静 王文成 王盛春 谭雪晗
• 来源期刊: 图学学报
• 学科: 工学
• 关键词: 多边形 网格 简便计算 点在多边形内的检测
• 年，卷（期）: 2019,（2）
• 所属期刊栏目: 专论:第21届中国计算机图形学大会(CHINAGRAPH 2018 广州)
• 页码范围: 267-273
• 页数: 7页
• 分类号: TP391
• 字数: 5596字
• 语种: 中文
• DOI: 10.11996/JG.j.2095-302X.2019020267

摘要

点在多边形内的检测是计算几何中的一个基本问题,有着广泛的应用需求.已提出许多方法减少要测试的多边形的边以加速.其中,均匀网格法具有很好的作用,因为各网格中的边很少,而测试点可迅即定位于一个网格.我们曾提出一种均匀网格法,预计算各网格中心点位于多边形内/外的属性,然后将测试点与所在网格的中心点连线,检测该连线与多边形的边的相交情况即可.其预处理和检测的复杂度分别为O(N)和O(N),N为多边形的边数.本文在此基础上进一步改进,预计算网格交点位于多边形内/外的属性,然后将测试点与其邻近网格交点的连线,转换为与坐标轴平行的两条相连直线段,以提高与多边形边求交计算的便捷性.实验结果表明,可将检测速度提高2倍多.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李静	中国科学院动物研究所动物进化与系统学院重点实验室	238	2528	23.0	40.0
2	王文成	中国科学院软件研究所计算机科学国家重点实验室	42	484	13.0	20.0
6	王盛春	中国科学院软件研究所计算机科学国家重点实验室	1	0	0.0	0.0
10	谭雪晗	中国科学院软件研究所计算机科学国家重点实验室	1	0	0.0	0.0