Algorithmus zur Erkennung des Schnittpunkts zweier Rechtecke?

143

Ich suche nach einem Algorithmus, um festzustellen, ob sich zwei Rechtecke schneiden (eines in einem beliebigen Winkel, das andere nur mit vertikalen / horizontalen Linien).

Das Testen, ob sich eine Ecke von einer in der anderen befindet, funktioniert FAST. Es schlägt fehl, wenn die Rechtecke eine kreuzartige Form bilden.

Es scheint eine gute Idee zu sein, die Verwendung von Steigungen der Linien zu vermeiden, was spezielle Fälle für vertikale Linien erfordern würde.

user20493
quelle
Was ist, wenn Sie Ihrer Eckprüfung eine Prüfung hinzufügen, um festzustellen, ob sich das zweite Rechteck innerhalb der Grenzen (rechteckig) des abgewinkelten Rechtecks ​​befindet?
Wes P
In welcher Sprache wirst du das machen? Denn in Java gibt es integrierte Klassen, mit denen Sie dies tun können.
Martijn
Ich denke, Grafik-API und die meisten GUI-Bibliotheken (wie Swing) haben dies implementiert.
l_39217_l
das kann Fälle übersehen, in denen sie sich überlappen, aber keine Ecke innerhalb eines Rechtecks ​​ist
Florian Bösch
1
Diese Frage ist fast dieselbe wie: stackoverflow.com/questions/306316/… . Dies ist jedoch auf der Suche nach einer Lösung, die speziell für C ++ geeignet ist. Die akzeptierte Antwort ist auch ziemlich einfach und unkompliziert.
Silver Gonzales

Antworten:

162

Die Standardmethode wäre, den Trennachsentest durchzuführen (führen Sie eine Google-Suche durch).

Zusamenfassend:

  • Zwei Objekte schneiden sich nicht, wenn Sie eine Linie finden, die die beiden Objekte trennt. zB befinden sich die Objekte / alle Punkte eines Objekts auf verschiedenen Seiten der Linie.

Das Schöne ist, dass es ausreicht, nur alle Kanten der beiden Rechtecke zu überprüfen. Wenn sich die Rechtecke nicht überlappen, ist eine der Kanten die Trennachse.

In 2D können Sie dies ohne Verwendung von Steigungen tun. Eine Kante wird einfach als Differenz zwischen zwei Eckpunkten definiert, z

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

Sie können eine Senkrechte dazu erhalten, indem Sie sie um 90 ° drehen. In 2D ist dies einfach wie folgt:

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

Also keine Trigonometrie oder Steigungen beteiligt. Eine Normalisierung des Vektors auf Längeneinheit ist ebenfalls nicht erforderlich.

Wenn Sie testen möchten, ob sich ein Punkt auf der einen oder anderen Seite der Linie befindet, können Sie einfach das Punktprodukt verwenden. Das Schild zeigt Ihnen, auf welcher Seite Sie stehen:

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

Testen Sie nun alle Punkte des Rechtecks ​​A gegen die Kanten des Rechtecks ​​B und umgekehrt. Wenn Sie eine Trennkante finden, schneiden sich die Objekte nicht (vorausgesetzt, alle anderen Punkte in B befinden sich auf der anderen Seite der Kante, auf die geprüft wird - siehe Zeichnung unten). Wenn Sie keine Trennkante finden, schneiden sich entweder die Rechtecke oder ein Rechteck ist im anderen enthalten.

Der Test funktioniert übrigens mit allen konvexen Polygonen.

Änderung: Um eine Trennkante zu identifizieren, reicht es nicht aus, alle Punkte eines Rechtecks ​​gegen jede Kante der anderen zu testen. Die Kandidatenkante E (unten) würde als solche als Trennkante identifiziert, da alle Punkte in A in derselben Halbebene von E liegen. Sie ist jedoch keine Trennkante, da die Eckpunkte Vb1 und Vb2 von B sind sind auch in dieser Halbebene. Es wäre nur eine Trennkante gewesen, wenn dies nicht der Fall gewesen wäre http://www.iassess.com/collision.png

