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.
Antworten:
Die Standardmethode wäre, den Trennachsentest durchzuführen (führen Sie eine Google-Suche durch).
Zusamenfassend:
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
Sie können eine Senkrechte dazu erhalten, indem Sie sie um 90 ° drehen. In 2D ist dies einfach wie folgt:
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:
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
quelle
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.
quelle
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:
Wir nennen das Rechteck A, B mit rectA, rectB.
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:
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)
Könnte auf eine GDC (Game Development Conference 2007) PPT verweisen www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt
quelle
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 ;-)
quelle
Ü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
quelle
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
quelle
Hier ist, was ich denke, um alle möglichen Fälle zu kümmern. Führen Sie die folgenden Tests durch.
Wenn die obigen 2 Tests false zurückgeben, überlappen sich diese beiden Rechtecke nicht.
quelle
Wenn Sie Java verwenden, verfügen alle Implementierungen der Shape-Schnittstelle über eine intersects- Methode, die ein Rechteck enthält.
quelle
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
quelle
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.
quelle
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.
quelle
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.
quelle
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:
quelle
Ich habe es so implementiert:
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.
quelle
Hier ist eine Matlab-Implementierung der akzeptierten Antwort:
quelle
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.
Die Funktion InterX kann heruntergeladen werden von: https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function
quelle
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.
quelle
In anderen Antworten wurde genug gesagt, daher füge ich nur einen Pseudocode-Einzeiler hinzu:
quelle