it-swarm-eu.dev

Algoritmus pro detekci průsečíku dvou obdélníků?

Hledám algoritmus, který by zjistil, zda se dva obdélníky protínají (jeden v libovolném úhlu, druhý s pouze svislými/vodorovnými čarami).

Testování, zda je roh jednoho z ostatních ALMOST funguje. Selhává, pokud obdélníky tvoří křížovitý tvar.

Vypadá to jako dobrý nápad vyhnout se použití svahů linek, což by vyžadovalo speciální případy pro svislé čáry.

136
user20493

Standardní metodou by bylo provést test oddělující osy (na tom vyhledávejte google).

Ve zkratce:

  • Dva objekty se neprotínají, pokud můžete najít čáru, která odděluje dva objekty. např. objekty/všechny body objektu jsou na různých stranách čáry.

Zábavná věc je, že stačí zkontrolovat všechny okraje obou obdélníků. Pokud se obdélníky nepřekrývají, jedna z hran bude oddělovací osou.

Ve 2D to můžete udělat bez použití svahů. Okraj je jednoduše definován jako rozdíl mezi dvěma vrcholy, např.

  Edge = v(n) - v(n-1)

Kolmo k tomu se dostanete otočením o 90 °. Ve 2D je to snadné:

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

Takže žádné trigonometrie nebo svahy. Normalizace vektoru na délku jednotky se také nevyžaduje.

Pokud chcete otestovat, zda je bod na jedné nebo druhé straně čáry, můžete použít pouze bodový produkt. znaménko vám sdělí, na které straně jste:

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

Nyní otestujte všechny body obdélníku A proti hranám obdélníku B a naopak. Pokud najdete oddělovací hranu, objekty se neprotínají (pokud jsou všechny ostatní body v B na druhé straně testované hrany - viz obrázek níže). Pokud nenajdete žádné dělící hrany, obdélníky se protínají nebo je v jednom obdélníku.

Test funguje s libovolnými konvexními polygony btw .. 

Změna: Pro identifikaci dělící hrany nestačí otestovat všechny body jednoho obdélníku proti každé hraně druhé. Kandidát-hrana E (dole) by byl jako takový být identifikován jako separační hrana, jak všechny body v A jsou ve stejné polovině-rovina E. Nicméně, to není oddělovací Edge protože vrcholy Vb1 a Vb2 B\t jsou také v této polovině letadla. Kdyby tomu tak nebylo, byl by to jen separační okraj http://www.iassess.com/collision.png

151
Nils Pipenbrinck

V podstatě se podívejte na následující obrázek: 


 

Pokud se dvě pole srazí, čáry A a B se budou překrývat.

Všimněte si, že toto bude muset být provedeno jak na ose X, tak na ose Y a obě se musí překrývat, aby se obdélníky kolidovaly.

Tam je dobrý článek v gamasutra.com který odpovídá na otázku (obrázek je z článku). Udělal jsem podobný algoritmus před 5 lety a musím najít svůj úryvek kódu, abych to sem napsal později

Doplněk: Věta o separační ose uvádí, že dvě konvexní tvary ne se překrývají, pokud existuje oddělovací osa (tj. Tam, kde se projekce zobrazují ne překrývají). Takže "Oddělovací osa existuje" => "Žádné překrytí". Toto není bi-implikace, takže nemůžete uzavřít konverzaci. 

15
m_pGladiator

V Cocoa můžete snadno zjistit, zda vybranáArea rect protíná váš otočený NSView rámeček. Nemusíte ani počítat polygony, normály a takové. Stačí přidat tyto metody do podtřídy NSView. Například uživatel vybere oblast v dohledu NSView, poté zavoláte metodu DoesThisRectSelectMe předáním vybranéArea rect. API convertRect: provede tuto práci. Stejný trik funguje, když kliknete na NSView, abyste jej vybrali. V takovém případě jednoduše přepište metodu hitTest níže. Převaděč API: udělá tuto práci ;-)

- (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;
}
4
Leonardo

