分離軸定理和Python

這就是我目前正在做的：分離軸定理和Python

創建4個垂直於2個矩形的4個邊的軸。由於它們是矩形，我不需要爲每條邊生成一個軸（正常）。

我然後循環我的4個軸。

所以對於每個軸：我得到矩形的每個角落到軸上的投影。有2個列表（數組）包含這些投影。每個矩形一個。然後我得到每個投影和軸的點積。這會返回一個標量值，可用於確定最小值和最大值。

現在2個列表包含標量而不是向量。我對列表進行排序，以便輕鬆選擇最小值和最大值。如果框B的最小值> =框A的最大值或框B的最大值B < =框A的最小值，那麼在該軸上不存在碰撞並且沒有碰撞。

此時函數完成並循環中斷。

如果這些條件都從未見過的所有的軸，然後我們有一個碰撞

我希望這是做它的正確途徑。

的Python代碼本身可以在這裏http://pastebin.com/vNFP3mAb

還發現： http://www.gamedev.net/page/reference/index.html/_/reference/programming/game-programming/collision-detection/2d-rotated-rectangle-collision-r2604

我有問題是，上面的代碼不起作用。即使在沒有碰撞的情況下，它也會始終檢測到碰撞。我輸入的內容正是代碼的功能。如果我錯過了任何步驟，或者只是不瞭解SAT如何工作，請告訴我。

來源

2011-05-16 Bruk Habtu

這是什麼問題？ – 2011-05-16 06:02:16

對於更一般的凸多邊形，我們會考慮與兩個多邊形的邊平行*的潛在分離軸，但由於您具體處理矩形，所以在這種情況下要求垂直於（或正常）軸以邊緣。 – hardmath 2011-05-16 09:26:49

我遇到的問題是上面的代碼不起作用。即使在沒有碰撞的情況下，它也會始終檢測到碰撞。對不起，不清楚。我將編輯我寫的內容，以便更清楚。 – 2011-05-16 17:15:07

我看到兩件事情是錯誤的。首先，投影應該只是頂點與軸的點積。你所做的事情太複雜了。其次，你得到你的軸的方式是不正確的。你寫：

Axis1 = [ -(A_TR[0] - A_TL[0]), 
      A_TR[1] - A_TL[1] ]

它應該閱讀：

Axis1 = [ -(A_TR[1] - A_TL[1]), 
      A_TR[0] - A_TL[0] ]

不同的是座標並給你一個載體，但要獲得垂直需要調換x和y的值和否定的一個他們。

希望有所幫助。

編輯發現了另一個錯誤

在此代碼：

if not (B_Scalars[0] <= A_Scalars[3] or B_Scalars[3] >= A_Scalars[0]): 
      #no overlap so no collision 
      return 0

這應該閱讀：

if not (B_Scalars[3] <= A_Scalars[0] or A_Scalars[3] <= B_Scalars[0]):

排序給你一個列表值的增加。因此[1,2,3,4]和[10,11,12,13]不重疊，因爲後者的最小值大於前者的最大值。第二個比較是當輸入集被交換時。

來源

2011-05-16 19:22:11 phkahler

感謝迴應phkahler。一旦我將投影到這個軸上的角落，找到在任一方向上最遠的兩個角（每個矩形）就是問題了嗎？這可以通過測量2個座標之間的長度來完成。我想我明白這是如何工作的。當我得到它的工作時，我會發布我的解決方案。 – 2011-05-16 20:47:45

沿着「方式太複雜」的路線行事，我對錶示矩形的方式感到不舒服。沒有明確表示矩形的旋轉角度。相反，表示法似乎是一般四邊形的表示法，即四個簡單標記爲「左上」，「右上」等的點。由此產生的八個座標過於籠統，因此您必須依靠填充它們的代碼讓他們一致。更嚴格的表示（中心，寬度，高度，旋轉角度）可以強制定義旋轉的矩形。 – hardmath 2011-05-17 01:51:56

@hardmath：是的我同意這是一個普通的四邊形，但是他的SAT的實現也計算了所有4邊的軸，所以只要它們是凸的就應該工作。 – phkahler 2011-05-17 18:41:28

一般來說，需要執行問題中概述的步驟以確定矩形是否「碰撞」（相交），並注意到OP會盡快斷開（以非交叉的結論）作爲分離軸被找到。

在提供早期退出機會的意義上，有幾種簡單的「優化」方法。這些的實際價值取決於正在檢查的矩形的分佈，但兩者都很容易併入現有框架。

（1）外接圓檢查

一種快速的方法來證明非交叉是通過示出兩個矩形的邊界圈不相交。矩形的邊界圓分享其中心，任一對角線的中點，並且其直徑等於任一對角線的長度。如果兩個中心之間的距離超過兩個圓的半徑之和，則這些圓不交叉。因此矩形也不能相交。如果目的是要找到一個分離軸，我們還沒有完成。但是，如果我們只想知道矩形是否「碰撞」，這可以提前退出。

（2）的另一

平行於另一個矩形的邊緣一個矩形的上軸的頂點的投影內的一個矩形的頂點提供足夠的信息來檢測何時該頂點是其他矩形內。當後一個矩形已經平移並且未旋轉到原點時（這些邊與普通軸平行），此檢查特別容易。如果碰巧一個矩形的頂點在另一個矩形的內部，矩形顯然相交。當然，這是一個交叉點的充分條件，而不是必要條件。但它允許提前結束交集（並且當然沒有找到分離軸，因爲都不存在）。

來源

2011-05-16 11:11:32 hardmath

分離軸定理和Python

回答

相關問題