一种计算机上使用简化求交计算的点在多边形内判定方法

摘要

本发明涉及一种计算机上使用简化求交计算的点在多边形内判定方法，步骤如下：将多边形的顶点坐标读入计算机内存，以生成多边形的包围盒，对多边形的包围盒进行均匀网格划分，并在网格单元中生成平行于一个坐标轴的条状结构；同时，判断网格线被其与多边形的边的交点所分割的片段是否位于多边形内/外的属性；对于一个测试点，从其发出一条射线，平行于条状结构生成时所平行的坐标轴；统计该射线所相交的多边形边的数目，直至其抵达一个非歧义的网格线片段；根据相交次数的奇偶性和该射线所抵达网格线片段位于多边形内/外的属性，即可知该测试点是否位于多边形内。本发明能极大地简化求交计算，并高效利用计算机并行处理能力，大幅提高计算效率。