Algorytm wykrywania przecięcia dwóch prostokątów?

143

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.

user20493
źródło
co, jeśli dodasz do swojego sprawdzania narożnika, sprawdzenia, czy drugi prostokąt znajduje się w granicach (prostokątny) prostokąta pod kątem?
Wes P
W jakim języku to zrobisz? Ponieważ w Javie są wbudowane klasy, które na to pozwalają.
Martijn
Myślę, że graficzny interfejs API i większość bibliotek GUI (takich jak swing) ma to zaimplementowane.
l_39217_l
że można pominąć przypadki, w których nakładają się one, ale nie jest w środku każdym rogu prostokąta
Florian Bösch
1
To pytanie jest prawie takie samo jak: stackoverflow.com/questions/306316/… . Chociaż poszukuje rozwiązania, które jest szczególnie przydatne w C ++. Przyjęta odpowiedź jest również dość prosta i jednoznaczna.
Silver Gonzales,

Odpowiedzi:

162

Standardową metodą byłoby wykonanie testu osi rozdzielających (poszukaj go w Google).

W skrócie:

  • Dwa obiekty nie przecinają się, jeśli możesz znaleźć linię oddzielającą oba obiekty. np. obiekty / wszystkie punkty obiektu znajdują się po różnych stronach linii.

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

  edge = v(n) - v(n-1)

Możesz uzyskać prostopadłość do tego, obracając ją o 90 °. W 2D jest to łatwe, ponieważ:

  rotated.x = -unrotated.y
  rotated.y =  unrotated.x

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:

  // rotated: your rotated edge
  // v(n-1) any point from the edge.
  // testpoint: the point you want to find out which side it's on.

  side = sign (rotated.x * (testpoint.x - v(n-1).x) + 
               rotated.y * (testpoint.y - v(n-1).y);

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

Nils Pipenbrinck
źródło
2
Ten algorytm nie działa we wszystkich przypadkach. Możliwe jest umieszczenie drugiego prostokąta obróconego o 45 stopni do pierwszego prostokąta i przesuniętego wzdłuż przekątnej tak, aby spełniał powyższe testy przecięcia, ale się nie przecinał.
Skizz
6
Skizz, sprawdź wszystkie osiem krawędzi. Jeśli obiekty nie przecinają jednej z ośmiu krawędzi, to je rozdzieli. Dlaczego nie opublikujesz zdjęcia przedstawiającego Twoją sprawę? Oś mogę ci pokazać ..
Nils Pipenbrinck,
2
Mój błąd, radzi sobie z tym stanem.
Skizz
2
Obraz jest teraz martwy (listopad 2012)
John Dvorak
2
Miałem duży problem z wizualizacją tego, więc odtworzyłem to, jak myślę, że wyglądał odnośnik. imgur.com/bNwrzsv
Rjdlee
16

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.

m_pGladiator
źródło
1
Oczywiście, ponieważ dwa kwadraty (0,0,1,1) i (0,3,1,4) nie nakładają się, ale ich rzuty na osi x całkowicie się pokrywają. Oba testy są konieczne, kombinacja jest wystarczająca.
MSalters
18
Nie wystarczy, aby rzuty xiy zachodziły na siebie: weź np. Prostokąty [(0,0), (0,3), (3,3), (3,0)] i [(2,5), (5,2), (7,4), (4,7)].
Joel w Gö
4
Zgadzam się z @Joel w Gö. Ta metoda pomija duży zestaw przypadków, w których prostokąty nie nakładają się, ale ich rzutowane promienie mają miejsce zarówno w osi x, jak i y.
Scottie T,
5
Ta odpowiedź nie jest błędna, ale wprowadza w błąd. Prawdą jest, że: Jeśli te dwa pola się zderzają, linie A i B będą się nakładać. ale prawdą jest również, że: Jeśli linie A i B nakładają się na siebie, oba pola mogą, ale nie muszą, kolidować
Matt spala
7
@floater: Powiedziałbym, że jest to nie tylko błędne, ale i mylące, co jest jeszcze gorsze.
BlueRaja - Danny Pflughoeft
4

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:

struct Rect {
    x, // the center in x axis
    y, // the center in y axis
    width,
    height
}

nazywamy prostokąt A, B z rectA, rectB.

    if Math.abs(rectA.x - rectB.x) < (Math.abs(rectA.width + rectB.width) / 2) 
&& (Math.abs(rectA.y - rectB.y) < (Math.abs(rectA.height + rectB.height) / 2))
    then
        // A and B collide
    end if

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:

struct RotatedRect : Rect {
    double angle; // the rotating angle oriented to its center
}

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)

    if Math.abs(rectA.x - rectB.x) < (Math.abs(widthA' + widthB') / 2) 