Nils Pipenbrinck
quelle
2
Dieser Algorithmus funktioniert nicht in allen Fällen. Es ist möglich, das zweite Rechteck um 45 Grad zum ersten Rechteck gedreht und entlang der Diagonale versetzt zu platzieren, sodass es die obigen Schnittpunkttests erfüllt, sich jedoch nicht schneidet.
Skizz
6
Skizz, überprüfe alle acht Kanten. Wenn die Objekte nicht schneidet eine der acht Kanten wird sie voneinander trennen. Warum postest du kein Bild, das deinen Fall zeigt? Ich kann Ihnen die Achse zeigen ..
Nils Pipenbrinck
2
Mein Fehler, es kommt mit diesem Zustand zurecht.
Skizz
2
Das Bild ist jetzt tot (
John Dvorak
2
Ich hatte große Probleme, dies zu visualisieren, also habe ich neu erstellt, wie das Bild, auf das verwiesen wird, meiner Meinung nach aussah. imgur.com/bNwrzsv
Rjdlee
16

Schauen Sie sich grundsätzlich folgendes Bild an:


Wenn die beiden Felder kollidieren, überlappen sich die Linien A und B.

Beachten Sie, dass dies sowohl auf der X- als auch auf der Y-Achse erfolgen muss und beide überlappen müssen, damit die Rechtecke kollidieren.

Es gibt einen guten Artikel auf gamasutra.com, der die Frage beantwortet (das Bild stammt aus dem Artikel). Ich habe vor 5 Jahren einen ähnlichen Algorithmus verwendet und muss mein Code-Snippet finden, um es später hier zu veröffentlichen

Änderung : Der Satz über die Trennachse besagt, dass sich zwei konvexe Formen nicht überlappen, wenn eine Trennachse vorhanden ist (dh eine, bei der sich die gezeigten Projektionen nicht überlappen). Also "Eine Trennachse existiert" => "Keine Überlappung". Dies ist keine Doppelimplikation, daher können Sie das Gegenteil nicht abschließen.

m_pGladiator
quelle
1
Offensichtlich überlappen sich zwei Quadrate (0,0,1,1) und (0,3,1,4) nicht, aber ihre Projektionen auf der x-Achse überlappen sich vollständig. Beide Tests sind notwendig, die Kombination ist ausreichend.
MSalters
18
Es reicht nicht aus, dass sich die x- und y-Projektionen überlappen: Nehmen Sie z. B. die Rechtecke [(0,0), (0,3), (3,3), (3,0)] und [(2,5), (5,2), (7,4), (4,7)].
Joel in Gö
4
Ich stimme @Joel in Gö zu. Bei dieser Methode wird eine große Anzahl von Fällen übersehen, in denen sich die Rechtecke nicht überlappen, ihre projizierten Radien jedoch sowohl in x als auch in y.
Scottie T
5
Diese Antwort ist nicht falsch, aber irreführend. Es ist wahr, dass: Wenn die beiden Kästchen kollidieren, überlappen sich die Linien A und B. aber es ist auch wahr, dass: Wenn sich die Linien A und B überlappen, können die beiden Kästchen kollidieren oder nicht
matt brennt am
7
@floater: Ich würde sagen, es ist nicht nur falsch, sondern auch irreführend, was noch schlimmer ist.
BlueRaja - Danny Pflughoeft
4

Die Antwort von m_pGladiator ist richtig und ich bevorzuge es. Der Test der Trennachse ist die einfachste und Standardmethode zum Erkennen von Rechtecküberlappungen. Eine Linie, bei der sich die Projektionsintervalle nicht überlappen, wird als Trennachse bezeichnet . Die Lösung von Nils Pipenbrinck ist zu allgemein. Mit dem Punktprodukt wird geprüft , ob sich eine Form vollständig auf der einen Seite der Kante der anderen befindet. Diese Lösung könnte tatsächlich zu konvexen Polygonen mit n Kanten führen. Es ist jedoch nicht für zwei Rechtecke optimiert.

Der kritische Punkt der Antwort von m_pGladiator ist, dass wir die Projektion von zwei Rechtecken auf beiden Achsen (x und y) überprüfen sollten. Wenn sich zwei Projektionen überlappen, können wir sagen, dass sich diese beiden Rechtecke überlappen. Die obigen Kommentare zur Antwort von m_pGladiator sind also falsch.

Für die einfache Situation, wenn zwei Rechtecke nicht gedreht werden, präsentieren wir ein Rechteck mit Struktur:

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

Wir nennen das Rechteck A, B mit 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

Wenn eines der beiden Rechtecke gedreht wird, sind möglicherweise einige Anstrengungen erforderlich, um die Projektion auf die x- und y-Achse zu bestimmen. Definieren Sie struct RotatedRect wie folgt:

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

Der Unterschied besteht darin, wie die Breite 'jetzt etwas anders ist: widthA' für rectA: Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle) widthB 'für 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

