多边形内的点
在计算几何中，多边形中的点（point-in-polygon, PIP）问题是指，查询输入的点是位于平面中的多边形的内部、外部还是边界上。它是点定位问题的一个特例，可应用于处理几何数据领域，例如计算机图形学、计算机视觉、地理信息系统(GIS)、运动规划和计算机辅助设计(CAD)。
一份计算机图形学中关于该问题的早期说明表示，早在 1974 年就有了两种常用求解方法——光线投射和角度求和[1]。
在光线追踪新闻的一期 [2]中，可以找到计算机图形学专家试图追溯问题的历史和解决问题的一些技巧。
射线投射算法[编辑]
这是一种查询点是在简单多边形内部或是外部的一种简单方法。从该点开始并沿任何固定方向发射射线，检查该射线与多边形的边相交的次数。如果该点位于多边形的外部，则射线将与多边形的边相交偶数次。如果该点位于多边形的内部，则它将与多边形的边相交奇数次。多边形边上的点的查询结果取决于射线相交算法的实现。
该算法有时也称为交叉数算法（Cross Number Algorithm）或奇偶规则算法（Even-odd Rule Algorithm），该算法早在1962年问世[3]。该算法基于一个简单的观察结论——如果一个点沿着一条射线从无限远移动到探测点，并且如果它穿过多边形的边界，可能多次，那么它交替地从外到内，然后从内到内到外面等结果，在每两次“过境”之后，移动点就会向外移动。可以使用约旦曲线定理从数学上证明这一观察结果。
精度有限的情况[编辑]
如果在有限算术精度的计算机上实现该算法，当点非常靠近多边形的边时，舍入误差可能导致错误的结果。对于某些应用程序，如电子游戏或其他娱乐产品，这不是一个大问题，因为它们通常倾向于选择速度而非精度。然而，对于形式上正确的计算机程序，必须引入数值公差ε 并在线测试P （点）是否位于L （线）的 ε 范围内，在这种情况下算法应停止并报告“ P过于接近边界。”
射线投射算法的大多数实现会依次连续检查射线与多边形所有边的交点。在这种情况下，必须解决以下问题。如果光线恰好通过多边形的一个顶点，那么它将在它们的相交点处与 2 个线段相交。虽然对于示例中最顶部的顶点或 4 和 5 交叉点之间的顶点的这种办法是有效的，但如示例所示的最右侧顶点，此时我们需要记录一次相交来获得正确结果。某个边与射线重合就会出现类似的问题。这个问题的解决方案如下：如果交点是待测多边形某个边上的一个顶点，则只有当该边的另一个顶点位于射线下方时，交点才算在内。这实际上等同于将与射线相交的顶点视为略高于射线。简而言之，就是规定射线经过的点同在射线一侧，随后进行跨立实验即可。
再次说明，射线穿过顶点的情况可能会在有限精度算法中引起数值问题：对于与同一顶点相邻的两条边，直接计算与射线的相交情况可能无法在这两种情况下给出顶点。如果多边形由其顶点构成，则通过在实际求交之前检查射线的 y 坐标与待测多边形边的端点来解决该问题。在其它情况下，当根据其它类型的数据计算多边形边时，必须通过其他技巧来提高算法的数值鲁棒性。
回转数算法[编辑]
这是另一种用于检查点是否在多边形内部的算法。这个算法计算给定点相对于多边形的回转数。如果回转数不为零，则该点位于多边形内。该算法有时也称为非零规则算法。
计算回转数的一种方法是将多边形每条边的对角相加[4]，换种就是把该点与多边形的所有顶点连接起来，计算相邻两边夹角的和，但这些角度是有方向性的。 然而，这涉及代价高昂的反三角函数，与射线投射算法相比，这导致该算法通常情况下的性能效率较低。幸运的是，我们不需要计算这些反三角函数。由于结果（即所有角度的总和）只能是 0 或 （或的倍数 )， 因此仅需跟踪多边形绕测试点旋转时穿过哪些象限[5]，这使得回转数算法的速度与计算边的相交次数相当。
Dan Sunday 在 2001 年发明了一种改进的计算回转数的算法[6]。它在计算中不使用角度，也不使用任何三角函数，其功能与上述射线投射算法完全相同。 Sunday 的算法通过考虑从被查询点发出的无限水平射线来工作。每当该射线穿过多边形的一条边时，会使用Juan Pineda的边界穿越算法 (1988) [7]来确定该相交情况会如何影响回转数。正如Sunday所描述的，如果边穿过射线时是"向上"的方向，回转数将增加；如果边穿过射线时是"向下"的方向，回转数将减少。Sunday的算法对于非简单多边形可以给出正确的答案，而边界穿越算法在这种情况下会给出错误结果。 [6]
实现[编辑]
SVG[编辑]
类似的方法在SVG中用于定义用颜色填充各种形状的方法，例如路径、折线、多边形、文本等 [8]。 这个填充算法受“填充规则”属性的影响。该值可以是nonzero或evenodd 。例如，在一个非凸正五边形曲面中，其中心有个“孔”（可见背景）具有evenodd ，并且没有nonzero属性。 [9]
对于简单的多边形，该算法将给出相同的结果。然而，对于复杂的多边形，算法可能会针对多边形与自身相交的区域中的点给出不同的结果，多边形在这些区域中没有明确定义内部和外部。使用奇偶规则的一种解决方案是在相交检查之前将（复杂的）多边形转换为更简单的偶奇等价的多边形[10]。 然而，该转换非常昂贵。使用快速非零回转数算法的成本更低，即使多边形自身重叠，该算法也能给出正确的结果。
多边形查询中的点[编辑]
多边形中的点问题可以考虑一般的重复几何查询设置：给定单个多边形和一系列查询点，快速求出每个查询点的位置结果。显然，平面点定位的任何通用方法都可以用。对于一些特殊的多边形，可以使用更简单的解决方案。
特例[编辑]
对于单调多边形、星形多边形、凸多边形和三角形，可以使用更简单的算法。
使用重心坐标系、参数方程或点积可以很容易地求解三角形情况。 [11]点积方法自然地扩展到任何凸多边形。
参考[编辑]
- ^ Ivan Sutherland et al.,"A Characterization of Ten Hidden-Surface Algorithms" 1974, ACM Computing Surveys vol. 6 no. 1.
- ^ "Point in Polygon, One More Time..." 互联网档案馆的存檔，存档日期2018-05-24., Ray Tracing News, vol. 3 no. 4, October 1, 1990.
- ^ Shimrat, M., "Algorithm 112: Position of point relative to polygon" 1962, Communications of the ACM Volume 5 Issue 8, Aug. 1962. https://dl.acm.org/doi/10.1145/368637.368653 （页面存档备份，存于互联网档案馆）
- ^ Hormann, K.; Agathos, A. The point in polygon problem for arbitrary polygons. Computational Geometry. 2001, 20 (3): 131. doi:10.1016/S0925-7721(01)00012-8
.
- ^ Weiler, Kevin, An Incremental Angle Point in Polygon Test, Heckbert, Paul S. (编), Graphics Gems IV, San Diego, CA, USA: Academic Press Professional, Inc.: 16–23, 1994, ISBN 0-12-336155-9
- ^ 6.0 6.1 Sunday, Dan. Inclusion of a Point in a Polygon. 2001. （原始内容存档于26 January 2013）.
- ^ Pineda, Juan. A Parallel Algorithm for Polygon Rasterization (PDF). SIGGRAPH'88. Computer Graphics 22 (Atlanta). August 1988 [8 August 2021]. （原始内容存档 (PDF)于2023-05-11）. 参数
|journal=与模板{{cite conference}}不匹配（建议改用{{cite journal}}或|book-title=） (帮助) - ^ Painting: Filling, Stroking, Colors and Paint Servers – SVG Tiny 1.2. www.w3.org. [2021-07-24]. （原始内容存档于2023-05-15）.
- ^ Painting: Filling, Stroking, Colors and Paint Servers – SVG Tiny 1.2. www.w3.org. [2021-07-24]. （原始内容存档于2023-05-15）.
- ^ Michael Galetzka, Patrick Glauner. A Simple and Correct Even-Odd Algorithm for the Point-in-Polygon Problem for Complex Polygons. Proceedings of the 12th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISIGRAPP 2017), Volume 1: GRAPP. 2017.
- ^ Accurate point in triangle test （页面存档备份，存于互联网档案馆） "...the most famous methods to solve it"
See also[编辑]
- Java 拓扑套件 (JTS)
- 讨论： http://www.ics.uci.edu/~eppstein/161/960307.html （页面存档备份，存于互联网档案馆）
- 绕组数与交叉数方法： http://geomalgorithms.com/a03-_inclusion.html （页面存档备份，存于互联网档案馆）