Wie kann ich feststellen, ob zwei konvexe Polygone schneiden?

Question

Angenommen, es gibt eine Reihe von konvexen Polygonen auf einer Ebene, vielleicht eine Karte. Diese Polygone können gegeneinander stoßen und eine Kante teilen, aber nicht überlappen können.

Um zu testen, ob zwei Polygonen P und Q Überlappung zunächst kann ich jede Kante Test in P , um zu sehen, ob es mit jedem schneidet von die Kanten in F . Wenn ein Schnittpunkt gefunden wird, erkläre ich, dass P und F schneiden. Falls keine schneiden, ich dann für den Fall zu prüfen haben, dass P ist vollständig enthalten ist, durch F , und umgekehrt. Als nächstes gibt es den Fall, dass P == F . Schließlich gibt es noch den Fall, dass ein paar Kanten teilen, aber nicht alle von ihnen. (Die letzten beiden Fälle können wahrscheinlich als der gleichen allgemeinen Fall gedacht werden, aber das ist vielleicht nicht wichtig sein.)

Ich habe einen Algorithmus, der erkennt, wenn zwei Liniensegmente schneiden. Wenn die beiden Segmente kolinear sind, werden sie nicht als für meine Zwecke schneiden.

Habe ich richtig die Fälle aufgezählt? Irgendwelche Vorschläge für die Prüfung für diese Fälle?

Beachten Sie, dass ich nicht bin auf der Suche die neue konvexe Polygon zu finden, dass der Schnittpunkt ist, ich will nur wissen, ob ein Schnittpunkt vorhanden ist. Es gibt viele gut dokumentierten Algorithmen für die Kreuzung zu finden, aber ich brauche nicht durch all die Mühe zu gehen.

Answer 1

könnten Sie diesen Kollisionsalgorithmus :

  

Um in der Lage zu entscheiden, ob zwei konvexe Polygone sich schneiden (einander berühren) wir das Separieren Achsensatz verwenden können. Im Wesentlichen:

     

  
• Wenn zwei konvexe Polygone nicht schneiden sich, gibt es eine Linie, die zwischen ihnen passiert.
  
• Eine solche Linie besteht nur, wenn eine der Seiten eines der Polygone bildet eine solche Linie.
  

     

Die erste Aussage ist einfach. Da die Polygone beide konvex sind, werden Sie eine Linie mit einem Polygon auf der einen Seite zeichnen können, und das andere Polygon auf der anderen Seite, wenn sie sich schneid sind. Das zweite ist, etwas weniger intuitiv. Schauen Sie sich Abbildung 1. Sofern in der Nähe sided der Polygone parallel zueinander sind, wobei der Punkt, den sie am nächsten zueinander erhalten, ist der Punkt, wo eine Ecke eines Polygons am nächsten zu einer Seite des anderen Polygons wird. Diese Seite wird dann eine Trennachse zwischen den Polygonen bilden. Wenn die Seiten parallel sind, sind sie beide Achsen trennt.

     

     

Wie funktioniert das uns konkret helfen, zu entscheiden, ob das Polygon A und B schneiden? Nun, wir gehen nur über jede Seite jedes Polygons und prüfen, ob es eine Trennachse bildet. Um dies zu tun wir mit einigen grundlegenden Vektor Mathematik sein, um alle Punkte der beiden Polygone auf einer Linie zerquetschen, die senkrecht zur Potentialtrennlinie (siehe Abbildung 2). Jetzt das ganze Problem ist bequem 1-dimensional. Wir können einen Bereich bestimmen, in dem die Punkte für jedes Polygons liegen, und diese Linie ist ein Trennachse, wenn diese Bereiche nicht überlappen.

     

     

Wenn Sie nach jeder Zeile von beiden Polygonen Überprüfung, keine Trennung Achse gefunden wurde, es ist erwiesen, dass die Polygone schneiden und hat etwas dagegen zu tun.

Answer 2

• Wenn die Polygone immer konvex sind, berechnet zuerst den Winkel einer Linie von Mitte zu Mitte der Polygone gezeichnet. benötigen Sie können dann beseitigen zu Randsegmenten in der Hälfte des Polygons (n) 180 Grad weg von dem anderen Polygon (s).

testen

