查看“︁多边形内的点”︁的源代码


[[File:Simple_polygon.svg|right|thumb|示例：一个[[简单多边形]]]]
在[[计算几何]]中，'''多边形中的点'''（point-in-polygon, '''PIP'''）问题是指，查询输入的点是位于平面中的[[多边形]]的内部、外部还是边界上。它是点定位问题的一个特例，可应用于处理几何数据领域，例如[[计算机图形|计算机图形学]]、[[计算机视觉]]、[[地理信息系统]](GIS)、[[运动规划]]和[[计算机辅助设计]](CAD)。

一份计算机图形学中关于该问题的早期说明表示，早在 1974 年就有了两种常用求解方法——光线投射和角度求和<ref>[[Ivan Sutherland]] et al.,"A Characterization of Ten Hidden-Surface Algorithms" 1974, ''[[ACM Computing Surveys]]'' vol. 6 no. 1.</ref>。

在''光线追踪新闻''的一期 <ref>[http://jedi.ks.uiuc.edu/~johns/raytracer/rtn/rtnv3n4.html#art22 "Point in Polygon, One More Time..."] {{Webarchive|url=https://web.archive.org/web/20180524215455/http://jedi.ks.uiuc.edu/~johns/raytracer/rtn/rtnv3n4.html#art22|date=2018-05-24}}, ''[[Ray Tracing News]]'', vol. 3 no. 4, October 1, 1990.</ref>中，可以找到计算机图形学专家试图追溯问题的历史和解决问题的一些技巧。

== 射线投射算法 ==
[[File:RecursiveEvenPolygon.svg|right|thumb|从多边形外部到任意一点的射线的交点数；如果是奇数，则表明该点位于多边形内。如果是偶数，则该点位于多边形之外；该方法也适用于三维情况。]]
这是一种查询点是在[[簡單多邊形|简单多边形]]内部或是外部的一种简单方法。从该点开始并沿任何固定方向发射[[直线|射线]]，检查该射线与多边形的边相交的次数。如果该点位于多边形的外部，则射线将与多边形的边相交[[奇偶性 (数学)|偶数次]]。如果该点位于多边形的内部，则它将与多边形的边相交[[奇偶性 (数学)|奇数次]]。多边形边上的点的查询结果取决于射线相交算法的实现。

该算法有时也称为交叉数算法（Cross Number Algorithm）或奇偶规则算法（Even-odd Rule Algorithm），该算法早在1962年问世<ref>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 {{Wayback|url=https://dl.acm.org/doi/10.1145/368637.368653 |date=20230613093628 }}</ref>。该算法基于一个简单的观察结论——如果一个点沿着一条射线从无限远移动到探测点，并且如果它穿过多边形的边界，可能多次，那么它交替地从外到内，然后从内到内到外面等结果，在每两次“过境”之后，移动点就会向外移动。可以使用[[若尔当曲线定理|约旦曲线定理]]从数学上证明这一观察结果。

=== 精度有限的情况 ===
如果在[[浮点数|有限算术精度]]的计算机上实现该算法，当点非常靠近多边形的边时，舍入误差可能导致错误的结果。对于某些应用程序，如电子游戏或其他娱乐产品，这不是一个大问题，因为它们通常倾向于选择速度而非精度。然而，对于形式上正确的[[计算机程序]]，必须引入[[数值分析|数值]][[公差 (工程学)|公差]]ε 并[[在线算法|在线]]测试''P'' （点）是否位于''L'' （线）的 ε 范围内，在这种情况下算法应停止并报告“ ''P''过于接近边界。”

射线投射算法的大多数实现会依次连续检查射线与多边形所有边的交点。在这种情况下，必须解决以下问题。如果光线恰好通过多边形的一个[[頂點 (幾何)|顶点]]，那么它将在它们的相交点处与 2 个线段相交。虽然对于示例中最顶部的顶点或 4 和 5 交叉点之间的顶点的这种办法是有效的，但如示例所示的最右侧顶点，此时我们需要记录一次相交来获得正确结果。某个边与射线重合就会出现类似的问题。这个问题的解决方案如下：如果交点是待测多边形某个边上的一个顶点，则只有当该边的另一个顶点位于射线下方时，交点才算在内。这实际上等同于将与射线''相交的''顶点''视为''略高于射线。简而言之，就是规定射线经过的点同在射线一侧，随后进行[[跨立实验]]即可。

再次说明，射线穿过顶点的情况可能会在[[浮点数|有限精度算法]]中引起数值问题：对于与同一顶点相邻的两条边，直接计算与射线的相交情况可能无法在这两种情况下给出顶点。如果多边形由其顶点构成，则通过在实际求交之前检查射线的 y 坐标与待测多边形边的端点来解决该问题。在其它情况下，当根据其它类型的数据计算多边形边时，必须通过其他技巧来提高算法的[[健壮性 (计算机科学)|数值鲁棒性]]。

== 回转数算法 ==
这是另一种用于检查点是否在多边形内部的算法。这个算法计算给定点相对于多边形的[[卷绕数|回转数]]。如果回转数不为零，则该点位于多边形内。该算法有时也称为''非零规则算法''。

计算回转数的一种方法是将多边形每条边的[[对角]]相加<ref name="Hormann">{{Cite journal |last=Hormann |first=K. |last2=Agathos |first2=A. |year=2001 |title=The point in polygon problem for arbitrary polygons |journal=Computational Geometry |volume=20 |issue=3 |page=131 |doi=10.1016/S0925-7721(01)00012-8 |doi-access=free}}</ref>，换种就是把该点与多边形的所有顶点连接起来，计算相邻两边夹角的和，但这些角度是有方向性的。 然而，这涉及代价高昂[[反三角函数|的反三角函数]]，与射线投射算法相比，这导致该算法通常情况下的性能效率较低。幸运的是，我们不需要计算这些反三角函数。由于结果（即所有角度的总和）只能是 0 或<math>2\pi</math> （或<math>2\pi</math>的倍数 )， 因此仅需跟踪多边形绕测试点旋转时穿过哪些象限<ref>{{citation|last=Weiler|first=Kevin|editor-last=Heckbert|editor-first=Paul S.|contribution=An Incremental Angle Point in Polygon Test|isbn=0-12-336155-9|location=San Diego, CA, USA|pages=16–23|publisher=Academic Press Professional, Inc.|title=Graphics Gems IV|year=1994|url=https://archive.org/details/isbn_9780123361554/page/16}}</ref>，这使得回转数算法的速度与计算边的相交次数相当。
[[File:Winding_number_algorithm_example.svg|thumb| Dan Sunday 的[[卷绕数|绕数]]算法的可视化示例。回转数为 0 表示该点在多边形之外；其他值表示该点在多边形内部]]
Dan Sunday 在 2001 年发明了一种改进的计算回转数的算法<ref name="sunday">{{Cite web|last=Sunday|first=Dan|year=2001|title=Inclusion of a Point in a Polygon|url=http://geomalgorithms.com/a03-_inclusion.html|url-status=dead|archive-url=https://web.archive.org/web/20130126163405/http://geomalgorithms.com/a03-_inclusion.html|archive-date=26 January 2013}}</ref>。它在计算中不使用角度，也不使用任何三角函数，其功能与上述射线投射算法完全相同。 Sunday 的算法通过考虑从被查询点发出的无限水平射线来工作。每当该射线穿过多边形的一条边时，会使用Juan Pineda的边界穿越算法 (1988) <ref>{{Cite conference |last=Pineda |first=Juan |date=August 1988 |title=A Parallel Algorithm for Polygon Rasterization |url=https://www.cs.drexel.edu/~david/Classes/Papers/comp175-06-pineda.pdf |conference=[[SIGGRAPH]]'88 |location=[[Atlanta]] |volume=22 |access-date=8 August 2021 |journal=Computer Graphics |archive-date=2023-05-11 |archive-url=https://web.archive.org/web/20230511061223/https://www.cs.drexel.edu/~david/Classes/Papers/comp175-06-pineda.pdf |dead-url=no }}</ref>来确定该相交情况会如何影响回转数。正如Sunday所描述的，如果边穿过射线时是"向上"的方向，回转数将增加；如果边穿过射线时是"向下"的方向，回转数将减少。Sunday的算法对于非简单多边形可以给出正确的答案，而边界穿越算法在这种情况下会给出错误结果。 <ref name="sunday" />

== 实现 ==

=== SVG ===
类似的方法在[[可縮放向量圖形|SVG]]中用于定义用颜色填充各种形状的方法，例如路径、折线、多边形、文本等 <ref>{{Cite web|title=Painting: Filling, Stroking, Colors and Paint Servers – SVG Tiny 1.2|url=https://www.w3.org/TR/2008/REC-SVGTiny12-20081222/painting.html#FillProperties|access-date=2021-07-24|website=www.w3.org|archive-date=2023-05-15|archive-url=https://web.archive.org/web/20230515171421/https://www.w3.org/TR/2008/REC-SVGTiny12-20081222/painting.html#FillProperties|dead-url=no}}</ref>。 这个填充算法受“填充规则”属性的影响。该值可以是{{Code|nonzero}}或{{Code|evenodd}} 。例如，在一个[[凸多胞形|非凸]]正五边形曲面中，其中心有个“孔”（可见背景）具有{{Code|evenodd}} ，并且没有{{Code|nonzero}}属性。 <ref>{{Cite web|title=Painting: Filling, Stroking, Colors and Paint Servers – SVG Tiny 1.2|url=https://www.w3.org/TR/2008/REC-SVGTiny12-20081222/painting.html#FillProperties|access-date=2021-07-24|website=www.w3.org|archive-date=2023-05-15|archive-url=https://web.archive.org/web/20230515171421/https://www.w3.org/TR/2008/REC-SVGTiny12-20081222/painting.html#FillProperties|dead-url=no}}</ref>

对于[[簡單多邊形|简单的多边形]]，该算法将给出相同的结果。然而，对于复杂的多边形，算法可能会针对多边形与自身相交的区域中的点给出不同的结果，多边形在这些区域中没有明确定义内部和外部。使用奇偶规则的一种解决方案是在相交检查之前将（复杂的）多边形转换为更简单的偶奇等价的多边形<ref>{{Cite conference |last=Michael Galetzka, Patrick Glauner |year=2017 |title=A Simple and Correct Even-Odd Algorithm for the Point-in-Polygon Problem for Complex Polygons |conference=Proceedings of the 12th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications ([[VISIGRAPP]] 2017), Volume 1: GRAPP}}</ref>。 然而，该转换非常昂贵。使用快速非零回转数算法的成本更低，即使多边形自身重叠，该算法也能给出正确的结果。

== 多边形查询中的点 ==
多边形中的点问题可以考虑一般的重复[[Geometric query|几何查询]]设置：给定单个多边形和一系列查询点，快速求出每个查询点的位置结果。显然，平面点定位的任何通用方法都可以用。对于一些特殊的多边形，可以使用更简单的解决方案。

=== 特例 ===
对于单调多边形、星形多边形、[[凸多边形]]和[[三角形]]，可以使用更简单的算法。

使用[[重心坐标|重心坐标系]]、[[參數方程|参数方程]]或[[点积]]可以很容易地求解三角形情况。 <ref>[https://totologic.blogspot.com/2014/01/accurate-point-in-triangle-test.html Accurate point in triangle test] {{Wayback|url=https://totologic.blogspot.com/2014/01/accurate-point-in-triangle-test.html |date=20230217004853 }} "''...the most famous methods to solve it''"</ref>点积方法自然地扩展到任何凸多边形。

== 参考 ==
{{Reflist}}

== See also ==

* Java 拓扑套件 (JTS)
* 讨论： http://www.ics.uci.edu/~eppstein/161/960307.html {{Wayback|url=http://www.ics.uci.edu/~eppstein/161/960307.html |date=20230515171413 }}
* 绕组数与交叉数方法： http://geomalgorithms.com/a03-_inclusion.html {{Wayback|url=http://geomalgorithms.com/a03-_inclusion.html |date=20130126163405 }}
[[Category:点]]
[[Category:几何算法]]
[[Category:计算几何]]
[[Category:多边形]]