Po pierwsze, w przypadku prostokątów wyrównanych do osi odpowiedź Kevina Reida jest najlepsza, a algorytm najszybszy.
Po drugie, dla prostych kształtów użyj prędkości względnych (jak pokazano poniżej) i twierdzenia o osi oddzielającej do wykrywania kolizji. To będzie powiedzieć, czy kolizja dzieje się w przypadku ruchu liniowego (bez rotacji). A jeśli występuje rotacja, potrzebujesz krótkiego czasu, aby był precyzyjny. Teraz, aby odpowiedzieć na pytanie:
Jak stwierdzić w ogólnym przypadku, czy przecinają się dwa wypukłe kształty?
Dam ci algorytm, który działa dla wszystkich wypukłych kształtów, a nie tylko sześciokątów.
Załóżmy, że X i Y są dwoma wypukłymi kształtami. Przecinają się wtedy i tylko wtedy, gdy mają wspólny punkt, tj. Istnieje punkt x ∈ X i punkt y ∈ Y taki, że x = y . Jeśli uważasz, że przestrzeń jest przestrzenią wektorową, oznacza to powiedzenie x - y = 0 . A teraz dochodzimy do tego biznesu Minkowskiego:
Suma Minkowskiego z X i Y jest zbiorem wszystkich x + y dla x ∈ X i Y ∈ Y .
Przykład dla X i Y
X, Y i ich suma Minkowskiego, X + Y
Załóżmy, że (-Y) jest zbiorem wszystkich -y dla y ∈ Y , a następnie biorąc pod uwagę poprzedni akapit, X i Y przecinają się tylko wtedy, gdy X + (-Y) zawiera 0 , to znaczy początek .
Uwaga boczna: dlaczego piszę X + (-Y) zamiast X-Y ? Cóż, ponieważ w matematyce istnieje operacja zwana różnicą Minkowskiego A i B, która jest czasami zapisywana jako X - Y, ale nie ma nic wspólnego z zestawem wszystkich x - y dla x ∈ X i y ∈ Y (prawdziwy Minkowski różnica jest nieco bardziej złożona).
Chcielibyśmy zatem obliczyć sumę Minkowskiego X i -Y i sprawdzić, czy zawiera ona pochodzenie. Początek nie jest szczególny w porównaniu z żadnym innym punktem, więc aby ustalić, czy początek znajduje się w określonej domenie, używamy algorytmu, który mógłby powiedzieć nam, czy dany punkt należy do tej domeny.
Suma Minkowskiego X i Y ma fajną właściwość, to znaczy, że jeśli X i Y są wypukłe, to X + Y też jest. Ustalenie, czy punkt należy do zbioru wypukłego, jest znacznie łatwiejsze, niż gdyby ten zbiór nie był (jak wiadomo) wypukły.
Nie możemy obliczyć wszystkich x - y dla x ∈ X i y ∈ Y, ponieważ istnieje nieskończoność takich punktów x i y , więc mam nadzieję, że ponieważ X , Y i X + Y są wypukłe, możemy po prostu użyć „najbardziej oddalone” punkty definiujące kształty X i Y , które są ich wierzchołkami, a my otrzymamy najbardziej zewnętrzne punkty X + Y i jeszcze więcej.
Te dodatkowe punkty są „otoczone” najbardziej zewnętrznymi punktami X + Y , aby nie przyczyniły się do zdefiniowania nowo uzyskanego kształtu wypukłego. Mówimy, że nie definiują „ wypukłego kadłuba ” zbioru punktów. Więc to, co robimy, polega na tym, że pozbywamy się ich w ramach przygotowań do ostatecznego algorytmu, który mówi nam, czy początek znajduje się w wypukłym kadłubie.
Wypukły kadłub X + Y. Usunęliśmy „wewnętrzne” wierzchołki.
Dlatego otrzymujemy
Pierwszy naiwny algorytm
boolean intersect(Shape X, Shape Y) {
SetOfVertices minkowski = new SetOfVertices();
for (Vertice x in X) {
for (Vertice y in Y) {
minkowski.addVertice(x-y);
}
}
return contains(convexHull(minkowski), Vector2D(0,0));
}
Pętle mają oczywiście złożoność O (mn), gdzie m i n to liczba wierzchołków każdego kształtu. minkoswkiZestaw zawiera MN elementy w większości. convexHullAlgorytm ma złożoność, który zależy od algorytmu użytego , można dążyć do O (k log (k)) , gdzie k jest wielkość zbioru punktów, więc w naszym przypadku mamy O (mn dziennik (MN) ) . containsAlgorytm ma złożoność liniową, która jest z liczbą krawędzi (w 2D) lub powierzchni (w 3D) o wypukłej, tak naprawdę zależy od Twoich kształtów wyjściowych, ale nie będzie większa niż O (mn) .
Pozwolę ci znaleźć w Google containsalgorytm wypukłych kształtów, jest dość powszechny. Mogę to tutaj umieścić, jeśli będę miał czas.
Ale robimy wykrywanie kolizji, więc możemy to bardzo zoptymalizować
Początkowo mieliśmy dwa ciała A i B poruszające się bez obrotu podczas pomiaru czasu dt (z tego, co mogę stwierdzić, patrząc na twoje zdjęcia). Nazwijmy v A i v B odpowiednie prędkości A i B , które są stałe podczas naszego czasu trwania dt . Otrzymujemy następujące:
a jak wskazano na zdjęciach, ciała te przesuwają się po obszarach (lub objętościach w 3D) podczas ich przemieszczania się:
i kończą się jako A ' i B' po upływie czasu.
Aby zastosować tutaj nasz naiwny algorytm, musielibyśmy tylko obliczyć objętości przeciągnięcia. Ale my tego nie robimy.
W ramce odniesienia B , B nie rusza (duh!). A A ma pewną prędkość w stosunku do B , którą otrzymujesz obliczając v A - v B (możesz zrobić odwrotnie, obliczyć prędkość względną B w ramce odniesienia A ).
Od lewej do prawej: prędkości w podstawowej ramce odniesienia; prędkości względne; obliczanie prędkości względnych.
Traktując B jako nieruchomo w swoim układzie odniesienia, trzeba tylko obliczyć objętość że A zamiata przez co porusza się w czasie dt z jego względną prędkość v - v B .
Zmniejsza to liczbę wierzchołków używanych w obliczeniach sumy Minkowskiego (czasami znacznie).
Inna możliwa optymalizacja to punkt, w którym obliczasz objętość przeciągniętą przez jedno z ciał, powiedzmy A. Nie musisz tłumaczyć wszystkich wierzchołków tworzących A. Tylko te, które należą do krawędzi (ścian w 3D), których zewnętrzna normalna „twarz” kierunku zamiatania. Z pewnością zauważyłeś to już podczas obliczania swoich obszarów zamiatanych dla kwadratów. Możesz stwierdzić, czy normalna jest w kierunku zamiatania, używając iloczynu iloczynu z kierunkiem zamiatania, który musi być dodatni.
Ostatnia optymalizacja, która nie ma nic wspólnego z twoim pytaniem dotyczącym skrzyżowań, jest naprawdę przydatna w naszym przypadku. Wykorzystuje wspomniane prędkości względne i tak zwaną metodę osi oddzielającej. Na pewno już o tym wiesz.
Załóżmy, że znamy promienie z A i B w stosunku do swoich ośrodków masy (to znaczy, że odległość pomiędzy środkiem masy i wierzchołka najdalej od niego), jak poniżej:
Kolizja może wystąpić tylko wtedy, gdy jest to możliwe, że ograniczająca krąg A spotykają się, że z B . Widzimy tutaj, że nie będzie, a sposobem, aby powiedzieć, że komputer jest obliczenie odległości od C B do I , jak na poniższym rysunku i upewnij się, że jest większy niż suma promieni A i B . Jeśli jest większy, nie ma kolizji. Jeśli jest mniejszy, to kolizja.
Nie działa to zbyt dobrze w przypadku kształtów, które są dość długie, ale w przypadku kwadratów lub innych takich kształtów wykluczenie kolizji jest bardzo dobrą heurystą .
Twierdzenie o osi oddzielającej zastosowane do B i objętość przesunięta przez A mówi jednak, czy doszło do zderzenia. Złożoność powiązanego algorytmu jest liniowa z sumą liczb wierzchołków każdego wypukłego kształtu, ale jest mniej magiczna, kiedy przychodzi czas na faktyczną obsługę kolizji.
Nasz nowy, lepszy algorytm, który wykorzystuje skrzyżowania do wykrywania kolizji, ale nadal nie jest tak dobry jak twierdzenie o osi oddzielającej do faktycznego stwierdzenia, czy doszło do kolizji
boolean mayCollide(Body A, Body B) {
Vector2D relativeVelocity = A.velocity - B.velocity;
if (radiiHeuristic(A, B, relativeVelocity)) {
return false; // there is a separating axis between them
}
Volume sweptA = sweptVolume(A, relativeVelocity);
return contains(convexHull(minkowskiMinus(sweptA, B)), Vector2D(0,0));
}
boolean radiiHeuristic(A, B, relativeVelocity)) {
// the code here
}
Volume convexHull(SetOfVertices s) {
// the code here
}
boolean contains(Volume v, Vector2D p) {
// the code here
}
SetOfVertices minkowskiMinus(Body X, Body Y) {
SetOfVertices result = new SetOfVertices();
for (Vertice x in X) {
for (Vertice y in Y) {
result.addVertice(x-y);
}
}
return result;
}
