邊界矩形碰撞測試？

Question

我有複雜的多邊形，我知道最小x，最小y，最大x和最大y。我也有另一個矩形，我知道左上角和右下角的頂點。知道這些信息，我怎麼知道這兩個邊框是否碰撞？謝謝

Answer 1

嘗試這樣：

typedef struct rect { 
    int top;  // maximum y-coord 
    int bottom; // minimum y-coord 
    int left; // minimum x-coord 
    int right; // maximum x-coord 
} rectangle; 

// Returns 1 if the point (x, y) lies within the rectangle, 0 otherwise 
int is_point_in_rectangle(rectangle r, int x, int y) { 
    if ((r.left <= x && r.right >= x) && 
     (r.bottom <= y && r.top >= y)) 
     return 1; 
    return 0; 
} 

// Returns 1 if the rectangles overlap, 0 otherwise 
int do_rectangles_intersect(rectangle a, rectangle b) { 
    if (is_point_in_rectangle(a, b.left , b.top ) || 
     is_point_in_rectangle(a, b.right, b.top ) || 
     is_point_in_rectangle(a, b.left , b.bottom) || 
     is_point_in_rectangle(a, b.right, b.bottom)) 
     return 1; 
    if (is_point_in_rectangle(b, a.left , a.top ) || 
     is_point_in_rectangle(b, a.right, a.top ) || 
     is_point_in_rectangle(b, a.left , a.bottom) || 
     is_point_in_rectangle(b, a.right, a.bottom)) 
     return 1; 
    return 0; 
} 

您可以爲任何多邊形做同樣的，只是遍歷所有的點，並呼籲is_point_in_rectangle他們。由於您只有複雜多邊形的邊界框，因此此方法可能會出現誤報（即，矩形位於複雜多邊形的邊界框內，但位於多邊形本身之外）。但是，這種限制適用於將複雜形狀簡化爲邊界框的任何方法。

Answer 2

如果區間[Ax1，Ax2]和[Bx1，Bx2]重疊和，區間[Ay1，Ay2]和[By1，By2]重疊，則矩形A和B發生碰撞。

Answer 3

我覺得下面的作品大多數的時代，但它肯定比邊界框檢查更準確，雖然比較複雜。看看以下問題：

Polygon in rectangle algorithm?

在那裏，您會看到找出一種算法，如果一個點是多邊形內。您可以將此測試應用於第一個poly w.r.t的每個點。第二個。然後是相反的。如果測試通過至少一次，就會發生碰撞。

Answer 4

創建矩形左右邊緣的x座標的排序數組。然後，使用「掃描線」通過矩形從左向右移動。保留一個二叉搜索樹，該樹包含與掃描線重疊的矩形的頂部和底部邊緣的y座標。對於數組的每個元素，檢查它是左邊還是右邊。如果是右邊緣，請從BST上取下相應的頂部和底部邊緣。如果它是左邊緣，則在BST中搜索與當前矩形重疊的矩形;如果有，返回重疊。然後，將矩形頂部和底部邊緣的y座標添加到BST。搜索需要O（n log n）時間，因爲需要O（n log n）時間對矩形進行排序，並且每次2n次迭代需要O（log n）時間 - 從谷歌搜索結果複製。