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

摘要

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