一种判定点是否位于多边形内的方法

本发明提供一种判定点是否位于多边形内的方法。该方法大致可分为两个步骤：先将多边形包围盒进行均匀地矩形网格剖分，由外及里逐步计算各个网格中心点的位置属性；再根据已获知‘内/外’属性的网格中心点和待测点的连线与多边形边的相交关系判定待测点位置。本发明操作简单，计算速度快，能有效减少判定计算要处理的多边形边的数量，还能统一处理多边形有自相交、重叠边等非流形情况，可很好地降低计算开销。

技术领域

[0001] 本发明涉及一种点在多边形内的判定计算方法，属于计算机算法、计算几何技术、计算机图形技术领域，具体说是一种基于网格划分快速执行点在多边形内判定计算的方法。

背景技术

[0002] 点在多边形内的判定计算是一种基本的计算几何技术，在计算机图形学、计算几何、地理信息系统等方面有着广泛的应用。该问题的描述是：给定多边形P和任意点Q，判定点Q是否位于多边形P内。

[0003] 关于多边形的点包容性判断的工作很多，基本可分为两类：一类是依靠计算某些参数得到判定结果。例如经典的射线法(ray-crossing) (Foley JD, van Dam A, FeinerSK, Hughes JF. Computer Graphics-Principles and Practice. 2nd ed. Reading, MA ：Addison-ffesley. 1990.),就是过待测点向某方向作一条射线,计算该射线与多边形的边的交点个数来进行判定。若有奇数个交点，则该点位于多边形内；否则位于多边形外。这种方法简单直观，可处理任意多边形，通常被用作与其他算法对比的基准算法。其它的还有基于角度之和的算法(Hormann K, Agathos A. The point in polygon problem for arbitrarypolygons. Computational Geometry ：Theory and Applications 2001 ;20 :131-144.)、基于三角形操作的算法（Feito FR，Torres JC. Inclusion test for general polyhedra.Computers & Graphics 1997 ；21 (I) :23-30.)等。这类算法的实现较为简单，但需要进行逐边操作，计算时间复杂度均为O(N)，这里N为多边形的边数。

[0004] 另一类则是通过将多边形分解为一些简单的几何单元，建立某种辅助结构来加速判定操作，如梯形法(Borut Zalik, Gordon J. Clapworthy, Auniversal trapezoidationalgorithm for planar polygons. Computers & Graphics 23(1999) :253-263.)、网格法(Zalik B， Kolingerova A cell-based point-in-polygon algorithm suitable forlarge sets of points.Computers &Geosciences 2001;27:1135-1145。和 Sheng Yang，Jun-Hai Yong，Jiaguang Sun，Hejin Gu,Jean-Claude Paul. A point-in-polygon methodbased on a quasi-closest point.Computers &Geosciences 36(2010) :205-213.)、分层法(Wencheng Wang, Jing Li，Enhua Wu. 2D point-in-po lygon test by classifyingedges into layers. Computers & Graphics 29(2005) :427-439.)、凸剖分法（JingLi，Wencheng Wang, Enhua Wu. Point-in-Polygon Tests by Convex Decomposition.Computers & Graphics 31 (2007) :636-648)、层次三角形（Juan J. Jimenez, FranciscoR.Feitoa, Rafael J. Seguraa. A new hierarchical triangle-based point-in-polygondata structure. Computers & Geosciences 35(2009) :1843-1853.)等。这类算法虽然能提高检测计算的效率，但其预计算的开销一般比较大。一般而言，它们比较适合于对同一多边形进行多次检测的应用。

[0005] 凸剖分法（Jing Li, Wencheng Wang, Enhua Wu. Point-in-Polygon Tests byConvex Decomposition. Computers & Graphics 31(2007) :636-648)是先将多边形凸剖分并以树结构管理所得的凸多边形，判定时通过树结构快速查找可能包含待测点的凸多边形，然后以高效的凸多边形点检测算法确定待测点是否在多边形内。当剖分得到的凸边形个数较少时，该算法具有很高的效率。但随着凹点数目的增多，凸多边形数目随之增多，检测时间增长。此外，凸剖分法的预处理时间也相对较长。

