Kreuzung von zwei konvexen Polygonen

Question

Ich habe zwei konvexe Polygone. Polygone werden als zyklische Listen ihrer Eckpunkte implementiert. Wie findet man eine Kreuzung dieser zwei Polygone?

Answer 1

For each edge V1-V2 in the first polygon, 
    Let H := Half-plane tangenting V1-V2, with the remaining 
     vertices on the "inside". 
    Let C := New empty polygon. 
    For each edge V3-V4 in the second polygon, 
     Let X := The intersection between V3-V4 and H. 
     If V3 inside H, and V4 is outside H then, 
      Add V3 to C. 
      Add X to C. 
     Else if both V3 and V4 lies outside H then, 
      Skip. 
     Else if V3 outside H, and V4 is inside H then, 
      Add X to C. 
     Else 
      Add V3 to C. 
    Replace the second polygon with C. 

Dies sollte für die einfache Verwendung ausreichen; 10-20 Vertices und nicht jeden Frame neu berechnen. — O (n)

---

Hier ein paar Links:

• Computer Graphics I – Polygon Clipping and Filling (pdf)
• rosettacode.org – Sutherland-Hodgman polygon clipping

Answer 2

Sie können davon profitieren, dass Beide Polygone sind konvex. Und mit diesem Wissen können Sie erreichen, O (n) Zeit mit dem folgenden Sweep-Line-Algorithmus:

Finden topeste Punkte in beiden Polygonen. Der Einfachheit halber haben Sie keine horizontalen Kanten. Erstellen Sie Listen mit Kanten, die zur linken und rechten Grenze eines Polygons beitragen.

Während Sie die Ebene nach unten kehren, speichern Sie 4 Kanten. left_edge_C1, right_edge_C1, left_edge_C2, right_edge_C2. Sie brauchen keinen Komplex, um die Kanten zu bearbeiten, weil es nur vier davon gibt. Sie können den nächsten Ereignispunkt finden, indem Sie einfach alle möglichen Optionen durchlaufen.

An jedem Ereignispunkt erscheint eine Kante an der Grenze ihres Schnittpunkts. Grundsätzlich können Sie an jedem Ereignispunkt einen der freien Fälle haben (siehe Bild).

Answer 3

Neben @ schöner Flugzeug-Sweep Beschreibung des Yola, gibt es eine beschriebene lineare Zeit Algorithmus in Computational Geometry in C, Kapitel 7 und C & Java-Code zur Verfügung steht (auf dem gleichen Link). Es gibt mehrere schwierige degenerierte Fälle, z. B. wenn sich die zwei Polygone an einem Punkt schneiden oder der Schnitt ein Segment ist.