&& (Math.abs(rectA.y - rectB.y) < (Math.abs(heightA' + heightB') / 2))
    then
        // A and B collide
    end if

Może odnosić się do GDC (Game Development Conference 2007) PPT www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt

tristan
źródło
Dlaczego potrzebujesz Math.abs () w "Math.abs (rectA.width + rectB.width)", aby obsłużyć ujemne szerokości?
AlexWien
Oś oddzielająca niekoniecznie jest kierunkiem kompasu, może mieć dowolny kąt.
Ben Voigt
Nieobrócone prostokąty prostokąty A (x = 0, y = 0, szerokość = 1, wysokość = 1) i prostokątB (x = 2, y = 0, szerokość = 100, wysokość = 1) nie przecinają się, ale Twoja metoda mówi, że tak krzyżować. czy robię coś źle?
Kagami Sascha Rosylight,
4

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 ;-)

- (BOOL)DoesThisRectSelectMe:(NSRect)selectedArea
{
    NSRect localArea = [self convertRect:selectedArea fromView:self.superview];

    return NSIntersectsRect(localArea, self.bounds);
}


- (NSView *)hitTest:(NSPoint)aPoint
{
    NSPoint localPoint = [self convertPoint:aPoint fromView:self.superview];
    return NSPointInRect(localPoint, self.bounds) ? self : nil;
}
Leonardo
źródło
2
Ten kod działa tylko dla prostokątów, które są kwadratowe na ekranie. To trywialny przypadek. Założenie jest takie, że mamy do czynienia z prostokątami, które nie są ustawione pod kątem 90 stopni względem ekranu lub siebie.
Duncan C
Jak sprawdziłem i użyłem w moich aplikacjach, ten kod działa na każdym obróconym prostokącie. Bez względu na stopień rotacji.
Leonardo
To nie opisuje algorytmu, ale tylko wspomina o bibliotece, która już go używa.
Ben Voigt
2

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

Louis Brandy
źródło
4
Ostrożny! Nie zapomnij o przypadku, gdy jeden prostokąt całkowicie otacza inny
Pitarou
2

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

Howard May
źródło
1

Oto, co myślę, że zajmie się wszystkimi możliwymi przypadkami. Wykonaj następujące testy.

  1. Sprawdź, czy którykolwiek z wierzchołków prostokąta 1 znajduje się wewnątrz prostokąta 2 i odwrotnie. Za każdym razem, gdy znajdziesz wierzchołek znajdujący się wewnątrz innego prostokąta, możesz wywnioskować, że przecinają się i zatrzymują wyszukiwanie. Spowoduje to, że jeden prostokąt będzie znajdował się całkowicie wewnątrz drugiego.
  2. Jeśli powyższy test nie daje jednoznacznych wyników, znajdź przecinające się punkty każdej linii jednego prostokąta z każdą linią drugiego prostokąta. Po znalezieniu punktu przecięcia sprawdź, czy znajduje się on pomiędzy wyimaginowanym prostokątem utworzonym przez odpowiednie 4 punkty. Kiedykolwiek taki punkt zostanie znaleziony, wyciągnij wniosek, że przecinają się i zatrzymują poszukiwania.

Jeśli powyższe 2 testy dadzą wynik fałszywy, wówczas te 2 prostokąty nie nakładają się.

John Smith
źródło
0

Jeśli używasz języka Java, wszystkie implementacje interfejsu Shape mają metodę intersects , która przyjmuje prostokąt.

Brendan Cashman
źródło
Niestety używam C #. Klasa Rectangle ma metodę Contains (), ale jest ona przeznaczona tylko dla nieobróconych prostokątów.
user20493
Metoda intersects () jest dość bezużyteczna, ponieważ zwraca wartość logiczną zamiast przecięcia, jak sądzę.
ZZ 5
0

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