[0006] 网格结构简单，仓Il建迅速，在实际中得到较多的应用。文献（Zalik B,KolingerovaA cell-based point-in-polygon algorithm suitable for large sets of points.Computers &Geosciences 2001 ；27 :1135_1145。)将多边形所在区域均匀剖分为 O(N)个网格，并为每个网格单元标记其位于多边形内、外、或是多边形边界上。在检测时，一一判定待测点和网格单元的位置关系，若待测点位于内部或外部网格单元内，则可以0(1)时间直接断定点位于多边形的内部或外部；若待测点位于边界网格单元中，则需要查找距待测点最近的边，并根据待测点与此最近边的位置关系得到最终判定结果。该方法的期望预处理时间为0(N3/2)，空间开销为O(N)，检测时间复杂度为0(N1/2)。但该判定方法的判定相对复杂，在最近点与待测点位于不同单元或者多边形的两条邻边几乎共线时会出现错误。为此，文献(Sheng Yang, Jun-Hai Yong, Jiaguang Sun, Hejin Gu, Jean-Claude Paul. Apoint-in-polygon method based on a quasi-closest point. Computers & Geosciences36(2010) :205-213.)提出了一种被称为“quasi-closest point”的改进方法（简称QCPM)，即附加一些约束条件并扩大查找范围至相邻单元，以找到合适的距待测点最近的边，以免选择错误而导致判定出错。这样，这种方法在判定时就需要处理多个网格单元。

[0007]由于点在多边形内的判定计算是一种基本计算，其效率对于应用系统的工作效率有很大的影响，因此，研究其高效处理的方法一直是国际上讨论的热点问题。

发明内容

[0008] 本发明的目的在于发掘局部相关性，以提高点在多边形内判定计算的效率。本发明提供一种基于矩形网格中心点判定待测点位置属性的方法。该方法大致可分为两个步骤：先将多边形包围盒进行均匀地矩形网格剖分，逐步计算各个网格中心点的位置属性；再根据已获知‘内/外’属性的网格中心点和待测点的连线与多边形边之间的关系判定待测点位置。

[0009] 在判定网格中心点的位置属性时，我们先处理靠近包围盒边沿的网格单元，即：对于任一个靠近包围盒边沿的网格中心点，将其与包围盒外任一点进行连线，然后计算与该连线相交的多边形边的数目，以判断这些点是否位于多边形内；然后，按照一定传递方式，如根据已获知其‘内/外’属性的网格中心点，由外及里逐步地递推计算它们邻近网格中心点是否位于多边形内，也就是说，任一个未知位置属性的网格中心点，与它附近已处理的网格中心点（只有第一次是与包围盒外的点）进行连线，然后计算与该连线相交的多边形边的数目，即可判断该点是否位于多边形内。以上过程逐步地进行，直至所有网格中心点获得其位于多边形‘内/外’的属性。如图I所示，我们按照由左往右的方式，逐步地计算各个网格中心点与多边形的位置关系。

[0010]在判断一个待测点是否位于多边形内时，我们根据其坐标得知它所在的网格单元，然后，将该网格单元中心点与待测点进行连线，计算与该连线相交的多边形边的数目。根据相交的边的数目和该中心点的‘内/外’属性，即可判断待测点是否位于多边形内。判断计算如下：如果相交的边数是奇数，则待测点的‘内/外’属性与该中心点的‘内/外’属性是相反的；反之，相交的边数是偶数，则待测点的‘内/外’属性与该中线点的‘内/外’属性是相同的。这可以根据射线法的原理很方便地推导出来。

[0011] 在本发明的处理中，有一些奇异情况要处理，即：网格中心点位于多边形的顶点或边上，这样的网格中心点被称为奇异点。对此，我们的处理如下：对于奇异点，我们进行标志；然后在进行检测计算时，如果待测点所在网格单元的中心点是一个奇异点，我们就沿着一定的方向（一般是沿着平行坐标轴的某个方向）逐步地搜索邻近的网格单元，直至找到一个非奇异的网格中心点（包围盒的外面的任一点都位于多边形外，在本发明中都作为非奇异网格中心点处理）。

[0012] 本发明的有益效果如下：

[0013] 与现有关于点在多边形内的判定计算方法相比，特别是与基于网格剖分的同类相 t匕，本发明的预计算简单快速，检测计算也很简便，空间需求少，能有效减少判定计算要处理的多边形边的数量，很好地利用局部计算降低计算开销。

[0014] 此外，由于本发明在检测时仅需要求线段相交多边形边的数量，因此本发明对于自相交、重叠边等非流形情况能够等同地处理。

附图说明null实施方式

[0019] 本发明包括两个阶段：第一阶段是对多边形的包围盒进行均匀的网格划分，并计算各个网格中心点（预测点）与多边形的位置关系；第二阶段是根据预测点的位置属性，对待测点进行局部计算，以判断待测点与多边形的位置关系。

[0020] 第一阶段的步骤如下：

[0021] I)根据文献（Zalik B, Kolingerova I.A cell-based point-in-polygonalgorithm suitable for large sets of points. Computers & Geosciences 2001 ；