odpověď m_pGladiatoru je správná a já to dávám přednost. Test separační osy je nejjednodušší a standardní metoda pro detekci překrytí obdélníku. Řádek, pro který se nepřesahují projekční intervaly, nazýváme oddělující osa. Řešení Nilsa Pipenbrincka je příliš obecné. Používá dot product ke kontrole, zda je jeden tvar zcela na jedné straně Edge druhé. Toto řešení může skutečně vyvolat konvexní polygony n-Edge. Není však optmized pro dva obdélníky.

kritickým bodem m_pGladiátorovy odpovědi je, že bychom měli zkontrolovat projekce dvou obdélníků na obou osách (x a y). Pokud se dvě projekce překrývají, můžeme říci, že tyto dva obdélníky se překrývají. Takže výše uvedené komentáře k odpovědi m_pGladiatoru jsou špatné.

pro jednoduchou situaci, pokud se dva obdélníky neotočí, představujeme obdélník se strukturou:

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

pojmenujeme obdélník A, B s 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

pokud se kterýkoliv ze dvou obdélníků otočí, Může to vyžadovat určité úsilí, aby se určily jejich projekce na osách x a y. Definujte struct RotatedRect následujícím způsobem:

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

rozdíl je v tom, jak je šířka nyní trochu jiná: widthA 'pro rectA: Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle) widthB' pro 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

Mohl by odkazovat na GDC (Game Development Conference 2007) PPT www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt

3
tristan

Zkontrolujte, zda některá z čar z jednoho obdélníku protíná některou z čar od druhé. Průsečík naivní linie lze snadno kódovat.

Pokud potřebujete více rychlosti, existují pokročilé algoritmy pro průsečík úsečky (zametací čára). Viz http://en.wikipedia.org/wiki/Line_segment_intersection

2
Louis Brandy

Jedním z řešení je použít něco, co se nazývá polygon typu No Fit. Tento polygon se vypočítá ze dvou polygonů (koncepčně posunutím jeden kolem druhého) a definuje plochu, pro kterou se polygony překrývají vzhledem k jejich relativnímu posunu. Jakmile budete mít tento NFP, musíte jednoduše provést test zahrnutí s bodem daným relativním posunem dvou polygonů. Tento test začlenění je rychlý a snadný, ale musíte nejprve vytvořit NFP.

Vyhledejte na webu polygon No Fit a zjistěte, zda můžete najít algoritmus pro konvexní polygony (pokud máte konkávní polygony, dostane se mnohem složitější). Pokud nemůžete najít nic, pak mi napište na howard dot J dot může gmail dot com

2
Howard May

Zde je to, co si myslím, že se postará o všechny možné případy. Proveďte následující testy. 

  1. Zkontrolujte, zda kterýkoliv z vrcholů obdélníku 1 leží uvnitř obdélníku 2 a naopak. Kdykoliv najdete vrchol, který se nachází uvnitř druhého obdélníku, můžete usoudit, že se protínají a zastavují hledání. To se postará o jeden obdélník, který bude zcela uvnitř.
  2. Pokud je výše uvedený test nejednoznačný, najděte průsečíky každého řádku 1 obdélníku s každým řádkem druhého obdélníku. Jakmile je bod průniku nalezen, zkontrolujte, zda se nachází mezi imaginárním obdélníkem vytvořeným odpovídajícími 4 body. Když je takový bod nalezen, dospěje k závěru, že se protínají a zastavují hledání.

Pokud se výše uvedené 2 testy vrátí nepravdivé, pak se tyto 2 obdélníky nepřekrývají.

1
John Smith

Pokud používáte Javu, všechny implementace rozhraní Shape mají metodu , která má obdélník. 

0
Brendan Cashman

Buď mi chybí něco jiného, ​​proč je to tak komplikované?

jestliže (x1, y1) a (X1, Y1) jsou rohy obdélníků, pak najít průsečík udělat:

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

Metoda hrubé síly má projít hranami horizontálního obdélníku a zkontrolovat každý bod podél hrany, aby zjistila, zda dopadá na nebo do druhého obdélníku.

Matematická odpověď je tvořit rovnice popisující každý okraj obou obdélníků. Nyní můžete jednoduše zjistit, zda některá ze čtyř čar z obdélníku A protíná některou z čar obdélníku B, což by mělo být jednoduché (rychlé) řešení lineární rovnice.

