Wie kann ich konvexe Polygone hinzufügen und subtrahieren?

Ich habe zwei konvexe 2D-Polygone, die sich überlappen . Ich suche einen Algorithmus, um sie zu subtrahieren und zu addieren . Das Ergebnis muss ein einzelnes konkaves Polygon oder (noch besser) eine Reihe der größten konvexen sein, die das konkave Ergebnis bilden (z. B. Dreiecke).

( Links: Die anfänglich überlappenden Polygone. Mitte: Das resultierende konkave Polygon nach dem Hinzufügen. Rechts: Eine Reihe von konvexen Polygonen, die das konkave Ergebnis bilden. Hier ist es aus Leistungsgründen besser, konvexe Polygone zu erhalten, die größer als ein Dreieck sind. Eine Subtraktion von zwei überlappende Polygone würden zu demselben Bild führen wie auf der linken Seite, wobei der überlappende Bereich jedoch nicht Teil des resultierenden Polygons ist.)

Wie kann ich das machen?

TL; DR Sie müssen boolesche Operationen mithilfe von BSP-Bäumen implementieren.

Nun, es scheint, dass wir hier über Konstruktive Festkörpergeometrie sprechen . Ich habe CSG auf kommerzieller Ebene implementiert, damit ich ein oder zwei Dinge darüber weiß.

Der klassische Artikel über CSG heißt Merging BSP Trees Yields Polyhedral Set Operations. Um ehrlich zu sein, ist es hier zu viel zu erklären, aber der Algorithmus befasst sich kurz gesagt mit Polygonen, die auf der gleichen Ebene liegen wie eine binäre Raumpartitionierung, also im Grunde genommen konstruieren ein BSP-Baum aus jedem Polygonnetz. Der zweite Schritt ist das Zusammenführen dieser BSP-Bäume. Sie nehmen einfach einen Baum und fügen ihn in den anderen ein. Der Algorithmus erklärt dann weiter, wie mit jedem Blattknoten zum Teilen und Subtrahieren der Knoten umgegangen wird. Knoten, die in der endgültigen Form nicht benötigt werden, werden entfernt, andere erhalten das entsprechende übergeordnete Element.

Aber warte! Das Papier handelt im Grunde genommen von Polygonnetzen und 3D-Ebenen, NEIN?

Der Algorithmus kann auf jede Dimension verallgemeinert werden. In Ihrem 2D-Fall ist es daher einfach, Liniensegmente anstelle von Ebenen als binäre Partitionen zu verwenden. Jedes Polygon wird also in einen BSP-Baum konvertiert, bevor die beiden zusammengeführt werden. Schließlich überqueren Sie den resultierenden Baum, um das endgültige Polygon zu erzeugen.

Beachten Sie, dass dieser Algorithmus und CSG im Allgemeinen das Rendern und Vernetzen von Flächen nicht direkt und nicht wirklich bereit zum Rendern ist. Daher müssen Sie die Flächen der endgültigen BSP-Bäume extrahieren. Ich finde Raytracing auch einfacher, um das CSG-Ergebnis zu rendern. Sie brauchen nur die Strahlen, um den Baum zu durchlaufen, anstatt die Flächen zu extrahieren und tatsächlich zu teilen (denken Sie daran, dass wir nur mit binären Partitionen arbeiten).

Bezüglich der numerischen Robustheit. Es ist gut zu bemerken, dass es zwei Arten von geometrischen Berechnungen gibt:

• Diejenigen , die auf dem Bau basieren, Sie bauen eine Form basierend auf dem Ergebnis einer früheren Operation. Zum Beispiel y = sqrt(x)und dann yin einer neuen Operation verwenden. Dies nennt man Konstruktion; Das Problem ist, dass sich numerische Fehler schnell ansammeln.
• Alternativ gibt es Operationen, die stattdessen Prädikate verwenden. Anstatt Konstruktionen zu verwenden, fragen Sie einfach, ob eine Bedingung wahr / falsch ist, und verwenden in verschiedenen Operationen denselben Wert. Zu den klassischen Tests gehören der Inircle-Test und der Orientierungstest. Dies ist auch ein Verdacht auf numerische Fehler, insbesondere wenn Sie einfache oder doppelte Genauigkeit verwenden, aber in der Regel bessere Ergebnisse erzielen. Es gibt andere Lösungen, die sich in Bezug auf Geschwindigkeit und Genauigkeit unterscheiden. Hier ist eine der jüngsten Arbeiten, in denen Konstruktionen vermieden werden, indem eine ebenenbasierte Geometrie verwendet wird, um genaue Ergebnisse zu erzielen. Ich werde auch aus der Zeitung zitieren:

Das Konzept der ebenenbasierten Darstellung von Polygonnetzen wurde erstmals von Sugihara und Iri beschrieben [SI89]. Diese Art der Darstellung bietet einen wichtigen Vorteil bei Aufgaben, bei denen die Topologie von Volumenkörpern, die durch Netze dargestellt werden, geändert werden muss, z

Und zum Schluss möchte ich hinzufügen, dass ich empfehlen würde, mit BSP-FAQs zu beginnen, wenn Sie Ihre BSP-CSG-Implementierung starten möchten .

Nach deinem Beispiel:

Wählen Sie einen Startscheitelpunkt auf Polygon A und prüfen Sie, ob sich Kanten im Uhrzeigersinn (oder gegen den Uhrzeigersinn) schneiden. Wenn es keine Schnittmenge gibt, fügen Sie dem resultierenden Polygon den vorherigen Scheitelpunkt hinzu. Wenn es einen Schnittpunkt gibt, fügen Sie den Schnittpunkt zu Ihrem resultierenden Polygon hinzu und beginnen Sie dann mit der Iteration über Polygon B in derselben Wicklungsreihenfolge. Machen Sie dasselbe und wechseln Sie erneut zu Polygon A, wenn eine Schnittmenge auftritt.

Nachdem Sie alle Eckpunkte für das neue Polygon akkumuliert haben, führen Sie einen Triangulationsalgorithmus für dieses Polygon aus. Die Ohrclip-Methode ist einfach zu implementieren, es gibt jedoch schnellere Optionen.

Wichtig: Stellen Sie sicher, dass sich der Scheitelpunkt, an dem Sie beginnen, nicht innerhalb des anderen Polygons befindet (prüfen Sie diesen Artikel auf Punkte in Polygontests).

Über jede Kante zu iterieren, um nach einem Schnittpunkt zu suchen, wäre ein O (n ^ 2) -Algorithmus. Sie können dies beschleunigen, indem Sie zuerst die Scheitelpunkte im anderen Polygon suchen, da die mit diesen Scheitelpunkten verknüpften Kanten die sich überschneidenden Kanten sind.

Wenn Sie ein konkaves Polygon möchten , wählen Sie einfach die nächste Kante zwischen den beiden Eingabepolygonen und fügen Sie zwei neue Kanten hinzu:

Konvex wird etwas komplizierter:

Ein Ansatz ist insofern iterativ, als er Scheitelpunkte vom zweiten zum ersten Polygon nacheinander hinzufügt und das erste Polygon in einen Container umwandelt, der alles umfasst.

Grundsätzlich:

• Durchlaufen Sie die Eckpunkte des zweiten Polygons.
• Durchlaufen Sie für jeden Scheitelpunkt V die Kanten des ersten Polygons:
• Finden sie eine „Reihe“ von Kanten , dass alle Gesicht der Scheitelpunkt
• Nehmen Sie das äußere Scheitelpunktpaar, das diesen Bereich definiert, und entfernen Sie alle Kanten in dem Bereich, der sie verbindet
• Zeichnen Sie zwei neue Segmente von diesen äußeren Scheitelpunkten zum neuen Scheitelpunkt (vom zweiten Polygon), und achten Sie dabei darauf, dass die neuen Kanten in die richtige Richtung weisen.
• Fahren Sie ab dem zweiten Polygon mit dem nächsten Scheitelpunkt fort

Hier ist ein Diagramm, das den Prozess für den ersten Scheitelpunkt veranschaulicht:

Eine schnellere Methode besteht darin, die Liste der Kanten auf jedem Polygon zu finden, die nicht dem anderen Polygon zugewandt sind, alles andere zu entfernen und die Endpunkte der verbleibenden Linienstreifen miteinander zu verbinden.

Vielleicht kann jemand anderes mit einem Subtraktionstipp mitreden.