技术领域

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