Kreuzung von zwei konvexen Polygonen
Habe ich zwei konvexe Polygone. Polygone umgesetzt werden als zyklische Listen von Ihren Scheitelpunkten. So finden Sie eine Kreuzung dieser beiden Polygone?
Du musst angemeldet sein, um einen Kommentar abzugeben.
Sollte dies ausreichend für die einfache Nutzung; 10-20 Knoten und nicht neu berechnen jeden Rahmen. — O(n2)
Hier ein paar links:
Profitieren Sie von der Tatsache, dass beide Polygone konvex sind. Und mit diesem wissen können Sie erreichen O(n) Zeit, indem Sie die folgende sweep-line-Algorithmus:
Finden Sie die obersten Punkte in beiden Polygone. Einfachheit halber angenommen, Sie haben keine horizontalen Kanten. Erstellen Sie Listen von Kanten Beitrag zu den Linken und Rechten Grenzen eines Polygons.
Beim kehren auf die Ebene, die Sie speichern 4 Kanten.
left_edge_C1
,right_edge_C1
,left_edge_C2
,right_edge_C2
. Sie brauchen keine komplexe zu strore die Kanten, denn es gibt nur vier von Ihnen. Finden Sie nächste Veranstaltung Punkt nur durch Durchlaufen aller möglichen Optionen.Bei jeder Veranstaltung zeigen einige Rand erscheinen an der Grenze Ihrer Kreuzung. Grundsätzlich, bei jeder Veranstaltung Punkt können Sie einen von drei Fällen (siehe pic.).
event point
bedeutet?Neben @Yola ist schön plane-sweep Beschreibung,
es ist eine linear-Zeit-Algorithmus beschrieben in
die " Computational Geometry in C, Kapitel 7. Und C & Java-code verfügbar ist (unter dem gleichen link). Es gibt mehrere knifflige entarteten Fällen, z.B., wenn die zwei Polygone schneiden sich in einem Punkt, oder die Kreuzung ist ein segment.