Könnte auf eine GDC (Game Development Conference 2007) PPT verweisen www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt

Tristan
quelle
Warum benötigen Sie Math.abs () in "Math.abs (rectA.width + rectB.width)", um negative Breiten zu verarbeiten?
AlexWien
Die Trennachse ist nicht unbedingt eine Kompassrichtung, sie kann einen beliebigen Winkel haben.
Ben Voigt
Nicht gedrehte Rechtecke rectA (x = 0, y = 0, width = 1, height = 1) und rectB (x = 2, y = 0, width = 100, height = 1) schneiden sich nicht, aber Ihre Methode sagt dies aus sich schneiden. Mache ich etwas falsch?
Kagami Sascha Rosylight
4

In Cocoa können Sie leicht erkennen, ob das ausgewählte Aect Rect das Frame Rect Ihres gedrehten NSView schneidet. Sie müssen nicht einmal Polygone berechnen, Normalen wie solche. Fügen Sie diese Methoden einfach Ihrer NSView-Unterklasse hinzu. Beispielsweise wählt der Benutzer einen Bereich in der Übersicht des NSView aus und ruft dann die Methode DoesThisRectSelectMe auf, die das selectedArea rect übergibt. Die API convertRect: erledigt diesen Job. Der gleiche Trick funktioniert, wenn Sie auf das NSView klicken, um es auszuwählen. In diesem Fall überschreiben Sie einfach die hitTest-Methode wie folgt. Die API convertPoint: erledigt diesen Job ;-)

