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

W zasadzie spójrz na poniższy obrazek:

http://www.gamasutra.com/features/20000330/bobic_08.gif

Jeśli oba pola zderzą się ze sobą, linie A i B nakładają się na siebie.

Zauważ, że będzie to musiało być wykonane zarówno na osi X, jak i Y, i obie muszą na siebie nakładać, aby prostokąty się zderzyły.

Jest dobry artykuł w gamasutra.com który odpowiada na 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 osi oddzielającej mówi, że dwa wypukłe kształty nie nakładają się na siebie, jeśli istnieje oś oddzielająca (tj. taka, w której projekcje pokazane nie nakładają się na siebie). Tak więc "istnieje oś oddzielająca" = > "brak nakładania się". Nie jest to dwujęzyczna implikacja, więc nie można zakończyć konwersacji.

W Cocoa możesz łatwo wykryć, czy selectedArea rect przecina obróconą ramkę nsview rect. Nie trzeba nawet obliczać wielokątów, normalów itp. Po prostu dodaj te metody do podklasy NSView. Na przykład, użytkownik wybiera obszar na nsview ' s superview, następnie wywołujesz metodę DoesThisRectSelectMe przekazując selectedArea rect. API convertRect: zrobi to zadanie. Ta sama sztuczka działa po kliknięciu na NSView, aby go wybrać. W takim przypadku wystarczy zastąpić metoda hitTest jak poniżej. API convertPoint: zrobi 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;
}

Odpowiedź M_pgladiatora jest słuszna i wolę ją. Test oddzielania osi jest najprostszą i standardową metodą wykrywania nakładania się prostokątów. Linię, dla której odstępy projekcji nie nakładają się na siebie nazywamy osią rozdzielającą. Rozwiązanie Nilsa Pipenbrincka jest zbyt ogólne. Używa produktu kropkowego , aby sprawdzić, czy jeden kształt jest całkowicie po jednej stronie krawędzi drugiej. Rozwiązanie to w rzeczywistości może wywoływać wielokąty wypukłe O n-krawędziach. Jednak nie jest optmized dla dwóch prostokąty.

Punktem krytycznym odpowiedzi m_pgladiatora jest to, że powinniśmy sprawdzić rzut dwóch prostokątów na obu osiach (x i y). Jeśli dwa rzuty nakładają się na siebie, możemy powiedzieć, że te dwa prostokąty nakładają się na siebie. Zatem powyższe komentarze do odpowiedzi m_pgladiatora są błędne.

Dla sytuacji prostej, 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 przez 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óraś z dwa prostokąty są obracane, Może wymagać pewnych wysiłków, aby określić ich rzut na osi x i Y. Define struct RotatedRect as following:

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

Różnica polega na tym, że szerokość ' jest teraz trochę inna: widthA " dla 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

Sprawdź, czy którakolwiek z linii z jednego prostokąta przecina którąkolwiek z linii z drugiego. Naiwne przecięcie segmentu linii jest łatwe do zakodowania.

Jeśli potrzebujesz większej prędkości, istnieją zaawansowane algorytmy przecięcia segmentów linii (sweep-line). Zobacz http://en.wikipedia.org/wiki/Line_segment_intersection

Jednym z rozwiązań jest użycie wielokąta bez dopasowania. Ten wielokąt jest obliczany z dwóch wielokątów (koncepcyjnie przez przesuwanie jednego wokół drugiego) i określa obszar, dla którego wielokąty nakładają się ze względu na ich względne przesunięcie. Gdy masz ten NFP, musisz po prostu zrobić test inkluzji 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ć NFP.

Wyszukaj wielokąt no Fit w sieci i sprawdź, czy możesz znaleźć algorytm dla wielokątów wypukłych (staje się znacznie bardziej złożony, jeśli masz wielokąty wklęsłe). Jeśli nie możesz nic znaleźć to napisz do mnie na 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óryś z wierzchołków prostokąta 1 znajduje się wewnątrz prostokąta 2 i odwrotnie. Za każdym razem, gdy znajdziesz wierzchołek, który znajduje się wewnątrz drugiego prostokąta, możesz wywnioskować, że przecinają się i przerywają wyszukiwanie. To zajmie się jednym prostokątem, który znajduje się całkowicie wewnątrz drugiego.
2. jeśli powyższy test jest niejednoznaczny znajdź przecinające się punkty każdej linii 1 prostokąta z każda linia drugiego prostokąta. Po znalezieniu punktu przecięcia sprawdź, czy znajduje się on pomiędzy wnętrzem urojonego prostokąta utworzonego przez odpowiednie 4 punkty. Gdy kiedykolwiek taki punkt zostanie znaleziony, stwierdzają, że przecinają się i przerywają poszukiwania.