27 :1135-1145.)中经验公式，计算网格划分的分辨率，即：^，

UD. ■ : ,其中，W和H分别为网格包围盒的长度和宽度，而No0fCellsx和NoOfCellsy分别是沿X轴y轴方向的网格单元个数。

[0022] 2)在确定分辨率后，要为每个网格单元计算落入其中的边，并将边指针加入相关网格单元。也就是说在确定分辨率后，要为每个网格单元计算并记录落入其中的边。所谓的边指针是指程序实现中指向边结构的指针。为了快速实现该过程，我们使用DDA算法(Cleary, J. C. , Wyvill, G. Analysis of an algorithm for fast ray tracing usinguniform space subdivision. The Visual Computer 1988 ；4 (2) :65-83)，仅以加法递增计算各个边占据的网格单元。

[0023]3)在创建网格之后，计算每个网格中心点的‘内/外’属性，也就是判定这些中心点位于多边形之内还是之外。

[0024] 具体方法是：在判定网格中心点的位置属性时，我们先处理靠近包围盒边沿的网格单元，即：对于任一个靠近包围盒边沿的网格中心点，将其与包围盒外任一点进行连线，然后计算与该连线相交的多边形边的数目，以判断这些点是否位于多边形内；然后，按照一定传递方式，如根据已获知其‘内/外’属性的网格中心点，由外及里逐步地递推计算它们邻近网格中心点是否位于多边形内，也就是说，任一个未知位置属性的网格中心点，与它附近已处理的网格中心点（只有第一次是与包围盒外的点）进行连线，然后计算与该连线相交的多边形边的数目，即可判断该点是否位于多边形内。以上过程逐步地进行，直至所有网格中心点获得其位于多边形‘内/外’的属性。如图I所示，自左至右遍历各个网格单元，并递推地进行判定计算各个网格中心点与多边形的位置关系。

[0025] 第二阶段的步骤如下：

[0026] I)根据待测点Q的坐标找到它所在的网格单元Cti, j，其中i，j分别为单元X，Y方向上的坐标。

[0027] 2)检测网格单元的中心点的标志，看它是否是奇异点。如果是奇异点，我们就从“往左、往右、往上、往下”中任选一个方向，从该网格单元出发，逐个地搜索所考察的邻近网格中心点是否是奇异的，直至找到一个非奇异的网格中心点，设为Μ’

[0028] 3)连一条从Q到中心点M’ ti,的连线QM’ ti,(称为待测边)。

[0029] 4)遍历该连线穿过的该网格单元中所有的边，记录与QM’ u有交的多边形边的个数。如果相交边数为偶数，则待测点Q与网格中心点M，[U的‘内/外’属性相同；否则，待测点Q与M’ 的‘内/外’属性相反。

[0030] 因为每条多边形的边为一条线段，故在本发明中，要检测多边形的边是否与两个点的连线相交，也就是说，要判断两条线段是否相交，可以通过判定点与直线的相对位置关系实现。即设有两条线段ei和e2，若ei的两个顶点分别位于e2的两侧，并且e2的两个顶点分别位于ei的两侧，则认为ei与e2有交；否则认为ei与e2无交。

[0031] 判断一个点Q与一条边e关系的方法如下：设边e的两个顶点分别为Ptl和P1, Q为待测点。计算向量获与向量可f的叉积的Z值。若该值大于0，则认为Q在e的右侧；否则认为Q在e左侧。如此得到的点与边的关系仅分为两种，即左侧与右侧。如果点与边共线，则强制认为其位于直线的某一侧（如设为左侧），这种行为称为强制设定规则。这样做的优点是避免了对奇异情况的特殊处理。它在各种奇异情况下均能得到正确的结果，下面举出几个例子作为说明，其他奇异情况以此类推。

[0032] 设沿多边形的边逆时针行走时（即图2中的箭头方向），左手侧为多边形内，右手侧为多边形外。若待测点与网格中心点的连线穿越多边形的顶点，则可能出现图2(a)、(b)所示的情况。M，是作为参考的已知位置属性的非奇异点，不失一般性可假定为多边形内。在图2(a)中，按照强制设定规则，相交AP1位于M’ Q1的左侧，而多边形的边士和匕的另一端也在M’ Q1的左侧，因此M’ Q1与和Id1均无交，Q1M,的位置属性相同，皆为内部。结论正确。图2(b)中，对于Q2，相交点P2的位置被强制设为M’ Q2的左侧，那么M’ Q2与b2无交，与a2有交。相交数量为1，02与『的位置属性相异，即Q2位于多边形外，结论正确。若待测点与网格中心点的连线与多边形的边共线，则可能出现图2(c)、（d)所示的情况。图2 (c)中，多边形的边b3与M，Q3重合，按照强制设定规则，边b3位于M，Q3的左侧，与M’ Q3无交。M’Q3分别与&3和C3相交，相交个数为2，因此Q3与,的属性相同，均为多边形内。而在图2(d)中，比与皿’ Q4重合。判定时，b4被判定为位于M’ 04的左侧，M’ Q4仅与a4相交。因此，Q4与,的属性相反，位于多边形外。