- Adam

0
Adam Davis

Průsečík každé strany úhlového obdélníku můžete najít na každé straně osy zarovnané na ose. Udělejte to tak, že zjistíte rovnici nekonečné linie, na které leží každá strana (tj. V1 + t(v2-v1) a v'1 + t '(v'2-v'1) v podstatě). bod, ve kterém se řádky setkávají při řešení t, když jsou tyto dvě rovnice stejné (pokud jsou rovnoběžné, můžete testovat) a poté otestovat, zda tento bod leží na úsečce mezi dvěma vrcholy, tj. je to pravda, že 0 <= t <= 1 a 0 <= t '= 1.

To se však nevztahuje na případ, kdy jeden obdélník zcela pokrývá druhý obdélník. Že můžete pokrýt testováním, zda všechny čtyři body obou obdélníků leží uvnitř druhého obdélníku. 

0
HenryR

To je to, co bych udělal pro 3D verzi tohoto problému:

Modelujte 2 obdélníky jako roviny popsané rovnicí P1 a P2, pak zapište P1 = P2 a odvozte z toho linii rovnice průsečíku, která nebude existovat, pokud jsou roviny rovnoběžné (žádný průsečík), nebo jsou ve stejné rovině, v tom případě dostanete 0 = 0. V takovém případě budete muset použít algoritmus průsečíku 2D obdélníku.

Pak uvidím, jestli ta čára, která je v rovině obou obdélníků, prochází oběma obdélníky. Pokud ano, pak máte průsečík dvou obdélníků, jinak ne (nebo ne, možná jsem vynechal rohový kufřík v hlavě).

Chcete-li zjistit, zda čára prochází obdélníkem ve stejné rovině, najdu 2 průsečíky přímky a stran obdélníku (modelování pomocí rovnic čar) a pak se ujistěte, že body průsečíků jsou s rozsah.

To je matematický popis, bohužel nemám žádný kód, jak toho dosáhnout.

0
freespace

Zde je implementace přijaté odpovědi:

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

Jedná se o běžnou metodu, která se provádí po řádcích a kontroluje, zda se čáry protínají. Toto je kód v MATLABu. 

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

funkci InterX lze stáhnout z: https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function

Dalším způsobem, jak provést test, který je o něco rychlejší než použití testu separační osy, je použít algoritmus čísel vinutí (pouze na kvadrantech - ne součet úhlu, který je strašně pomalý) na každém vrcholu každého obdélníku (libovolně zvolena). Pokud některý z vrcholů má nenulové číslo vinutí, oba obdélníky se překrývají.

Tento algoritmus je poněkud delší, než test na separační ose, ale je rychlejší, protože vyžaduje pouze test s poloviční rovinou, pokud hrany kříží dva kvadranty (na rozdíl od až 32 testů metodou oddělující osy)

Algoritmus má další výhodu v tom, že může být použit pro testování překrytí libovolného polygonu (konvexní nebo konkávní). Pokud vím, algoritmus funguje pouze ve 2D prostoru.

0
Mads

Mám jednoduchší metodu, pokud máme 2 obdélníky:

R1 = (min_x1, max_x1, min_y1, max_y1)

R2 = (min_x2, max_x2, min_y2, max_y2)

Překrývají se pouze tehdy, když:

Překrytí = (max_x1> min_x2) a (max_x2> min_x1) a (max_y1> min_y2) a (max_y2> min_y1)

Můžete to udělat i pro 3D krabice, ve skutečnosti to funguje pro libovolný počet dimenzí.

0
BitFarmer

Dost bylo řečeno v jiných odpovědích, takže přidám pseudocode one-liner:

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

Implementoval jsem to takto:

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

Matice mB je libovolná matice afinní transformace, která převádí body v prostoru B na body v prostoru A. To zahrnuje jednoduchou rotaci a překlad, rotaci plus měřítko a plné afinní deformace, ale ne perspektivní deformace.

To nemusí být co nejoptimálnější. Rychlost nebyla velkým problémem. Zdá se však, že pro mě funguje dobře.

0
Robotbugs