Zufallsgenerierte Polygone

Ausgehend von einer Menge von Punkten in der Ebene soll ein geschlossenes Polygon erzeugt werden. Wie können die Punkte verbunden werden, ohne dass sich zwei Polygonkanten überschneiden?

Zur Lösung dieser Aufgabe existiert eine Vielzahl von Algorithmen, von denen hier einige vorgestellt werden sollen.
Um die erzeugten Polygonformen zu veranschaulichen, können die Algorithmen in einem Applet ausprobiert werden. Dieses Applet sollte sich mittlerweile gestartet haben und als eigenständiges Fenster sichtbar sein.

Im unteren Teil dieser Seite gibt es eine Beschreibung des Applets.


Die Algorithmen

Folgende Algorithmen werden hier vorgestellt : Laufzeitangaben beziehen sich auf die Größe n der Punktmenge.

ConvexBottom


Laufzeit: O(n log n)

Ein recht einfacher Algorithmus, der Polygone erzeugt, die eine halbkonvexe Form aufweisen (hier einen konvexen "Boden", daher der Name).
Die Idee zu diesem Algorithmus stammt aus [1].

Zunächst werden die beiden Extrempunkte in Bezug auf die x-Koordinate bestimmt, also die beiden Punkte mit kleinsten bzw. größtem x-Wert. Diese werden durch eine imaginäre Gerade verbunden, die die Punktmenge somit in eine obere und untere Hälfte teilt.
Nun wird die konvexe Hülle der unteren Hälfte berechnet und dann die imaginäre Gerade wieder entfernt. Man hat nun bereits den konvexen Boden des Polygons berechnet.
Alle übriggebliebenen Punkte, die nicht in der Hülle enthalten sind, werden nun gemäß ihrer x-Koordinate von links nach rechts sortiert und in dieser Reihenfolge verbunden. Die beiden Extrempunkte werden noch mit dem konvexen Boden verbunden.

Das so entstandene Polygon weist neben dem konvexen Boden typischerweise ein "Zick-Zack-Muster" von Kanten oberhalb des Bodens auf.
Denkbar sind neben einem ConvexBottom natürlich auch Varianten mit einem konvexen "Dach" oder einer konvexen linken oder rechten Seite bei gleicher Laufzeit.

SpacePartitioning


Laufzeit: O(n2) im worst case; bei balancierter Rekursion O(n log n)

Die Punktmenge wird rekursiv so in je zwei Mengen unterteilt, dass deren konvexe Hüllen disjunkt sind und lediglich eine Kante gemeinsam haben. So ergeben sich im günstigsten Fall log(n) Rekursionen. Sobald eine Teilmenge nur noch aus zwei Punkten besteht, terminiert die Rekursion und erzeugt eine neue Polygonkante.

Details zur Berechnung können in [2] nachgeschlagen werden.

Die erzeugten Polygone sind meistens recht stark verzweigt und verwinkelt; es ergeben sich sowohl konvexe Formen als auch solche, die den von SteadyGrowth erzeugten Formen ähnlich sind.

SteadyGrowth


Laufzeit: quadratisch in O(n2)

SteadyGrowth (Quelle: [2]) erzeugt ein einfaches Polygon, indem ein Startpolygon aus einer Teilmenge der Punktmenge sukzessiv erweitert wird, bis alle Punkte der Punktmenge im Polygon enthalten sind.

Als Startpolygon werden drei Punkte der Punktmenge derart gewählt, dass die konvexe Hülle dieser drei Punkte keine weiteren Punkte der Punktmenge enthält.
In jedem der folgenden Iterationsschritte wird nun ein Punkt s gewählt derart, dass durch Hinzufügen von s die neue konvexe Hülle wiederum keine der übrigbleibenden Punkte enthält. Es wird eine Kante (u, v) des Polygons gesucht, die von s vollständig sichtbar ist, und durch die Kette (u, s, v) ersetzt. Somit wird das Polygon um den Punkt s erweitert.

SteadyGrowth liefert typischerweise Polygone, die sich von einem Zentrum aus in zwei bis drei Richtungen erstrecken und dabei sehr verwinkelt sind.

TwoOptMoves


Laufzeit: O(n4)