Adam Davis
źródło
2
Problem z równaniami polega na tym, że masz linię pionową o nieskończonym nachyleniu.
user20493
Dla każdego rozwiązania są etui narożne.
Adam Davis,
2
i jeden kwadrat całkowicie otaczający drugi.
Oliver Hallam
0

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.

HenryR
źródło
0

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ć.

wolna przestrzeń
źródło
Przegapiłeś część, w której jeśli znajdziesz płaską linię przecięcia, musisz upewnić się, że jej część znajduje się w obu prostokątach.
Lee Louviere
0

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.

Mads
źródło
3
Może się mylę, ale czy to po prostu nie sprawdza, czy wierzchołki jednego prostokąta znajdują się wewnątrz drugiego? Jeśli tak, to nie wystarczy, ponieważ prostokąty mogą się nakładać bez żadnych wierzchołków w środku.
sinelaw
Czy potrafią z prostokątami? W jaki sposób? Wydaje mi się, że aby przecinały się 2 prostokąty, przynajmniej jeden wierzchołek jednego z nich musi leżeć na drugim prostokącie.
Duncan C
@DuncanC: Tak, mogą. Kontrprzykładem jest krzyż i został nawet wymieniony w pierwotnym pytaniu.
Ben Voigt
@BenVoigt To bardzo stary wątek, ale masz absolutną rację.
Duncan C
0

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:

    xIntersect = false;
    yIntersect = false;
    if (!(Math.min(x1, x2, x3, x4) > Math.max(X1, X2, X3, X4) || Math.max(x1, x2, x3, x4) < Math.min(X1, X2, X3, X4))) xIntersect = true;
    if (!(Math.min(y1, y2, y3, y4) > Math.max(Y1, Y2, Y3, Y4) || Math.max(y1, y2, y3, y4) < Math.min(Y1, Y2, Y3, Y4))) yIntersect = true;
    if (xIntersect && yIntersect) {alert("Intersect");}
user1517108
źródło
3
Tęsknisz za tym, że chce, aby jeden został obrócony o dowolny kąt.
Robotbugs,
0

Zaimplementowałem to w ten sposób:

bool rectCollision(const CGRect &boundsA, const Matrix3x3 &mB, const CGRect &boundsB)
{
    float Axmin = boundsA.origin.x;
    float Axmax = Axmin + boundsA.size.width;
    float Aymin = boundsA.origin.y;
    float Aymax = Aymin + boundsA.size.height;

    float Bxmin = boundsB.origin.x;
    float Bxmax = Bxmin + boundsB.size.width;
    float Bymin = boundsB.origin.y;
    float Bymax = Bymin + boundsB.size.height;

    // find location of B corners in A space
    float B0x = mB(0,0) * Bxmin + mB(0,1) * Bymin + mB(0,2);
    float B0y = mB(1,0) * Bxmin + mB(1,1) * Bymin + mB(1,2);

    float B1x = mB(0,0) * Bxmax + mB(0,1) * Bymin + mB(0,2);
    float B1y = mB(1,0) * Bxmax + mB(1,1) * Bymin + mB(1,2);

    float B2x = mB(0,0) * Bxmin + mB(0,1) * Bymax + mB(0,2);
    float B2y = mB(1,0) * Bxmin + mB(1,1) * Bymax + mB(1,2);

    float B3x = mB(0,0) * Bxmax + mB(0,1) * Bymax + mB(0,2);
    float B3y = mB(1,0) * Bxmax + mB(1,1) * Bymax + mB(1,2);

    if(B0x<Axmin && B1x<Axmin && B2x<Axmin && B3x<Axmin)
        return false;
    if(B0x>Axmax && B1x>Axmax && B2x>Axmax && B3x>Axmax)
        return false;
    if(B0y<Aymin && B1y<Aymin && B2y<Aymin && B3y<Aymin)
        return false;
    if(B0y>Aymax && B1y>Aymax && B2y>Aymax && B3y>Aymax)
        return false;

    float det = mB(0,0)*mB(1,1) - mB(0,1)*mB(1,0);
    float dx = mB(1,2)*mB(0,1) - mB(0,2)*mB(1,1);
    float dy = mB(0,2)*mB(1,0) - mB(1,2)*mB(0,0);

    // find location of A corners in B space
    float A0x = (mB(1,1) * Axmin - mB(0,1) * Aymin + dx)/det;
    float A0y = (-mB(1,0) * Axmin + mB(0,0) * Aymin + dy)/det;

    float A1x = (mB(1,1) * Axmax - mB(0,1) * Aymin + dx)/det;
    float A1y = (-mB(1,0) * Axmax + mB(0,0) * Aymin + dy)/det;

    float A2x = (mB(1,1) * Axmin - mB(0,1) * Aymax + dx)/det;
    float A2y = (-mB(1,0) * Axmin + mB(0,0) * Aymax + dy)/det;

    float A3x = (mB(1,1) * Axmax - mB(0,1) * Aymax + dx)/det;
    float A3y = (-mB(1,0) * Axmax + mB(0,0) * Aymax + dy)/det;

    if(A0x<Bxmin && A1x<Bxmin && A2x<Bxmin && A3x<Bxmin)
        return false;
    if(A0x>Bxmax && A1x>Bxmax && A2x>Bxmax && A3x>Bxmax)
        return false;
    if(A0y<Bymin && A1y<Bymin && A2y<Bymin && A3y<Bymin)
        return false;
    if(A0y>Bymax && A1y>Bymax && A2y>Bymax && A3y>Bymax)
        return false;

    return true;
}

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.