- (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
quelle
2
Dieser Code funktioniert nur für Rechtecke, die quadratisch zum Bildschirm sind. Das ist ein trivialer Fall. Die Annahme ist, dass es sich um Rechtecke handelt, die sich nicht in einem Winkel von 90 Grad zum Bildschirm oder zueinander befinden.
Duncan C
Wie ich in meinen Anwendungen überprüft und verwendet habe, funktioniert dieser Code für jedes gedrehte Rechteck. Unabhängig vom Rotationsgrad.
Leonardo
Dies beschreibt den Algorithmus jedoch nicht, sondern erwähnt nur eine Bibliothek, die ihn bereits verwendet.
Ben Voigt
2

Überprüfen Sie, ob eine der Linien eines Rechtecks ​​eine der Linien des anderen schneidet. Naive Liniensegmentkreuzung ist einfach zu codieren.

Wenn Sie mehr Geschwindigkeit benötigen, gibt es erweiterte Algorithmen für den Schnittpunkt von Liniensegmenten (Sweep-Line). Siehe http://en.wikipedia.org/wiki/Line_segment_intersection

Louis Brandy
quelle
4
Vorsichtig! Vergessen Sie nicht den Fall, in dem ein Rechteck ein anderes vollständig umschließt
Pitarou
2

Eine Lösung besteht darin, ein sogenanntes No-Fit-Polygon zu verwenden. Dieses Polygon wird aus den beiden Polygonen berechnet (konzeptionell durch Verschieben umeinander) und definiert den Bereich, für den sich die Polygone aufgrund ihres relativen Versatzes überlappen. Sobald Sie diesen NFP haben, müssen Sie einfach einen Einschlusstest mit einem Punkt durchführen, der durch den relativen Versatz der beiden Polygone gegeben ist. Dieser Inklusionstest ist schnell und einfach, aber Sie müssen zuerst den NFP erstellen.

Suchen Sie im Web nach No Fit Polygon und prüfen Sie, ob Sie einen Algorithmus für konvexe Polygone finden können (bei konkaven Polygonen wird dies VIEL komplexer). Wenn Sie nichts finden können, senden Sie mir eine E-Mail an howard dot J dot kann gmail dot com

Howard May
quelle
1

Hier ist, was ich denke, um alle möglichen Fälle zu kümmern. Führen Sie die folgenden Tests durch.

  1. Überprüfen Sie, ob sich die Eckpunkte von Rechteck 1 innerhalb von Rechteck 2 befinden und umgekehrt. Jedes Mal, wenn Sie einen Scheitelpunkt finden, der sich innerhalb des anderen Rechtecks ​​befindet, können Sie daraus schließen, dass sie sich schneiden und die Suche stoppen. Dies kümmert sich um ein Rechteck, das sich vollständig im anderen befindet.
  2. Wenn der obige Test nicht schlüssig ist, finden Sie die Schnittpunkte jeder Linie eines Rechtecks ​​mit jeder Linie des anderen Rechtecks. Sobald ein Schnittpunkt gefunden wurde, prüfen Sie, ob er sich innerhalb des imaginären Rechtecks ​​befindet, das durch die entsprechenden 4 Punkte erstellt wurde. Wann immer ein solcher Punkt gefunden wird, schließen Sie, dass sie sich schneiden und die Suche stoppen.

Wenn die obigen 2 Tests false zurückgeben, überlappen sich diese beiden Rechtecke nicht.

John Smith
quelle
0

Wenn Sie Java verwenden, verfügen alle Implementierungen der Shape-Schnittstelle über eine intersects- Methode, die ein Rechteck enthält.

Brendan Cashman
quelle
Leider benutze ich C #. Die Rectangle-Klasse verfügt über eine Contains () -Methode, jedoch nur für nicht gedrehte Rechtecke.
user20493
Die Methode intersects () ist ziemlich nutzlos, da sie boolesche Werte anstelle von intersection zurückgibt, denke ich.
ZZ 5.
0

Nun, die Brute-Force-Methode besteht darin, die Kanten des horizontalen Rechtecks ​​zu durchlaufen und jeden Punkt entlang der Kante zu überprüfen, um festzustellen, ob er auf oder in das andere Rechteck fällt.

Die mathematische Antwort besteht darin, Gleichungen zu bilden, die jede Kante beider Rechtecke beschreiben. Jetzt können Sie einfach herausfinden, ob eine der vier Linien von Rechteck A eine der Linien von Rechteck B schneidet, was ein einfacher (schneller) linearer Gleichungslöser sein sollte.

-Adam

Adam Davis
quelle
2
Das Problem mit Gleichungen ist, wenn Sie eine vertikale Linie haben, die eine unendliche Steigung hat.
user20493
Für jede Lösung gibt es Eckfälle.
Adam Davis
2
und ein Quadrat umschließt das andere vollständig.
Oliver Hallam
0

Sie können den Schnittpunkt jeder Seite des abgewinkelten Rechtecks ​​mit jeder Seite des achsenausgerichteten finden. Finden Sie dazu die Gleichung der unendlichen Linie, auf der jede Seite liegt (dh v1 + t (v2-v1) und v'1 + t '(v'2-v'1) im Grunde) und finden Sie den Punkt, an dem die Linien treffen sich, indem sie nach t auflösen, wenn diese beiden Gleichungen gleich sind (wenn sie parallel sind, können Sie dies testen) und dann testen, ob dieser Punkt auf dem Liniensegment zwischen den beiden Eckpunkten liegt, dh ist es wahr, dass 0 <= t ist <= 1 und 0 <= t '<= 1.

Dies gilt jedoch nicht für den Fall, dass ein Rechteck das andere vollständig abdeckt. Dies können Sie abdecken, indem Sie testen, ob alle vier Punkte eines Rechtecks ​​innerhalb des anderen Rechtecks ​​liegen.

HenryR
quelle
0

Folgendes würde ich für die 3D- Version dieses Problems tun :

Modellieren Sie die beiden Rechtecke als durch die Gleichungen P1 und P2 beschriebene Ebenen, schreiben Sie dann P1 = P2 und leiten Sie daraus die Schnittliniengleichung ab, die nicht existiert, wenn die Ebenen parallel sind (kein Schnittpunkt) oder in derselben Ebene liegen. In diesem Fall erhalten Sie 0 = 0. In diesem Fall müssen Sie einen 2D-Rechteckschnittalgorithmus verwenden.

Dann würde ich sehen, ob diese Linie, die in der Ebene beider Rechtecke liegt, durch beide Rechtecke verläuft. Wenn dies der Fall ist, haben Sie einen Schnittpunkt von 2 Rechtecken, andernfalls nicht (oder sollte es nicht sein, ich hätte möglicherweise einen Eckfall in meinem Kopf übersehen).

Um herauszufinden, ob eine Linie durch ein Rechteck in derselben Ebene verläuft, würde ich die 2 Schnittpunkte der Linie und die Seiten des Rechtecks ​​finden (Modellierung mithilfe von Liniengleichungen) und dann sicherstellen, dass die Schnittpunkte mit in übereinstimmen Angebot.

Das sind die mathematischen Beschreibungen, leider habe ich keinen Code, um das oben genannte zu tun.

Freiraum
quelle
Sie haben den Teil verpasst, in dem Sie sicherstellen müssen, dass ein Teil davon in beiden Rechtecken vorhanden ist, wenn Sie die planare Schnittlinie finden.
Lee Louviere
0

Eine andere Möglichkeit, den Test durchzuführen, der etwas schneller ist als die Verwendung des Trennachsentests, besteht darin, den Algorithmus für Wicklungszahlen (nur für Quadranten - keine Winkelsummierung, die fürchterlich langsam ist) für jeden Scheitelpunkt eines der Rechtecke (willkürlich gewählt) zu verwenden. Wenn einer der Eckpunkte eine Wicklungszahl ungleich Null hat, überlappen sich die beiden Rechtecke.

Dieser Algorithmus ist etwas langwieriger als der Trennachsentest, jedoch schneller, da nur dann ein Halbebenentest erforderlich ist, wenn Kanten zwei Quadranten kreuzen (im Gegensatz zu bis zu 32 Tests mit der Trennachsenmethode).

Der Algorithmus hat den weiteren Vorteil, dass er zum Testen der Überlappung eines beliebigen Polygons (konvex oder konkav) verwendet werden kann. Soweit ich weiß, funktioniert der Algorithmus nur im 2D-Raum.

Mads
quelle
3
Ich kann mich irren, aber prüft das nicht einfach, ob sich die Eckpunkte eines Rechtecks ​​in einem anderen befinden? Wenn ja, reicht dies nicht aus, da sich Rechtecke ohne Scheitelpunkte überlappen können.
Sinelaw
Können sie mit Rechtecken? Wie? Es scheint mir, dass mindestens ein Scheitelpunkt eines der Rechtecke auf dem anderen Rechteck liegen muss, damit sich zwei Rechtecke schneiden.
Duncan C
@ DuncanC: Ja, das können sie. Das Gegenbeispiel ist ein Kreuz und wurde sogar in der ursprünglichen Frage aufgeführt.
Ben Voigt
@ BenVoigt Dies ist ein sehr alter Thread, aber du hast absolut Recht.
Duncan C
0

Entweder fehlt mir etwas anderes, warum das so kompliziert machen?

Wenn (x1, y1) und (X1, Y1) Ecken der Rechtecke sind, gehen Sie wie folgt vor, um den Schnittpunkt zu finden:

    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
quelle
3
Sie vermissen, dass er möchte, dass einer um einen beliebigen Winkel gedreht wird.
Robotbugs
0

Ich habe es so implementiert:

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

Die Matrix mB ist eine affine Transformationsmatrix, die Punkte im B-Raum in Punkte im A-Raum umwandelt. Dies umfasst einfache Rotation und Translation, Rotation plus Skalierung und vollständige affine Verzerrungen, jedoch keine perspektivischen Verzerrungen.

Es ist möglicherweise nicht so optimal wie möglich. Geschwindigkeit war kein großes Problem. Allerdings scheint es für mich in Ordnung zu funktionieren.

Robotbugs
quelle
0

Hier ist eine Matlab-Implementierung der akzeptierten Antwort:

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
quelle
0

Dies ist die herkömmliche Methode. Gehen Sie Zeile für Zeile und prüfen Sie, ob sich die Linien schneiden. Dies ist der Code in MATLAB.

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

Die Funktion InterX kann heruntergeladen werden von: https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function

Siva Srinivas Kolukula
quelle
0

Ich habe eine einfachere Methode, wenn wir zwei Rechtecke haben:

R1 = (min_x1, max_x1, min_y1, max_y1)

R2 = (min_x2, max_x2, min_y2, max_y2)

Sie überlappen sich genau dann, wenn:

Überlappung = (max_x1> min_x2) und (max_x2> min_x1) und (max_y1> min_y2) und (max_y2> min_y1)

Sie können dies auch für 3D-Boxen tun, tatsächlich funktioniert es für eine beliebige Anzahl von Dimensionen.

BitFarmer
quelle
0

In anderen Antworten wurde genug gesagt, daher füge ich nur einen Pseudocode-Einzeiler hinzu:

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