[2] beschreiben mit 2-opt Moves, zusammengefasst, einen Algorithmus, der aus einem zufälligen Polygon der Punktmenge (wie es z.B. durch Random entsteht) solange sich überkreuzende Kanten ersetzt, bis ein einfaches Polygon entsteht.

Wie in der Abbildung zu sehen, wird ein Paar sich überkreuzender Kanten (s, t), (u, v) gesucht und durch z.B. das Paar (s, v), (u, t) ersetzt, um die Überkreuzung zu entfernen. Nach [2] werden maximal O(n3) solche Ersetzungen durchgeführt, was die hohe Laufzeit erklärt.

Die erzeugten Polygone sind bei genügend großer Punktanzahl stark verzweigt.
Eine Besonderheit dieses Algorithmus ist, dass er jedes einfache Polygon erzeugen kann, das mit einer gegebenen Punktmenge möglich ist.

TwoPeasants


Laufzeit: O(n log n)

Ein Algorithmus mit einem seltsamen Namen (peasant: Bauer), der sich laut [1] von der Art und Weise ableitet, die im ländlichen Italien zum Einzäunen von Weiden angewandt werden soll...

Ähnlich wie in ConvexBottom werden zunächst die Punkte mit kleinster bzw. größter x-Koordinate ermittelt und durch eine imaginäre Linie verbunden, wodurch eine obere und untere Punktmengenhälfte entsteht. Das weitere Vorgehen erfolgt in zwei Schritten:
Zunächst wird nur die obere Hälfte der Punktmenge betrachtet; ausgehend vom linken Extrempunkt wird jeweils der aktuelle Punkt mit dem am nächsten liegenden Punkt verbunden, ohne die imaginäre Linie zu kreuzen, bis der rechte Extrempunkt erreicht ist.
Dann wird analog von rechts nach links für die untere Hälfte der Punktmenge vorgegangen, bis der linke Extrempunkt wieder erreicht ist.

Im Allgemeinen erhält man auf diese Weise ein in der Form recht "ausgeglichenes" einfaches Polygon. Der Algorithmus ähnelt der Art und Weise, wie ein Mensch intuitiv auf dem Papier eine Punktmenge zu einem einfachen Polygon verbinden würde.

Random


Laufzeit: linear in O(n)

Dieser einfachste Algorithmus wird lediglich der Vollständigkeit halber aufgeführt.

Die Punktmenge wird in zufälliger Reihenfolge durchlaufen, vorherige Punkt wird mit dem jeweils aktuellen Punkt verbunden. Nach dem Durchlauf wird das Polygon geschlossen.

Es entsteht so ein geschlossenes Polygon, das allerdings Überschneidungen aufweisen kann.


Das Applet

[Applet kann nicht gestartet werden]

Bei einem Klick auf den Startknopf öffnet sich ein separates Fenster mit dem RandomPolygon2Tool. Neben der reinen Visualisierung bietet dieses Tool die Möglichkeit, ein erzeugtes Zufallspolygon in den Editor zu importieren (Button Import), was hier natürlich nicht möglich ist.

Unterhalb des Import-Buttons finden sich sechs verschiedene Buttons, die jeweils den Namen eines der vorgestellten Algorithmen tragen und bei Betätigung ein neues Polygon der betreffenden Art erzeugen.
Das Zeichenfenster in der Mitte stellt das erzeugte Polygon dar. Die drei Zoom-Buttons oberhalb ermöglichen eine Vergrößerung bzw. Verkleinerung der Ansicht.

Unterhalb der Algorithmus-Buttons befinden sich Einstellmöglichkeiten für das Intervall der Punktanzahl und die Größe des Polygons:
Das Punktanzahl-Intervall legt fest, wie viele Zufallspunkte erzeugt werden; die Zahl der Punkte liegt im Bereich des Intervalls.
Die Größenangaben sind maximale Werte für die Breite und Höhe des Polygons.


Literatur:

[1]:PoPS - Polygonizations of Point Sets.
[2]:Auer, Held. Heuristics for the Generation of Random Polygons. In Proc. 8th Canad. Conf. Comput. Geom., pp 38-44, Ottawa, Canada, Aug 1996. Carleton University Press.
Siehe dazu auch: Generating random simple polygons [an open problem] - How quickly can we generate a random simple polygon with a given set of vertices?