Karten aus Voronoi-Netzwerken

vorhergehende Artikel in: Java Numerik
15.03.2022

Ich habe bereits vor einiger Zeit über Methoden zur Erzeugung von Karten - etwa Stadtplänen oder Labyrinthen zum Beispiel für Computerspiele berichtet.

Ich habe mich aber bei beiden verlinkten Ergebnissen an der Regularität, die immer noch darin enthalten war gestört: Die Grundlage für diese Ergebnisse war immer ein Gitter von miteinander verbundenen Rechtecken. Ich wollte von dieser Beschränkung loskommen und dachte an Voronoi-Polygone als Grundlage für solche Generatoren statt der üblichen Rechtecke.

Man benötigt aber die explizite parametrische Form der Polygone - oder anders gesagt: die Eckpunktkoordinaten, um sie als Grundlage eines Graphen zur weiteren Bearbeitung nutzen zu können. Es stellte sich bei meinen Recherchen heraus, dass genau diese Form aber nicht einfach erhältlich ist. Ich fand zwar einige Algorithmen, die Voronoi-Polygone erzeugen, die dann aber genau die Koordinaten der Eckpunkte nicht als Ergebnis haben, sondern den zugrundeliegenden Vektorraum einfach nur partitionieren.

Da ich (vorerst) nur an zweidimensionalen Vektorräumen Interesse hatte dachte ich mir, dass es doch möglich sein müsste, einen eigenen Algorithmus zu implementieren. Dabei fing ich natürlich nicht von vorne völlig neu an sondern stützte mich auf vorhandene Algorithmen.

Ich möchte das Vorgehen an einigen Illustrationen dokumentieren - Gehen wir zunächst von einigen zufällig generierten zweidimensionalen Punkten aus, die die Zentren der zu erzeugenden Voronoi-Polygone darstellen sollen:

Screenshot Zufällig erzeugte Punkte

Für diese Punkte wird anschließend mittels des Bowyer-Watson-Algorithmus die Delauney Triangulation berechnet - das Ergebnis ist ein Netzwerk von Dreiecken wie hier dargestellt:

Screenshot Ergebnis der Delauney Triangulation

Für jedes der im Netzwerk enthaltenen Dreiecke wird anschließend der Umkreis bestimmt:

Screenshot Umkreise der durch die Delauney Triangulation gewonnenen Dreiecke

Die Mittelpunkte dieser Umkreise können miteinander verbunden werden - Dadurch ergeben sich Liniensegmente, die genau den Begrenzungen der gesuchten Voronoi-Polygone entsprechen:

Screenshot Seiten der Vornoi-Polygone

Man sieht aber leicht, dass durch dieses Verfahren nicht alle benötigten Begrenzungen der Voronoi-Polygone gefunden werden können. Daher habe ich folgende Ergänzungen zum Algorithmus hinzugefügt: Zunächst werden die Außenkanten des als Graph aufgefassten Delauney Triangulationsergebnisses gesucht:

Screenshot Außenkanten des Graphen aus der Delauney Triangulation

Anschließend werden darauf die Mittelsenkrechten konstruiert:

Screenshot Mittelsenkrechte auf den Außenkanten

Anschließend wird der kürzere Abschnitt jeder Mittelsenkrechten (gemessen bis zum Rand) in die Menge der Begrenzungen der Voronoi-Polygone aufgenommen. Schließlich werden aus den Schnittpunkten dieser Mittelsenkrechten mit dem Rand weitere zusätzliche Begrenzungen für Voronoi-Polygone am Rand entlang aufgenommen - im nachfolgenden Bild sind diese dick und rot markiert:

Screenshot Himzufügen fehlender Begrenzungen für Voronoi-Polygone

Damit hat man eine geschlossene Darstellung aller Kanten aller enthaltenen Voronoi-Polygone und kann die Polygone selbst konstruieren:

Screenshot Voronoi-Polygone

Zwei Sonderfälle sind beim aktuellen Stand des Algorithmus noch nicht berücksichtigt: Falls die Außenkante des Graphen aus der Delauney Triangulation zu konkav wird, schlägt der vorgestellte Algorithmus fehl - das passiert immer dann, wenn sich zwei oder mehr der aus den Mittelsenkrechten gewonnenen zusätzlichen Polygonkanten schneiden. Ein weiterer bisher nicht behandelter Sonderfall tritt ein, wenn die Punkte den gesamten Eingangsraum nicht vollständig überdecken. Dafür müsste das Auswahlkriterium der Hälften der Mittelsenkrechten angepasst werden - es darf nicht mehr allein auf der Entfernung des Mittelpunkts von den Grenzen des Eingangsraumes abhängen.

Aktualisierung vom 15. März 2022

Der zweite der genannten Sonderfälle - die nicht vollständige Überdeckung des Eingangsraumes durch die Punkte - wurde inzwischen in der Implementierung adressiert!

Alle Artikel rss Wochenübersicht Monatsübersicht Github Repositories Gitlab Repositories Mastodon Über mich home xmpp


Vor 5 Jahren hier im Blog

  • CI/CD mit shellcheck

    13.10.2019

    Ich habe mich entschlossen, in meinen diversen Shell-Projekten shellcheck als Mittel zur Qualitätssicherung einzusetzen.

    Weiterlesen...

Neueste Artikel

  • Linux-System SBOM visualisiert als Graph

    In meinem $dayjob kam neulich die Frage auf, ob es möglich wäre, die aktuelle Softwareinstallation eines Linux-Systems als Software Bill of Materials (SBOM) zu exportieren.

    Weiterlesen...
  • Visualisierung von Datenmodellen als gerichtete Graphen

    Ich habe - motiviert durch meine Experimente zur Visualisierung von Paketabhängigkeiten in Linux-Installationen als interaktive Graphen - versucht, relationale Datenmodelle in ähnlicher Form zu visualisieren und dazu zwei Plugins für die sQLshell geschrieben.

    Weiterlesen...
  • Carl Sagan - Christmas Lectures at the Royal Institution

    Die Royal Institution hat in ihren Schätzen gegraben und die Christmas Lectures von Carl Sagan auf Youtube nochmals veröffentlicht. Meiner Ansicht nach unbedingt lohnenswert für alle, die Englisch verstehen!

    Weiterlesen...

Manche nennen es Blog, manche Web-Seite - ich schreibe hier hin und wieder über meine Erlebnisse, Rückschläge und Erleuchtungen bei meinen Hobbies.

Wer daran teilhaben und eventuell sogar davon profitieren möchte, muß damit leben, daß ich hin und wieder kleine Ausflüge in Bereiche mache, die nichts mit IT, Administration oder Softwareentwicklung zu tun haben.

Ich wünsche allen Lesern viel Spaß und hin und wieder einen kleinen AHA!-Effekt...

PS: Meine öffentlichen GitHub-Repositories findet man hier - meine öffentlichen GitLab-Repositories finden sich dagegen hier.