多邊形到多邊形碰撞檢測問題

Question

我一直在實施我的窄相位碰撞檢測的幾個問題。 Broadphase正在完美運作。

我有一組多邊形，它們的頂點順時針順序具有一個stl :: vector數組。每個週期，我檢查他們是否碰撞。

我從here使用我的觀點的數據結構借來以下點在多邊形測試和改變了它：

int InsidePolygon(std::vector <Point> poly, Point p) { 
    int i, j, c = 0; 
    int nvert = poly.size(); 

    for (i = 0, j = nvert-1; i < nvert; j = i++) { 

    if (((poly[i].y> p.y) != (poly[j].y> p.y)) && (p.x < (poly[j].x-poly[i].x) * (p.y-poly[i].y)/(poly[j].y-poly[i].y) + poly[i].x)) 
     c = !c; 

    } 
    return c; 
} 

我已經延長，爲包括PolygonPolygon功能，檢查所有1個多邊形兌點另一個，然後扭轉它來檢查其他方式。

int PolygonPolygon(std::vector <Point> polygon1, std::vector <Point> polygon2) { 

    for(int i=0; i<polygon1.size();i++) {  
    if(InsidePolygon(polygon2, polygon1[i])) { 
     return 1; 
    } 
    } 
    for(int j=0; j<polygon2.size();j++) {  
    if(InsidePolygon(polygon1, polygon2[j])) { 
     return 1; 
    } 
    } 

    return 0; 

} 

奇怪的是，我的PolygonPolygon函數總是返回1.所以，我有幾個問題：

1. 我有沒有什麼地方搞砸了的邏輯？我應該以不同的方式編寫我的PolygonPolygon函數嗎？

2. 對於PolygonPolygon測試是否有更好的方法，多邊形本身不能保證是凸的，這就是爲什麼我在多邊形方法中選擇點的原因。我也希望能夠確定哪一點最終會發生碰撞，如果我能通過這一點。

3. 我是否應該按照特定的順序來呈現我的觀點以進行InsidePolygon測試？

Answer 1

感謝您的幫助！但我已經設法自行解決。

將頂點轉換爲世界空間並旋轉它們的重要性不應該被忽視，特別是如果你碰撞它們。

Answer 2

您可能需要考慮trying to draw a line between polygons作爲替代碰撞檢測方法。

[編輯]哎呀，我錯過了你有非凸多邊形中有太多的事實。也許「Determining if a point lies on the interior of a polygon」會更好？要麼你或者可以首先將你的非凸多邊形分解成凸多邊形。

此外，StackOverflow上至少有one similar question。