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

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

技术领域

本发明属于计算机算法、计算机图形学、计算几何、地理信息系统处理领域，具体说是一种涉及点在多边形内判定计算的方法，即：对于一个点的空间位置，判断该位置是否位于一个多边形所限定的空间区域内的方法。

背景技术

点在多边形内的判定计算，是计算机图形学、计算几何、地理信息系统处理中的一种基础计算技术，就是对于一个多边形而言，任一个测试点，要判断该点是否位于该多边形内。这方面的工作很多，其中使用比较广泛的有射线法和基于均匀网格划分的方法。射线法，就是从测试点发出一条射线，统计它与多边形的边的相交次数。如果相交次数为偶数，则测试点在多边形外；否则，在内。射线法要与多边形的每条边进行求交测试，其计算复杂度为O(N)，这里N为多边形的边的数目。为降低计算复杂度，提出了多种方法，先对多边形进行一定的预处理，如将多边形划分成梯形或凸多边形，然后可快速定位测试点所位于的局部区域，再根据局部区域的情况进行判断计算。这类方法可减少需要检测的多边形的边数，计算复杂度可降至O(logN)。但这类方法的预处理比较麻烦。为此，均匀网格方法提出，对多边形的包围盒进行与坐标轴对齐的矩形网格划分，由此可进行简单的预处理，也可将测试点的检测限定于所在网格单元邻近的局部区域进行。经过对多种方法进行对比后，均匀网格方法是适于实际应用的高效的点在多边形内判定计算方法。进一步，提出了将射线法与均匀网格法相结合的方法，先计算各个网格交点位于多边形内/外的属性，然后将测试点与其所在网格单元的网格交点进行连线，就可局部化地使用射线法进行点在多边形内的判定计算。由于一个网格交点与多个网格单元相关，这几个网格单元中的多边形的边都要进行检测。为此，一些方法提出，先计算每个网格单元中心点位于多边形内/外的属性，然后将测试点与其所在网格单元的中心点进行连线处理，并改进了网格中心点位于多边形内/外属性的判定计算方法和网格分辨率的优化处理，以及对一些歧义情况进行鲁棒处理的方法，它们可将均匀网格方法的预处理的计算复杂度降至O(N)，将测试计算的复杂度的期望值降至O(1)。

虽然射线法与均匀网格法的结合将计算复杂度降至最低了，但其基本的测试射线与多边形的边的求交运算依然有较多的乘法、加法等计算，对于计算机处理器而言，计算代价还是比较高。

发明内容

为了解决上述技术问题，本发明提出一种计算机上使用简化求交计算的点在多边形内判定方法，以简化求交计算，并便于高效使用计算机的并行处理能力，由此提高点在多边形内的判断计算效率。本发明对射线法与网格法的结合进行进一步的改进。首先，将测试点发出的射线固定为平行于一个坐标轴的方向，这样就可预先知道交点的一个坐标，降低射线与多边形的边的求交计算复杂性。同时，对网格单元内的多边形的边的片段进行条状结构的管理，使得每个条状结构中的边均可能与位于该条状结构中的射线相交，这样，网格单元中大量与射线无相交的边将无需与射线进行求交计算，并且，这样也有利于使用GPU进行并行计算以更好地提高效率，因为无需进行费时的分叉处理以判断射线是否与边可能相交。

本发明的技术方案，为一种简化求交计算的点在多边形内判定方法，包括以下步骤：

步骤(1)将多边形的顶点坐标读入计算机内存，以生成多边形的包围盒，使得包围盒的边界均位于多边形外；对多边形的包围盒进行与坐标轴对齐的均匀网格划分，依据多边形的边与X轴或Y轴平行的网格线的交点将这些网格线划分成许多片段，并判断并记录各个网格线片段位于多边形内/外的属性；

步骤(2)在每个网格单元中生成条状结构，以管理网格单元中所含的多边形的边片段，在此，一个条状结构是由平行于Y轴或X轴的边作为边界构成，使得其中的多边形的边片段与该条状结构的两端边界均相交；

步骤(3)输入测试点进行检测时，利用单独处理器或并行的多个处理器，对于每一个测试点，从其发出一条平行于Y轴或X轴射线，由近至远逐步计算其与X轴或Y轴平行网格线的交点，直至该交点位于多边形内/外的属性能够由其所在的网格线的片段位于多边形内/外的属性获知，此时，终止射线的前行；

步骤(4)将要用到的相关条状结构调入，在单独处理器或并行处理器中，进行点在多边形内的判断计算；此时，对于从一个测试点发出的射线，计算其与所经过的条状结构中的多边形的边的相交情况，统计该射线与多边形的边的相交次数；

