Autor Wątek: Kolizja dwóch obróconych prostokątów  (Przeczytany 782 razy)

Offline JasonVoorhees

  • Użytkownik
    • FotoGry

# Listopad 11, 2010, 15:44:16
Wykrywanie kolizji dwóch obróconych prostokątów zaimplementowane w Python'ie według http://www.gamedev.net/reference/articles/article2604.asp
Może się komuś przyda bo szukając rozwiązania tego problemu ten artykuł był jednym z nielicznych. Do funkcji przekazujemy współrzędne czterech punktów każdego z dwóch prostokątów w dowolnej kolejności. Dla moich danych testowych (nie jest ich zbyt wiele) ten sposób działa poprawnie. Jeśli wykryłeś błędy w implementacji (nie działa dla jakiegoś przypadku) to pisz w tym temacie.

def reorganize_points(rect): # cztery punkty w kolejnosci: gorny lewy, gorny prawy, dolny lewy, dolny prawy
rect.sort(cmp=lambda x,y: cmp(y[1],x[1]))
for i in [0,2]:
if rect[i][0]>rect[i+1][0]:
tmp=rect[i+1]
rect[i+1]=rect[i]
rect[i]=tmp


def check_collision(A,B):
#Setting Up
reorganize_points(A)
reorganize_points(B)
#Step 1 okreslenie osi
Axis=[]
Axis.append([A[1][0] - A[0][0],A[1][1] - A[0][1]])
Axis.append([A[1][0] - A[3][0],A[1][1] - A[3][1]])
Axis.append([B[0][0] - B[2][0],B[0][1] - B[2][1]])
Axis.append([B[0][0] - B[1][0],B[0][1] - B[1][1]])
for axis in Axis:
scalarsA=[]
scalarsB=[]
for point in A:
#Step 2 projekcja wektorow reprezentujacych cztery katy kazdego prostokata na kazdej osi
tmp=(point[0]*axis[0]+point[1]*axis[1])/(axis[0]**2+axis[1]**2)
x=axis[0]*tmp
y=axis[1]*tmp
#Step 3 obliczanie wartosci skalarnej
scalarsA.append(x*axis[0]+y*axis[1])
for point in B:
#Step 2 projekcja wektorow reprezentujacych cztery katy kazdego prostokata na kazdej osi
tmp=(point[0]*axis[0]+point[1]*axis[1])/(axis[0]**2+axis[1]**2)
x=axis[0]*tmp
y=axis[1]*tmp
#Step 3 obliczanie wartosci skalarnej
scalarsB.append(x*axis[0]+y*axis[1])
#Step 4 sprawdzenie maksymalnej i minimalnej wartosci skalarnej
maxA=max(scalarsA)
minA=min(scalarsA)
maxB=max(scalarsB)
minB=min(scalarsB)
if minB>maxA or maxB<minA:
return False
return True

test_rect1=[[-4.0,-2.5],[-3.0,-1.5],[-3.0,-3.5],[-2,-2.5]]
test_rect2=[[-2.5,-2.5],[-1.5,-3.5],[-0.5,-0.5],[0.5,-1.5]]
test_rect3=[[-3.0,-1.4],[-2.25,-2.0],[-2.0,-0.5],[-1.25,-1.25]]
test_rect4=[[-1.0,0.0],[-1.5,0.5],[-1.5,-0.5],[-2.0,0.0]]
test_rect5=[[0.75,-2.0],[1.5,-1.0],[1.0,-0.5],[0.5,-1.5]]
print check_collision(test_rect4,test_rect5)
« Ostatnia zmiana: Listopad 12, 2010, 04:26:44 wysłana przez JasonVoorhees »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych