複合多邊形內的點

Question

我已經看到很多點內多邊形的算法。 我的教訓至今都來自這個網站：http://alienryderflex.com/polygon/

最好的算法一般是這樣的：

var inside = false; 
for (int i = poly.Count - 1, j = 0; j < poly.Count; i = j++) 
{ 
    var p1 = poly.Vertices[i]; 
    var p2 = poly.Vertices[j]; 

    if ((p1.Y < testY != p2.Y < testY) && //at least one point is below the Y threshold and the other is above or equal 
     (p1.X >= testX || p2.X >= testX)) //optimisation: at least one point must be to the right of the test point 
    { 
     if (p1.X + (testY - p1.Y)/(p2.Y - p1.Y) * (p2.X - p1.X) > testX) 
      inside = !inside; 
    } 
} 

但複合多邊形段可以是直線或圓弧。圓弧段由正常的2個點和用於查找圓弧的中心和半徑的凸起定義。 2點用於查找弧的起點和終點角度。

使用測試點Y和Math.Asin((testY - arc.Center.Y)/arc.Radius)我可以找到測試線與圓相交的角度。當測試線與圓相交時，有2個交點。之後，我測試角度以瞭解交點是否在弧線上。

到目前爲止，我的結果還不錯，只是當測試點發生的時候與頂點完全相同的y。它將被計算爲2個相鄰的分段。對於一個正常的部分，這種情況下是通過避免如果(p1.Y < testY != p2.Y < testY)

我找不到的圓弧部分組成的配料多邊形任何類似的實現。有人曾經做過類似的事情或有任何暗示嗎？

Answer 1

這一行

p1.Y < testY != p2.Y < testY 

你只計算從接近底部的查詢線段（或穿過它）。這正是你需要爲弧線做的事情。

爲此，可能希望將弧分割爲單調部分（相對於y軸）。在你的例子中，較低的弧線已經是單調的了。上部弧線應分成兩部分（沿着垂直線穿過其中心）。然後，你必須爲每個分段minY和maxY並且可以應用上述公式：

minY < testY != maxY < testY 

或者，也可以檢查是否交點是在圓弧端（等於y座標），並評估如果電弧繼續向下基於角度和弧線方向。但取決於實施，這可能會有一些數值穩定性問題。第一個選項（分成單調部分）可能更容易實現。它推廣到其他原語。