So ermitteln Sie, ob zwei Kreissektoren miteinander überlappen

Question

Jeder Sektor kann als (x, y, r, a, d) dargestellt werden, wobei x, y die Position, r der Radius, d die Richtung ist. und a ist der Winkel. Angesichts dieser Informationen von zwei Kreissektoren, wie zu bestimmen, ob sie sich überschneiden? Gibt es einen effizienten Algorithmus, um es zu lösen? Vielen Dank!

Answer 1

Ich kenne eine sehr schnelle Möglichkeit, die Möglichkeit zu diskontieren, da ich das für Kreiskollisionen vorher benutzt habe.

Berechnen Sie den Abstand zwischen den beiden Zentren, und wenn das größer als die Summe der Radien ist, kann es keine Kollision geben. Aus Gründen der Effizienz, verwenden Quadratwurzel nicht, arbeiten nur direkt auf die quadrierten Werte:

if (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) > (r1 + r2) * (r1 + r2): 
    # No chance of collision. 

es aus für Kreissegmente Arbeiten wird ein wenig härter sein.

---

Ihre Wahl der Methode hängt davon ab, wie genau Sie es brauchen. Wenn Sie tatsächlich Mathe machen, benötigen Sie wahrscheinlich eine hohe Genauigkeit. Aber wenn du das zum Beispiel für ein Computerspiel tust, ist es nahe genug, um gut genug zu sein.

Wenn das der Fall wäre, würde ich in die Transformation des Bogens in eine Reihe von geraden Linien (deren Anzahl würde wahrscheinlich auf a, die "Ausbreitung" des Bogens - Sie könnten wahrscheinlich mit einem Weg kommen ein paar Linien für eine Ausbreitung von einem Grad von Bogen, aber das würde nicht gut funktionieren für 180 Grad).

Gerade Kollisionserkennung ist eine viel bekanntere Methode, obwohl Sie mit der Tatsache umgehen müssen, dass die Anzahl der Vergleiche schnell steigen kann.

---

Wenn Sie keine Liniensegmente verwenden möchten, folgt hier der folgende Prozess. Es verwendet einen Kreiskollisionsalgorithmus, um die Null-, einen oder zwei Kollisionspunkte für die vollständigen Kreise zu ermitteln, und prüft dann diese Punkte, um zu sehen, ob sie innerhalb beider Bögen liegen.

Führen Sie zuerst diese Überprüfung aus, um den Fall zu erkennen, in dem keine Kollision möglich ist. Wenn keine Kollision zwischen den Kreisen möglich ist, können die Bögen auch nicht kollidieren.

Zweitens, überprüfen Sie, ob die Kreise einen einzigen Kollisionspunkt haben. Das ist der Fall wenn:

(x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) == (r1 + r2) * (r1 + r2) 

innerhalb eines geeigneten Fehlerbereichs, natürlich. Wir sollten jetzt alle wissen, dass der Vergleich von Gleitkommazahlen für die Gleichheit eine Art von Deltavergleich verwenden sollte.

Wenn das der Fall ist, haben Sie einen Punkt zu überprüfen, und Sie können diesen Punkt leicht herausfinden. Es ist der Punkt r1 Einheiten entlang der Geraden (x1,y1)-(x2,y2) führenden oder, es zu betrachten als einen Bruchteil entlang dieser Linie bewegt:

(x1 + (x2-x1) * (r1+r2)/r1, y1 + (y2-y1) * (r1+r2)/r1) 

Ansonsten gibt es zwei Punkte zu überprüfen und Sie können die Antworten auf eine Verwendung Frage wie this one, um festzustellen, was diese beiden Punkte sind.

Nachdem Sie einige Kollisionspunkte haben, ist es eine much simpler method, um herauszufinden, ob diese Punkte auf einem Bogen sind, wenn man bedenkt, dass der Kandidatenpunkt auf beiden Bögen sein müssen, für sie, kollidieren nicht nur auf einer .

Answer 2

Da wir kreisförmige Sektoren haben, spielen Winkel und Richtung keine Rolle, wenn Sie dies in Echtzeit tun. Das Folgende gilt nur für vollständige Kreissektoren oder wenn beide Sektoren aufeinander zeigen.

Sie die nächsten Schritte folgen:

1) Finden Sie den Abstand zwischen jedem Sektor, 2) zu dieser Entfernung sowohl Radius subtrahieren, 3), wenn das Ergebnis negativ ist, es zu einer Kollision zwischen den beiden gewesen Sektoren. ansonsten ist es die Entfernung zur Kollision.

zum Beispiel haben wir zwei Sektoren, beide mit einem Radius von 50 Einheiten. der Abstand zwischen ihren Mittelpunkten ist 80. subtrahieren Sie 80-50-50 = -20, also wissen Sie, dass es eine Kollision 20 Einheiten in der Entfernung gegeben hat.

Wenn der Abstand 500, 500-50-50 = 400, ein positiver Wert ist, wissen Sie jetzt, dass diese beiden Sektoren 400 Einheiten voneinander entfernt sind.

jetzt, wenn die Kreise zu nahe sind, sagen wir, 1 Einheit auseinander, 1-50-50 = -99, was bedeutet, dass sie sich fast vollständig überlappen.

Für echte segmentierte kreisförmige Sektoren was Sie in den Kommentaren angegeben haben, sollten Sie paxdiablos oder Macs Antworten verwenden.

Answer 3

Es gibt zwei Schritte. Erstens ist es, herauszufinden, ob die beiden Zentren sind nahe genug zueinander, um eine Kollision zu ermöglichen, die durch den Vergleich der Abstand zwischen ihnen die Summe ihrer Radien getan werden kann:

if (((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) > ((r1 + r2) * (r1 + r2))) 
    // No collision. 

Dann müssen Sie prüfen, ob die Linie zwischen den Zentren fällt innerhalb der Bögen durch Ihre verschiedenen Winkeln definiert:

float angle1to2 = Math.atan2(y2 - y1, x2 - x1); 
if (angle1to2 < (d1 - a1/2) || angle1to2 > (d1 + a1/2)) 
    // No collision 
float angle2to1 = angle1to2 + Math.PI; 
if (angle2to1 < (d2 - a2/2) || angle2to1 > (d2 + a2/2)) 
    // No collision 

Wenn Sie durch diese Kontrollen erhalten, ohne die Möglichkeit einer Kollision ausgeschlossen ist, dann haben Sie erfolgreich eine Kollision erkannt wird.

Vorbehalt: Dieser Code wird überhaupt nicht getestet. Insbesondere müssen die atan2 Aufrufe abhängig von Ihrem Koordinatensystem etwas optimieren.

BEARBEITEN: gerade erkannt dies vermisst einen wichtigen Eckfall, wo die Bögen nicht aufeinander "zeigen", sondern immer noch überlappen. Will wiederkäuen und zurück ...