• , um die Kanten zu beseitigen, mit dem Polygon auf der linken Seite starten. nimmt das Liniensegment von der Mitte des Polygons, die senkrecht zu dem Liniensegment von der vorherige Kugel ist, und berühren beiden Seiten des Polygons. nennt dieses Liniensegment P, mit Scheiteln P1 und P2. Dann wird für alle Scheitel, wenn die x-Koordinate kleiner als P1.x und P2.x können, die Knoten in dem „sicheren bucket“ gehen.

• , wenn es nicht der Fall ist, müssen Sie überprüfen, um sicherzustellen, dass es auf der „sicheren“ Seite der Linie ist (nur überprüfen die y-Koordinaten zu)

-Wenn ein Liniensegment im Polygon hat alle Vertices in dem „sicheren bucket“ Sie können es ignorieren.

-Reverse der Polarität, so dass Sie "rechts orientierten" für das zweite Polygon sind.

Answer 3

Ihre Testfälle sollten funktionieren, da Sie den Fall sind überprüft, wo die Polygone überhaupt nicht schneiden (vollständig außerhalb oder vollständig innen), sowie der Teilschnittes gibt es irgendeine Form (Kanten immer schneiden, wenn es ist Überlappung).

Für die Prüfung, würde ich nur sicherstellen, dass jede mögliche Kombination zu testen. Die eine fehlende oben von dem, was ich sehe, ist eine einzige Kante geteilt, aber ein Poly in der anderen enthalten ist. Ich würde auch Tests für einige komplexere Poly Formen hinzufügen, von tri -.> Vielen Seiten versehen, nur als Vorsichtsmaßnahme

Auch, wenn Sie einen U-förmigen Poly haben, die völlig die Poly umgeben, aber nicht überlappen, glaube ich Ihr Fall damit umgehen würde, aber ich würde das als Kontrolle hinzufügen, wie gut.

Answer 4

Da altCognito bereits gab man eine Lösung, werde ich nur darauf hinweisen ein ausgezeichnetes Buch über Computational Geometry dass Sie interessieren könnte.

Answer 5

GJK Kollision a href <=" http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?&arnumber=2083 "rel =" nofollow noreferrer "> Erkennung sollte Arbeit .

Answer 6

Hier ist eine Idee:

• den Mittelpunkt jedes Polygons finden

• Die zwei Punkte jedes Polygons am nächsten zum Mittelpunkt des anderen. Sie werden benachbarte Punkte in konvexe Polygone sein. Diese definieren die nächsten Kante jedes Polygons, wollen wir die Punkte nennen {A, B} und {Y, Z}

• Hier finden Sie die Kreuzung der Linien AB und YZ. Wenn die Liniensegmente kreuzen (der Schnittpunkt auf AB liegt zwischen A und B), Ihre Polygone schneiden. Wenn AB und XY parallel ignorieren diese Bedingung, wird der nächste Schritt Falle das Problem.

• Es gibt einen weiteren Fall, dass Sie für, überprüfen müssen, was ist, wenn die Polygone stark genug schneiden, dass AB und XY vollständig aneinander vorbei sind und nicht wirklich schneiden. Diese abzufangen Fall berechnen die senkrechten Abstände von AB und XY zu jedem Polygonen Mittelpunkte. Wenn entweder Mittelpunkt näher an der Linie des Segments gegenüber Polygon Ihre Polygon Überlappung stark.

Answer 7

Es gibt mehr Möglichkeiten Kreuzung und / oder Eindämmung zwischen konvexen Polygonen zu erfassen. Es hängt alles davon ab, wie effizient Sie wollen, dass der Algorithmus zu sein. Betrachten wir zwei konvexen Polygonen und R B mit r und b Eckpunkten jeweils:

1. Sweep Linie basierten Algorithmus. Wie Sie erwähnen können Sie ein Sweep Linie Verfahren ausführen und die Intervalle von der Kreuzung des Polygone mit der geschwungenen Linie resultierenden halten. Wenn zu irgendeinem Zeitpunkt die Intervalle überlappen, dann schneiden sich die Polygone. Die Komplexität ist O ((r + b) log (r + b)) Zeit.
2. Rotating Zangen basierter Algorithmus. Siehe hier und hier für weitere Details. Die Komplexität ist O (r + b) Zeit.
3. Die effizientesten Methoden können hier und hier . Diese Algorithmen nehmen O (log r + log b) Zeit.