Wie kann ich feststellen, ob sich ein Kreis und ein Rechteck im euklidischen 2D-Raum schneiden? (dh klassische 2D-Geometrie)
192
Wie kann ich feststellen, ob sich ein Kreis und ein Rechteck im euklidischen 2D-Raum schneiden? (dh klassische 2D-Geometrie)
Antworten:
Es gibt nur zwei Fälle, in denen sich der Kreis mit dem Rechteck schneidet:
Beachten Sie, dass das Rechteck hierfür nicht achsparallel sein muss.
(Eine Möglichkeit, dies zu sehen: Wenn keine der Kanten einen Punkt im Kreis hat (wenn alle Kanten vollständig "außerhalb" des Kreises liegen), kann der Kreis das Polygon nur dann noch schneiden, wenn er vollständig innerhalb des Kreises liegt Polygon.)
Mit dieser Einsicht wird etwa wie folgt arbeiten, wo die Kreismitte hat
P
und RadiusR
, und das Rechteck hat EckenA
,B
,C
,D
in dieser Reihenfolge (nicht vollständiger Code):Wenn Sie eine Geometrie schreiben, haben Sie wahrscheinlich bereits die oben genannten Funktionen in Ihrer Bibliothek. Andernfalls
pointInRectangle()
kann auf verschiedene Arten implementiert werden; Jeder der allgemeinen Punkte in Polygonmethoden funktioniert, aber für ein Rechteck können Sie einfach überprüfen, ob dies funktioniert:Und
intersectCircle()
ist auch einfach zu implementieren: Eine Möglichkeit wäre zu prüfen, ob der Fuß der Senkrechten vonP
zur Linie nahe genug und zwischen den Endpunkten liegt, und die Endpunkte ansonsten zu überprüfen.Das Coole ist, dass die gleiche Idee nicht nur für Rechtecke funktioniert, sondern auch für den Schnittpunkt eines Kreises mit einem einfachen Polygon - muss nicht einmal konvex sein!
quelle
So würde ich es machen:
So funktioniert das:
Das erste Linienpaar berechnet die absoluten Werte der x- und y-Differenz zwischen dem Mittelpunkt des Kreises und dem Mittelpunkt des Rechtecks. Dadurch werden die vier Quadranten zu einem zusammengefasst, sodass die Berechnungen nicht viermal durchgeführt werden müssen. Das Bild zeigt den Bereich, in dem der Mittelpunkt des Kreises liegen muss. Beachten Sie, dass nur der einzelne Quadrant angezeigt wird. Das Rechteck ist der graue Bereich, und der rote Rand umreißt den kritischen Bereich, der genau einen Radius von den Rändern des Rechtecks entfernt ist. Der Mittelpunkt des Kreises muss innerhalb dieses roten Randes liegen, damit der Schnittpunkt auftritt.
Das zweite Linienpaar eliminiert die einfachen Fälle, in denen der Kreis weit genug vom Rechteck entfernt ist (in beide Richtungen), dass kein Schnitt möglich ist. Dies entspricht dem grünen Bereich im Bild.
Das dritte Linienpaar behandelt die einfachen Fälle, in denen der Kreis nahe genug am Rechteck (in beide Richtungen) liegt, sodass ein Schnittpunkt garantiert ist. Dies entspricht den orangefarbenen und grauen Abschnitten im Bild. Beachten Sie, dass dieser Schritt nach Schritt 2 ausgeführt werden muss, damit die Logik sinnvoll ist.
Die verbleibenden Linien berechnen den schwierigen Fall, in dem der Kreis die Ecke des Rechtecks schneiden kann. Berechnen Sie zum Lösen den Abstand vom Mittelpunkt des Kreises und der Ecke und stellen Sie dann sicher, dass der Abstand nicht größer als der Radius des Kreises ist. Diese Berechnung gibt false für alle Kreise zurück, deren Mittelpunkt innerhalb des rot schattierten Bereichs liegt, und gibt true für alle Kreise zurück, deren Mittelpunkt innerhalb des weiß schattierten Bereichs liegt.
quelle
;)
circleDistance_x = abs(circle.x - (rect.x-rect.w/2)); circleDistance_y = abs(circle.y - (rect.y-rect.h/2));
Hier ist eine andere Lösung, die ziemlich einfach zu implementieren ist (und auch ziemlich schnell). Es werden alle Schnittpunkte erfasst, auch wenn die Kugel das Rechteck vollständig betreten hat.
Mit jeder anständigen Mathematikbibliothek kann dies auf 3 oder 4 Zeilen gekürzt werden.
quelle
Ihre Kugel und Ihr Rechteck schneiden sich IIF ist
der Abstand zwischen dem Kreismittelpunkt und einem Scheitelpunkt Ihres Rechtecks kleiner als der Radius Ihrer Kugel
ODER
der Abstand zwischen dem Kreismittelpunkt und einer Kante Ihres Rechtecks ist kleiner als der Radius Ihrer Kugel ( [ Punkt-Linie-Abstand ])
ODER
der Kreismittelpunkt liegt innerhalb des Rechtecks
Punkt-Punkt-Abstandes:
Punkt-Linie-Abstand:
Kreismittelpunkt innerhalb von Rect:
Nehmen Sie eine Trennachse: Wenn eine Projektion auf eine Linie vorhanden ist, die das Rechteck vom Punkt trennt, schneiden sie sich nicht
Sie projizieren den Punkt auf Linien parallel zu den Seiten Ihres Rect und können dann leicht feststellen, ob sie sich schneiden. Wenn sie sich nicht auf allen 4 Projektionen schneiden, können sie (der Punkt und das Rechteck) nicht schneiden.
Sie brauchen nur das innere Produkt (x = [x1, x2], y = [y1, y2], x * y = x1 * y1 + x2 * y2)
Ihr Test würde so aussehen:
Dies setzt kein achsenausgerichtetes Rechteck voraus und ist zum Testen von Schnittpunkten zwischen konvexen Mengen leicht erweiterbar.
quelle
Dies ist die schnellste Lösung:
Beachten Sie die Ausführungsreihenfolge, und die Hälfte der Breite / Höhe ist vorberechnet. Auch das Quadrieren erfolgt "manuell", um einige Taktzyklen zu sparen.
quelle
Die einfachste Lösung, die ich gefunden habe, ist ziemlich einfach.
Es funktioniert, indem der Punkt im Rechteck gefunden wird, der dem Kreis am nächsten liegt, und dann der Abstand verglichen wird.
All dies können Sie mit wenigen Vorgängen tun und sogar die Funktion sqrt vermeiden.
Und das ist es! Die obige Lösung geht von einem Ursprung oben links auf der Welt aus, wobei die x-Achse nach unten zeigt.
Wenn Sie eine Lösung für die Behandlung von Kollisionen zwischen einem sich bewegenden Kreis und einem Rechteck suchen, ist dies weitaus komplizierter und wird in einer anderen Antwort von mir behandelt.
quelle
Eigentlich ist das viel einfacher. Sie brauchen nur zwei Dinge.
Zunächst müssen Sie vier orthogonale Abstände vom Kreismittelpunkt zu jeder Linie des Rechtecks ermitteln. Dann schneidet Ihr Kreis das Rechteck nicht, wenn drei davon größer als der Kreisradius sind.
Zweitens müssen Sie den Abstand zwischen dem Kreismittelpunkt und dem Rechteckmittelpunkt ermitteln. Der Kreis befindet sich dann nicht innerhalb des Rechtecks, wenn der Abstand größer als die Hälfte der diagonalen Länge des Rechtecks ist.
Viel Glück!
quelle
Hier ist mein C-Code zum Auflösen einer Kollision zwischen einer Kugel und einem nicht achsenausgerichteten Feld. Es basiert auf einigen meiner eigenen Bibliotheksroutinen, kann sich aber für einige als nützlich erweisen. Ich benutze es in einem Spiel und es funktioniert perfekt.
quelle
Nehmen Sie zur Visualisierung den Nummernblock Ihrer Tastatur. Wenn die Taste '5' Ihr Rechteck darstellt, repräsentieren alle Tasten 1-9 die 9 Quadranten des Raums geteilt durch die Linien, aus denen Ihr Rechteck besteht (wobei 5 die Innenseite ist).
1) Wenn der Mittelpunkt des Kreises im Quadranten 5 liegt (dh innerhalb des Rechtecks), schneiden sich die beiden Formen.
Damit gibt es zwei mögliche Fälle: a) Der Kreis schneidet zwei oder mehr benachbarte Kanten des Rechtecks. b) Der Kreis schneidet mit einer Kante des Rechtecks.
Der erste Fall ist einfach. Wenn sich der Kreis mit zwei benachbarten Kanten des Rechtecks schneidet, muss er die Ecke enthalten, die diese beiden Kanten verbindet. (Das oder sein Zentrum liegt in Quadrant 5, den wir bereits behandelt haben. Beachten Sie auch, dass der Fall, in dem sich der Kreis mit nur zwei gegenüberliegenden Kanten des Rechtecks schneidet, ebenfalls abgedeckt ist.)
2) Wenn eine der Ecken A, B, C, D des Rechtecks innerhalb des Kreises liegt, schneiden sich die beiden Formen.
Der zweite Fall ist schwieriger. Wir sollten beachten, dass dies nur passieren kann, wenn der Mittelpunkt des Kreises in einem der Quadranten 2, 4, 6 oder 8 liegt Die entsprechende Ecke ist der nächstgelegene Punkt.)
Jetzt haben wir den Fall, dass der Mittelpunkt des Kreises in einem der 'Kanten'-Quadranten liegt und sich nur mit der entsprechenden Kante schneidet. Dann muss der Punkt an der Kante, der dem Mittelpunkt des Kreises am nächsten liegt, innerhalb des Kreises liegen.
3) Konstruieren Sie für jede Linie AB, BC, CD, DA senkrechte Linien p (AB, P), p (BC, P), p (CD, P), p (DA, P) durch den Mittelpunkt des Kreises P. For Wenn bei jeder senkrechten Linie der Schnittpunkt mit der ursprünglichen Kante innerhalb des Kreises liegt, schneiden sich die beiden Formen.
Für diesen letzten Schritt gibt es eine Verknüpfung. Wenn der Mittelpunkt des Kreises im Quadranten 8 liegt und die Kante AB die Oberkante ist, hat der Schnittpunkt die y-Koordinate von A und B und die x-Koordinate des Mittelpunkts P.
Sie können die vier Linienschnittpunkte konstruieren und prüfen, ob sie an den entsprechenden Kanten liegen, oder herausfinden, in welchem Quadranten P sich befindet, und den entsprechenden Schnittpunkt überprüfen. Beide sollten sich zu derselben booleschen Gleichung vereinfachen. Seien Sie vorsichtig, dass der obige Schritt 2 nicht ausschloss, dass sich P in einem der 'Eck'-Quadranten befindet. es suchte nur nach einer Kreuzung.
Bearbeiten: Wie sich herausstellt, habe ich die einfache Tatsache übersehen, dass # 2 ein Unterfall von # 3 oben ist. Schließlich sind auch Ecken Punkte an den Kanten. Eine gute Erklärung finden Sie in der Antwort von @ ShreevatsaR unten. Vergessen Sie in der Zwischenzeit die Nummer 2 oben, es sei denn, Sie möchten eine schnelle, aber redundante Überprüfung.
quelle
Diese Funktion erkennt Kollisionen (Schnittpunkte) zwischen Kreis und Rechteck. Er arbeitet in seiner Antwort wie die e.James-Methode, aber diese erkennt Kollisionen für alle Winkel des Rechtecks (nicht nur bis zur oberen Ecke).
HINWEIS:
aRect.origin.x und aRect.origin.y sind Koordinaten des linken unteren Rechteckwinkels!
aCircle.x und aCircle.y sind Koordinaten von Circle Center!
quelle
Ich habe eine Methode, die die teuren Pythagoras vermeidet, wenn sie nicht notwendig sind - dh. wenn sich Begrenzungsrahmen des Rechtecks und des Kreises nicht schneiden.
Und es wird auch für nicht-euklidische funktionieren:
dLat=(lat-circleY); dLon=(lon-circleX); normed=dLat*dLat+dLon*dLon
. Wenn Sie diese normDist-Methode verwenden, müssen Sie natürlich einenormedDist = dist*dist;
für den Kreis erstellenDen vollständigen BBox- und Circle- Code meines GraphHopper- Projekts anzeigen .
quelle
Ich habe eine Klasse für die Arbeit mit Formen geschaffen, die Ihnen Spaß machen
quelle
Hier funktioniert der modifizierte Code zu 100%:
Bassam Alugili
quelle
Hier ist ein schneller einzeiliger Test dafür:
Dies ist der achsenausgerichtete Fall, in dem
rect_halves
ein positiver Vektor von der Rechteckmitte zu einer Ecke zeigt. Der Ausdruck im Innerenlength()
ist ein Delta-Vektor voncenter
zu einem nächstgelegenen Punkt im Rechteck. Dies funktioniert in jeder Dimension.quelle
Es ist effizient, weil:
quelle
arbeitete für mich (nur arbeiten, wenn der Winkel des Rechtecks 180 ist)
quelle
Die Antwort von e.James ein wenig verbessern:
Dies subtrahiert
rect.w / 2
undrect.h / 2
einmal statt bis zu dreimal.quelle
Für diejenigen, die die Kreis- / Rechteckkollision in geografischen Koordinaten mit SQL berechnen müssen, ist
dies meine Implementierung in Oracle 11 des von e.James vorgeschlagenen Algorithmus .
Für die Eingabe sind Kreiskoordinaten, Kreisradius in km und zwei Eckpunktkoordinaten des Rechtecks erforderlich:
quelle
Funktioniert, habe das erst vor einer Woche herausgefunden und muss es jetzt testen.
quelle
quelle
Angenommen, Sie haben die vier Kanten des Rechtecks. Überprüfen Sie den Abstand zwischen den Kanten und dem Mittelpunkt des Kreises. Wenn dieser kleiner als der Radius ist, schneiden sich die Formen.
quelle
Wenn sich das Rechteck mit dem Kreis schneidet, sollten sich ein oder mehrere Eckpunkte des Rechtecks innerhalb des Kreises befinden. Angenommen, die vier Punkte eines Rechtecks sind A, B, C, D. Mindestens einer von ihnen sollte den Kreis schneiden. Wenn also der Abstand von einem Punkt zum Mittelpunkt des Kreises kleiner als der Radius des Kreises ist, sollte er den Kreis schneiden. Um die Entfernung zu ermitteln, können Sie den Satz von Pythagoras verwenden:
Diese Technik hat einige Grenzen. Aber es wird besser für die Spieleentwickler funktionieren. insbesondere Kollisionserkennung
Es ist ein gutes Update des Arvo-Algorithmus
quelle