基于网格中心点的点在多边形内的高效判定

• 作者: 李静 王文成
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 多边形 点包容性检测 网格 中心点
• 年，卷（期）: 2012,（9）
• 所属期刊栏目: 计算机图形学与计算机辅助设计
• 页码范围: 2481-2488
• 页数: 8页
• 分类号: TP391
• 字数: 6440字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2012.04087

摘要

提出一种基于均匀网格的点在多边形内的高效判定算法.它首先建立均匀网格,并从左至右依次计算每个网格单元中心点的位置属性.每个单元中心点的位置属性直接依据其左侧邻接单元已知位置属性的中心点快速获得.在判定点的位置时,确定被测点所在单元,并依据该单元中心点的位置属性判定被测点的位置属性.由于预处理和判定时均利用邻近点的已知位置属性来确定未知点位置属性,可以很好地进行局部化的计算.因此,新方法比现有方法快很多,并且其预处理时间复杂度也由同类网格算法的O(N3/2)下降为O(N).同时,新方法可以统一处理含有自相交及重叠边的非流形多边形.实验结果表明,相比于其他基于均匀网格的方法,新方法可将预处理的速度提高几倍,将判断计算的速度提高十几到几十倍.其速度甚至优于具有该问题最低判定计算时间复杂度O(logN)的基于凸剖分的判定算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李静	中国科学院软件研究所计算机科学国家重点实验室	238	2528	23.0	40.0
2	王文成	中国科学院软件研究所计算机科学国家重点实验室	42	484	13.0	20.0