保證多邊形法線的向外方向

我想寫一個Java遊戲中使用分離軸定理進行碰撞檢測的2D遊戲。爲了解決兩個多邊形之間的碰撞，我需要知道碰撞的最小平移矢量，並且我需要知道它相對於多邊形指向哪個方向（以便我可以給一個多邊形沿該方向施加一個懲罰力，另一個反方向的懲罰力量）。作爲參考，我試圖執行算法here。保證多邊形法線的向外方向

我想保證，如果我打電話給我的碰撞檢測功能collide(Polygon polygon1, Polygon polygon2)它檢測到衝突，返回的MTV將始終指向遠離polygon1，向 polygon2。爲了做到這一點，我需要保證我生成的分離軸，即多邊形邊的法線，總是指向產生它們的多邊形。（這樣，我知道在將它用作MTV之前，從多邊形2中取消任何軸）。

不幸的是，看起來多邊形邊緣的法線I是否指向多邊形的內部或外部取決於多邊形的點是以順時針還是逆時針順序聲明的。我使用here所描述的算法來生成法線，並且假設我選擇(x, y) => (y, -x)作爲「垂直」方法，如果按順時針順序遍歷頂點，則所得法線將僅指向遠離多邊形。

鑑於我不能強制客戶端按順時針順序聲明多邊形的點（我使用java.awt.Polygon，它只是公開兩個數組的x和y座標），是否有數學如何保證我生成的法向量的方向朝向多邊形的外部？我對向量數學不太擅長，所以可能有一個明顯的解決方案來解決這個問題。關於SAT的大多數Internet資源只是假定您可以始終按順時針順序遍歷多邊形的頂點。

來源

2012-07-18 Edward

我終於明白了，但發佈的一個答案不是完整的解決方案，所以我不會接受它。我能夠確定使用this SO answer描述的基本算法多邊形的排序，這是（在大衛·諾曼的鏈接也描述不太清楚）：

for each edge in polygon: 
    sum += (x2 - x1) * (y2 + y1)

然而，有哪個沒有回答這些問題提到一個重要的警告。通常情況下，如果此和爲正，則可以決定多邊形的頂點爲順時針，如果和爲負，則可以逆時針旋轉。但的比較是倒置的在Java的2D圖形系統中，而實際上在很多圖形系統中，因爲的正y軸指向向下。因此，在一個正常的，數學座標系，可以說

if sum > 0 then polygon is clockwise

在圖形但座標系的倒Y軸，它實際上是

if sum < 0 then polygon is clockwise

我的實際代碼，使用Java的多邊形，看起來像這樣：

//First, find the normals as if the polygon was clockwise 

int sum = 0; 
for(int i = 0; i < polygon.npoints; i++) { 
    int nextI = (i + 1 == polygon.npoints ? 0 : i + 1); 
    sum += (polygon.xpoints[nextI] - polygon.xpoints[i]) * 
     (polygon.ypoints[nextI] + polygon.ypoints[i]); 
} 

if(sum > 0) { 
    //reverse all the normals (multiply them by -1) 
}

來源

2012-07-22 00:08:27 Edward

您可以使用例如this問題的答案來計算每個多邊形排序的方向，然後如果兩個多邊形的順序不同，則將法線乘以-1。

您還可以檢查傳遞給算法的每個多邊形，看看它是否被錯誤地排序，再次使用上述算法，並在必要時顛倒頂點順序。

請注意，在計算頂點順序時，一些算法將適用於所有多邊形，一些適用於凸多邊形。

來源

2012-07-18 19:40:59

該鏈接不再起作用。錯誤403. – 2012-11-21 15:56:04

我修復了鏈接 – 2012-11-21 22:16:25

保證多邊形法線的向外方向

回答

相關問題