多邊形內的點
在計算幾何中，多邊形中的點（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 （頁面存檔備份，存於互聯網檔案館）