[0033] 由于本发明在检测时只需求解线段相交多边形边的数量，因此本发明对于自相交、重叠边等非流形情况能够等同地处理。以图3为例，图3(a)中，多边形的边P5Pc^P P2P3自相交，中心点M位于多边形内，测试边QM与P5Pci和P2P3均相交，交点数为偶数，所以Q位 于多边形内。在图3(b)中，边P2P3和P3P2重叠，中心点則立于多边形内，测试边QM与P2P3和P3P2均相交，交点数为偶数，所以Q位于多边形内。

[0034] 为了验证新算法的性能，我们在一台配置有2. 85GHz CPU，4GB RAM的台式机上与其他算法进行了对比实验。用于对比的算法分别来自于网格法（Zalik B, KolingerovaI. A cell-based point-in-polygon algorithm suitable for large sets of points.Computers &Geosciences 2001 ；27 :1135-1145)、网格改进法 QCPM (Sheng Yang，Jun-HaiYong, Jiaguang Sun，Hejin Gu, Jean-Claude Paul. A point-in-polygon method basedon a quasi-closest point. Computers & Geosciences 36(2010) :205-213.)和凸剖分法(Jing Li，Wencheng Wang，Enhua Wu. Point-in-Polygon Tests by ConvexDecomposition. Computers & Graphics31 (2007) :636-648.)。其中，网格法和 QCPM 的数据直接引用自文献（ShengYang，Jun-Hai Yong, Jiaguang Sun, Hejin Gu, Jean-ClaudePaul.A point-in-polygon method based on a quasi-closest point. Computers &Geosciences 36(2010) :205-213.)。其试验中使用的计算机配置为 2. 93GHz CPU，512MBRAM，优于我们实验的机器。凸剖分法为三叉树实现。被测多边形均来自文献（Zalik B，Kolingerova I.A cell-based point-in-polygon algorithm suitable forlarge setsofpoints. Computers & Geosciences 2001 ；27 :1135-1145)，如图 4 所不。待测点个数均为1，000，000，均匀分布在比网格包围盒稍大的范围内，图4a)为多边形pollO，图4b)为多边形pollOO，图4c)为多边形poll249，图4d)为多边形pol28000。表I列出了实验结果，包括各种算法的预处理时间、1，000，000个点的判定时间、预处理和判定的总时间（单位均为秒），以及新方法相对于这些对比方法的计算加速率。在此，各种网格方法都是基于同样的网格划分分辨率进行的。

[0035] 表I本发明与其他方法的对比实验数据

[0036]

[0037]

[0038] #rp = (Tp_old-Tp_new) /Tp_new, Tp_old是对比方法预处理的时间，Tp_new是新方法的预处理时间。

[0039] rd = (Td_old-Td_new) /Td_new, 是对比方法判定计算的时间，Td_new是新方法判定计算的时间。

[0040] $rt = (Tt_old-Tt_new) /Tt_new, Tt_old是对比方法的总时间开销，Tt_nOT是新方法的总时间开销。

[0041] 由表I可知，与凸剖分法相比较，除多边形pollO外，本发明的效率均优于凸剖分算法。这是因为在多边形边数较少、凹点较少的情况下，凸剖分方法需要处理的凸多边形较少，因此会稍快。而当多边形的复杂度提高时，本发明则优于凸剖分法，且多边形的边数越多，凹点数越多，本发明的优势越明显。与其他基于网格划分的方法相比，本发明的优势明显，在预处理时可节省数倍的时间，而在判定计算时可提高一个数量级。从表I中可知，本发明的总时间开销很少，这是有利于动态情况下的点在多边形中的判定计算的，比如洪水泛滥时确定哪些位置是否被洪水淹没，因为洪水覆盖区域的多边形是动态变化的。

[0042] 此外，除存储基本网格结构外，本发明仅需要为每个网格中心点存储其是否‘奇异’的标志和‘内/外’属性，只需要2个比特位，因此空间需求很少，这也是有利于实践应用的。