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

作     者：王盛春 王文成 谭雪晗 李静 WANG Sheng-chun;WANG Wen-cheng;TAN Xue-han;LI Jing

作者机构：中国科学院软件研究所计算机科学国家重点实验室北京100190 中国科学院大学计算机科学与技术学院北京100190 中国科学院动物研究所动物进化与系统学院重点实验室北京100101 

出 版 物：《图学学报》 (Journal of Graphics)

年 卷 期：2019年第40卷第2期

页      面：267-273页

学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家重点研发计划项目(2017YFB1002700) 国家自然科学基金项目(61661146002 61872348) 

主　　题：多边形 网格 简便计算 点在多边形内的检测 

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