步骤(5)根据步骤(3)和(4)的结果，得知测试点位于多边形内/外的属性。

进一步的，所述步骤(1)对网格线被其与多边形的边的交点所划分的片段位于多边形内/外属性的判断，其步骤是如下：

(1.a)将一条网格线可看作是从其最外端的一个点发出的一条射线，并与多边形的边进行求交而得到这条网格线与多边形的边相交情况；

(1.b)网格线的最外端的点是位于多边形外的。同时，根据点在多边形内判断计算的射线法，可知相邻的网格线片段位于多边形内/外的属性是交替变化的，由此，可知网格线上各个片段位于多边形内/外的属性。

进一步的，所述步骤(2)对于每个网格单元中的多边形的边片段，建立条状结构进行管理，其步骤如下：

(2.a)对于一个网格单元中的边片段，根据它们位于该网格单元中的端点的X或Y坐标值，生成许多平行于Y或X坐标轴的平行线，由这些平行线作为边界将该网格单元剖分成许多条状结构；

(2.b)每个条状结构记录其所包含的边，无需记录该边片段的端点的坐标。

进一步的，所述步骤(3)对一个测试点进行测试时发出的射线是与条状结构的边界边平行的。

进一步的，所述步骤(3)对从测试点发出的射线与网格线进行由近至远的求交时，判断该交点位于多边形内/外的属性是否可由其所位于的网格线片段位于多边形内/外的属性来获知，并由此决定射线是否停止前进；如果可获知，则该射线停止前进；否则，该射线要继续往前与后续网格线进行求交处理。

进一步的，所述步骤(4)对一条测试用的射线与其经过的每个条状结构中的多边形的边进行求交测试时，无需在求交点前进行该边是否与射线相交的检测，因此便于使用计算机的并行能力，如减少使用GPU时的费时的分叉处理。计算射线与一条边的交点时，该交点的一个坐标值是已知的，就是该射线所垂直的坐标轴的坐标值；通过判断交点的另一个坐标值与测试点的另一个坐标值的大小，即可知射线与该边是否真的相交。

进一步的，所述步骤(5)中综合步骤(3)和(4)的结果，得到测试点位于多边形内/外的属性，其处理如下：

(5.a)如果射线终止前行时与网格线的交点位于多边形内，则射线与多边形的边相交次数为偶数时，测试点位于多边形内；否则，在外；

(5.b)如果射线终止前行时与网格线的交点位于多边形外，则射线与多边形的边相交次数为偶数时，测试点位于多边形外；否则，在内。

有益效果：

本发明能极大的节省求交计算中的乘法、加法等运算，并能高效使用计算机的并行处理能力如GPU等，可大幅提高点在多边形内的判定计算效率。

附图说明null实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整的描述。显然，所描述的实施例仅为本发明的一部分实施例，而不是全部的实施例，基于本发明中的实施例，本领域的普通技术人员在不付出创造性劳动的前提下所获得的所有其他实施例，都属于本发明的保护范围。

本发明是一种使用计算机简化求交计算的点在多边形内判定方法，能够用于工程中诸多场景，比如说，在地理信息系统中，对于一个区域的道路、楼房、公园等以多边形方式进行区域限定；当要对某些目标进行定位时，如某辆汽车是否位某条道路上、或位于某个公园内等，则可使用本发明进行快速检索。或者，当洪水浸漫一个城市时，洪水覆盖的区域可用多边形表达，则使用本发明可快速知道哪些位置还没有被洪水覆盖、是安全的。

根据本发明的一个实施例，不失一般性，本发明将条状结构和测试用的射线均按照平行Y轴的方向生成，且射线是从测试点向上射出(其Y坐标逐步增大的方向)，如图1所示。

根据本发明的一个实施例，本发明上述方法分二个阶段：

第一阶段对多边形进行预处理；

第二阶段：根据预处理结果，判定一个测试点是否位于多边形内。

第一段的工作步骤如下：

1)检测多边形所有顶点的X坐标和Y坐标，得到最小的X坐标、最小的Y坐标、最大的X坐标和最大的Y坐标。然后将最小X坐标和最小的Y坐标均各自降低预定数值，将最大的X坐标和最大的Y坐标均各自增大预定数值，由此得到该多边形的包围盒，且包围盒的边界均位于多边形外。

2)对包围盒进行网格分辨率优化的均匀网格剖分。根据“Jing Li and WenchengWang.2014.Point-In-Polygon Tests by Applying the Ray Crossing Method LocallyVia Grid Center Points.International Journal of Electrical Engineering 21,3(2014),85–92.”中的方法计算每个网格单元沿X、Y轴方向的长度Mx和My分别为：

Mx＝k*sqrt(M*W/H),

My＝k*sqrt(M*H/W)