Szukam algorytmu do wykrywania, czy przecinają się dwa prostokąty (jeden pod dowolnym kątem, drugi tylko z liniami pionowymi / poziomymi).
Testowanie, czy róg jednego jest w drugim PRAWIE działa. Nie powiedzie się, jeśli prostokąty utworzą kształt podobny do krzyża.
Wydaje się, że dobrym pomysłem jest unikanie nachyleń linii, co wymagałoby specjalnych przypadków dla linii pionowych.
Odpowiedzi:
Standardową metodą byłoby wykonanie testu osi rozdzielających (poszukaj go w Google).
W skrócie:
Zabawne jest to, że wystarczy po prostu sprawdzić wszystkie krawędzie dwóch prostokątów. Jeśli prostokąty nie zachodzą na siebie, jedna z krawędzi będzie osią rozdzielającą.
W 2D możesz to zrobić bez używania nachyleń. Krawędź jest po prostu definiowana jako różnica między dwoma wierzchołkami, np
Możesz uzyskać prostopadłość do tego, obracając ją o 90 °. W 2D jest to łatwe, ponieważ:
Więc nie ma tu żadnych trygonometrii ani nachyleń. Nie jest również wymagana normalizacja wektora do długości jednostki.
Jeśli chcesz sprawdzić, czy punkt znajduje się po jednej lub drugiej stronie linii, możesz po prostu użyć iloczynu skalarnego. znak powie ci, po której jesteś stronie:
Teraz porównaj wszystkie punkty prostokąta A z krawędziami prostokąta B i odwrotnie. Jeśli znajdziesz oddzielającą krawędź, obiekty nie przecinają się (pod warunkiem, że wszystkie inne punkty w B znajdują się po drugiej stronie badanej krawędzi - patrz rysunek poniżej). Jeśli nie znajdziesz oddzielającej krawędzi, albo prostokąty się przecinają, albo jeden prostokąt jest zawarty w drugim.
Tak przy okazji, test działa z dowolnymi wypukłymi wielokątami.
Poprawka: Aby zidentyfikować krawędź oddzielającą, nie wystarczy przetestować wszystkie punkty jednego prostokąta względem każdej krawędzi drugiej. Krawędź kandydująca E (poniżej) jako taka byłaby identyfikowana jako krawędź oddzielająca, ponieważ wszystkie punkty w A znajdują się w tej samej półpłaszczyźnie E. Jednak nie jest to krawędź oddzielająca, ponieważ wierzchołki Vb1 i Vb2 z B są również w tej półpłaszczyźnie. Byłaby to tylko krawędź oddzielająca, gdyby tak nie było http://www.iassess.com/collision.png
źródło
Zasadniczo spójrz na poniższy obrazek:
Jeśli oba pola się zderzą, linie A i B będą się nakładać.
Zwróć uwagę, że będzie to musiało zostać zrobione zarówno na osi X, jak i na osi Y, a obie muszą na siebie zachodzić, aby prostokąty się zderzyły.
Na gamasutra.com jest dobry artykuł, który odpowiada na to pytanie (zdjęcie pochodzi z artykułu). Zrobiłem podobny algorytm 5 lat temu i muszę znaleźć mój fragment kodu, aby umieścić go tutaj później
Poprawka : Twierdzenie o oddzielnych osiach stwierdza, że dwa wypukłe kształty nie nakładają się, jeśli istnieje oś oddzielająca (tj. Taka, w której występy, jak pokazano , nie zachodzą na siebie). Więc „Istnieje oś oddzielająca” => „Brak nakładania się”. Nie jest to podwójna implikacja, więc nie można wnioskować na odwrót.
źródło
Odpowiedź m_pGladiator jest prawidłowa i wolę ją. Test oddzielnych osi jest najprostszą i standardową metodą wykrywania nakładania się prostokątów. Linię, dla której odstępy rzutowania nie zachodzą na siebie, nazywamy osią rozdzielającą . Rozwiązanie Nilsa Pipenbrincka jest zbyt ogólne. Wykorzystuje iloczyn skalarny, aby sprawdzić, czy jeden kształt jest całkowicie po jednej stronie krawędzi drugiej. To rozwiązanie faktycznie może spowodować powstanie wielokątów wypukłych o n-krawędziach. Jednak nie jest zoptymalizowany dla dwóch prostokątów.
krytycznym punktem odpowiedzi m_pGladiator jest to, że powinniśmy sprawdzić rzutowanie dwóch prostokątów na obie osie (x i y). Jeśli dwa rzuty nakładają się, możemy powiedzieć, że te dwa prostokąty nakładają się. Więc komentarze powyżej do odpowiedzi m_pGladiator są błędne.
dla prostej sytuacji, jeśli dwa prostokąty nie są obrócone, przedstawiamy prostokąt o strukturze:
nazywamy prostokąt A, B z rectA, rectB.
jeśli którykolwiek z dwóch prostokątów jest obrócony, może wymagać pewnych wysiłków, aby określić ich rzut na osie x i y. Zdefiniuj strukturę RotatedRect w następujący sposób:
różnica polega na tym, że szerokość 'jest teraz trochę inna: widthA' for rectA:
Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle)
widthB 'for rectB:Math.sqrt(rectB.width*rectB.width + rectB.height*rectB.height) * Math.cos(rectB.angle)
Może odnosić się do GDC (Game Development Conference 2007) PPT www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt
źródło
W kakao można łatwo wykryć, czy prostokąt selectedArea przecina prostokąt ramki z obróconym NSView. Nie musisz nawet obliczać wielokątów, normalnych i takich. Po prostu dodaj te metody do swojej podklasy NSView. Na przykład użytkownik wybiera obszar w superviewie NSView, a następnie wywołujemy metodę DoesThisRectSelectMe, przekazując prostokąt selectedArea. API convertRect: wykona tę pracę. Ta sama sztuczka działa, gdy klikniesz NSView, aby go wybrać. W takim przypadku po prostu zastąp metodę hitTest, jak poniżej. API convertPoint: wykona to zadanie ;-)
źródło
Sprawdź, czy którakolwiek z linii z jednego prostokąta przecina którąkolwiek z linii z drugiego. Naiwne przecięcie segmentów linii jest łatwe do zakodowania.
Jeśli potrzebujesz większej prędkości, istnieją zaawansowane algorytmy przecinania się segmentów linii (linia przeciągnięcia). Zobacz http://en.wikipedia.org/wiki/Line_segment_intersection
źródło
Jednym z rozwiązań jest użycie czegoś, co nazywa się niepasującym wielokątem. Ten wielokąt jest obliczany z dwóch wielokątów (koncepcyjnie przez przesuwanie jednego wokół drugiego) i definiuje obszar, na który nachodzą wielokąty, biorąc pod uwagę ich względne przesunięcie. Po uzyskaniu tego punktu NFP wystarczy wykonać test włączenia z punktem określonym przez względne przesunięcie dwóch wielokątów. Ten test włączenia jest szybki i łatwy, ale najpierw musisz utworzyć punkt NFP.
Poszukaj w Internecie hasła No Fit Polygon i sprawdź, czy możesz znaleźć algorytm dla wypukłych wielokątów (robi się ZNACZNIE bardziej złożony, jeśli masz wklęsłe wielokąty). Jeśli nie możesz niczego znaleźć, napisz do mnie na adres howard dot J dot may gmail dot com
źródło
Oto, co myślę, że zajmie się wszystkimi możliwymi przypadkami. Wykonaj następujące testy.
Jeśli powyższe 2 testy dadzą wynik fałszywy, wówczas te 2 prostokąty nie nakładają się.
źródło
Jeśli używasz języka Java, wszystkie implementacje interfejsu Shape mają metodę intersects , która przyjmuje prostokąt.
źródło
Cóż, metoda brutalnej siły polega na chodzeniu po krawędziach poziomego prostokąta i sprawdzaniu każdego punktu wzdłuż krawędzi, aby zobaczyć, czy spada na drugi prostokąt, czy też w niego.
Matematyczną odpowiedzią jest utworzenie równań opisujących każdą krawędź obu prostokątów. Teraz możesz po prostu sprawdzić, czy którakolwiek z czterech linii prostokąta A przecina którąkolwiek z linii prostokąta B, który powinien być prostym (szybkim) rozwiązaniem równań liniowych.
-Adam
źródło
Można było znaleźć przecięcie każdej strony prostokąta ustawionego pod kątem z każdą stroną prostokąta ustawionego pod kątem. Zrób to, znajdując równanie nieskończonej linii, na której leży każda strona (tj. V1 + t (v2-v1) i v'1 + t '(v'2-v'1) w zasadzie), znajdując punkt, w którym linie spotykają się rozwiązując dla t, gdy te dwa równania są równe (jeśli są równoległe, możesz to sprawdzić), a następnie sprawdzając, czy ten punkt leży na odcinku linii między dwoma wierzchołkami, tj. czy to prawda, że 0 <= t <= 1 i 0 <= t '<= 1.
Nie dotyczy to jednak przypadku, gdy jeden prostokąt całkowicie zakrywa drugi. Możesz to sprawdzić, sprawdzając, czy wszystkie cztery punkty jednego z prostokątów leżą wewnątrz drugiego prostokąta.
źródło
Oto co bym zrobił dla wersji 3D tego problemu:
Zamodeluj 2 prostokąty jako płaszczyzny opisane równaniem P1 i P2, a następnie zapisz P1 = P2 i wyprowadź z tego równanie przecięcia, które nie będzie istniało, jeśli płaszczyzny są równoległe (brak przecięcia) lub znajdują się w tej samej płaszczyźnie, w takim przypadku otrzymasz 0 = 0. W takim przypadku będziesz musiał zastosować algorytm przecięcia prostokąta 2D.
Wtedy zobaczyłbym, czy ta linia, która jest w płaszczyźnie obu prostokątów, przechodzi przez oba prostokąty. Jeśli tak, to masz przecięcie 2 prostokątów, w przeciwnym razie nie (lub nie powinno, mogłem przegapić narożną walizkę w mojej głowie).
Aby sprawdzić, czy linia przechodzi przez prostokąt na tej samej płaszczyźnie, znajdę 2 punkty przecięcia linii i boków prostokąta (modelując je za pomocą równań linii), a następnie upewnię się, że punkty przecięcia są z w zasięg.
To opisy matematyczne, niestety nie mam kodu aby to zrobić.
źródło
Innym sposobem wykonania testu, który jest nieco szybszy niż przy użyciu testu osi rozdzielających, jest użycie algorytmu liczb uzwojeń (tylko na kwadrantach - nie sumowanie kątów, które jest przerażająco wolne) na każdym wierzchołku dowolnego prostokąta (dowolnie wybranego). Jeśli którykolwiek z wierzchołków ma niezerową liczbę uzwojeń, dwa prostokąty nakładają się.
Ten algorytm jest nieco bardziej rozwlekły niż test osi rozdzielającej, ale jest szybszy, ponieważ wymaga tylko testu półpłaszczyzny, jeśli krawędzie przecinają dwa kwadranty (w przeciwieństwie do maksymalnie 32 testów przy użyciu metody osi rozdzielających)
Algorytm ma tę kolejną zaletę, że można go używać do testowania zachodzenia dowolnego wielokąta (wypukłego lub wklęsłego). O ile wiem, algorytm działa tylko w przestrzeni 2D.
źródło
Albo brakuje mi czegoś innego, po co to tak skomplikowane?
jeśli (x1, y1) i (X1, Y1) są rogami prostokątów, to aby znaleźć przecięcie wykonaj:
źródło
Zaimplementowałem to w ten sposób:
Macierz mB to dowolna macierz transformacji afinicznej, która konwertuje punkty w przestrzeni B na punkty w przestrzeni A. Obejmuje to prosty obrót i translację, obrót ze skalowaniem oraz pełne wypaczenia afiniczne, ale nie wypaczenia perspektywy.
Może nie być tak optymalne, jak to możliwe. Szybkość nie była wielkim problemem. Jednak wydaje mi się, że działa dobrze dla mnie.
źródło
Oto implementacja zaakceptowanej odpowiedzi w języku Matlab:
źródło
Jest to konwencjonalna metoda, przejdź linia po linii i sprawdź, czy linie się przecinają. To jest kod w MATLABIE.
funkcję InterX można pobrać ze strony: https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function
źródło
Mam własną prostszą metodę, jeśli mamy 2 prostokąty:
R1 = (min_x1, max_x1, min_y1, max_y1)
R2 = (min_x2, max_x2, min_y2, max_y2)
Zachodzą na siebie wtedy i tylko wtedy, gdy:
Nakładanie = (max_x1> min_x2) i (max_x2> min_x1) i (max_y1> min_y2) i (max_y2> min_y1)
Możesz to zrobić również dla pudełek 3D, w rzeczywistości działa to dla dowolnej liczby wymiarów.
źródło
Wystarczająco dużo zostało powiedziane w innych odpowiedziach, więc dodam tylko jedną linijkę pseudokodu:
źródło