Jeśli powyższe 2 testy zwrócą wartość false, wówczas te 2 prostokąty nie nakładają się na siebie.

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

Cóż, metoda brute force polega na chodzeniu po krawędziach poziomego prostokąta i sprawdzaniu każdego punktu wzdłuż krawędzi, aby zobaczyć, czy spada na lub w innym prostokącie.

Matematyczną odpowiedzią jest tworzenie równań opisujących każdą krawędź obu prostokątów. Teraz możesz po prostu znaleźć, czy którakolwiek z czterech linii z prostokąta A przecina którąkolwiek z linii prostokąt B, co powinno być prostym (szybkim) rozwiązaniem równań liniowych.

- Adam

Można znaleźć przecięcie każdej strony kątowego prostokąta z każdą stroną osi-wyrównany jeden. V1 + t(V2-v1) i V'1 + t'(V'2-v'1) w zasadzie), znalezienie punktu, w którym linie się spotykają, 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 sprawdzić, czy ten punkt leży na odcinku linii między dwoma wierzchołkami, tj.

Jednak nie obejmuje to przypadku, gdy jeden prostokąt całkowicie pokrywa drugi. Które możesz pokryć, sprawdzając, czy wszystkie cztery punkty jednego prostokąta leżą wewnątrz drugiego prostokąta.

Tak bym zrobił, dla 3D wersja tego problemu:

Modeluj 2 prostokąty jako płaszczyzny opisane równaniami P1 i P2, następnie napisz P1=P2 i uzyskaj z tego równanie linii przecięcia, które nie będzie istnieć, jeśli płaszczyzny są równoległe (bez przecięcia) lub są w tej samej płaszczyźnie, w którym to przypadku otrzymasz 0 = 0. W takim przypadku będziesz musiał zastosować algorytm przecięcia prostokąta 2D.

Wtedy sprawdziłbym czy ta linia, która jest w płaszczyźnie obu prostokąty, przechodzi przez oba prostokąty. Jeśli tak, to masz przecięcie 2 prostokątów, w przeciwnym razie nie masz (lub nie powinieneś, mogłem pominąć narożną obudowę w mojej głowie).

Aby znaleźć, czy linia przechodzi przez prostokąt w tej samej płaszczyźnie, chciałbym znaleźć 2 punkty przecięcia linii i boków prostokąta (modelowanie ich za pomocą równań liniowych), a następnie upewnić się, że punkty przecięć są w zakresie.

To jest matematyczne opisy, niestety nie mam kodu do wykonania powyższego.

Innym sposobem wykonania testu, który jest nieco szybszy niż test osi oddzielającej, jest użycie algorytmu liczb uzwojenia (tylko na ćwiartkach - , a nie sumowanie kąta, 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ę uzwojenia, dwa prostokąty nakładają się na siebie.

Algorytm ten jest nieco bardziej rozwinięty niż test osi oddzielającej, ale jest szybszy, ponieważ wymaga tylko testu półpłaszczyznowego jeśli krawędzie przecinają dwie ćwiartki (w przeciwieństwie do maksymalnie 32 badań metodą osi oddzielającej)

Algorytm ma dodatkową zaletę, że może być użyty do testowania nakładania się dowolnego wielokąta (wypukłego lub wklęsłego). Z tego co wiem, algorytm działa tylko w przestrzeni 2D.

Albo coś mi umyka, dlaczego to takie skomplikowane?

Jeśli (x1,y1) i (X1,Y1) są narożnikami prostokątów, to aby znaleźć przecięcie do:

    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 tak:

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

To może nie być tak optymalne, jak to możliwe. Prędkość nie była wielkim problemem. Jednak wydaje się działać ok dla mnie.

Oto implementacja matlab zaakceptowanej odpowiedzi:

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 metoda konwencjonalna, idź 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ć z: https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function

Mam własną metodę prostszą, jeśli mamy 2 prostokąty:

R1 = (min_x1, max_x1, min_y1, max_y1)

R2 = (min_x2, max_x2, min_y2, max_y2)

Nakładają się wtedy i tylko wtedy, gdy:

Overlap = (max_x1 > min_x2) and (max_x2 > min_x1) and (max_y1 > min_y2) and (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.

Dość już zostało powiedziane w innych odpowiedziach, więc dodam tylko pseudocode one-liner:

!(a.left > b.right || b.left > a.right || a.top > b.bottom || b.top > a.bottom);