Robotbugs
źródło
0

Oto implementacja zaakceptowanej odpowiedzi w języku Matlab:

function olap_flag = ol(A,B,sub)

%A and B should be 4 x 2 matrices containing the xy coordinates of the corners in clockwise order

if nargin == 2
  olap_flag = ol(A,B,1) && ol(B,A,1);
  return;
end

urdl = diff(A([1:4 1],:));
s = sum(urdl .* A, 2);
sdiff = B * urdl' - repmat(s,[1 4]);

olap_flag = ~any(max(sdiff)<0);
Jed
źródło
0

Jest to konwencjonalna metoda, przejdź linia po linii i sprawdź, czy linie się przecinają. To jest kod w MATLABIE.

C1 = [0, 0];    % Centre of rectangle 1 (x,y)
C2 = [1, 1];    % Centre of rectangle 2 (x,y)
W1 = 5; W2 = 3; % Widths of rectangles 1 and 2
H1 = 2; H2 = 3; % Heights of rectangles 1 and 2
% Define the corner points of the rectangles using the above
R1 = [C1(1) + [W1; W1; -W1; -W1]/2, C1(2) + [H1; -H1; -H1; H1]/2];
R2 = [C2(1) + [W2; W2; -W2; -W2]/2, C2(2) + [H2; -H2; -H2; H2]/2];

R1 = [R1 ; R1(1,:)] ;
R2 = [R2 ; R2(1,:)] ;

plot(R1(:,1),R1(:,2),'r')
hold on
plot(R2(:,1),R2(:,2),'b')


%% lines of Rectangles 
L1 = [R1(1:end-1,:) R1(2:end,:)] ;
L2 = [R2(1:end-1,:) R2(2:end,:)] ;
%% GEt intersection points
P = zeros(2,[]) ;
count = 0 ;
for i = 1:4
    line1 = reshape(L1(i,:),2,2) ;
    for j = 1:4
        line2 = reshape(L2(j,:),2,2) ;
        point = InterX(line1,line2) ;
        if ~isempty(point)
            count = count+1 ;
            P(:,count) = point ;
        end
    end
end
%%
if ~isempty(P)
    fprintf('Given rectangles intersect at %d points:\n',size(P,2))
    plot(P(1,:),P(2,:),'*k')
end

funkcję InterX można pobrać ze strony: https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function

Siva Srinivas Kolukula
źródło
0

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.

BitFarmer
źródło
0

Wystarczająco dużo zostało powiedziane w innych odpowiedziach, więc dodam tylko jedną linijkę pseudokodu:

!(a.left > b.right || b.left > a.right || a.top > b.bottom || b.top > a.bottom);
Przemek
źródło