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

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.

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

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.

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

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

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

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

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

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

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

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.

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

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.

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

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.

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

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

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.

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