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

  • Zugriff auf Maps ohne Cast in Java

    22.11.2017

    Collections im Zusammenspiel mit Generics erlauben es, ohne Cast auf Elemente gleichen Typs typsicher zuzugreifen - was aber wenn man typsicher auf Elemente unterschiedlicher Typen in einer Collection zugreifen möchte, ohne zu casten? Hier die Vorstellung einer möglichen Antwort

    Weiterlesen...

Neueste Artikel

  • Nerd-Dictation Tests

    Ich habe vor einiger Zeit schon einmal mit Spracherkennung experimentiert und war damals enttäuscht - vielleicht aber auch deshalb, weil ich nur mäßig motiviert war und mich deshalb bereits früh abschrecken ließ, als nicht alles sofort so funktioniert hat wie ich es wollte. Nun habe ich das Thema nochmals aufgegriffen...

    Weiterlesen...
  • Struktur von PKIs re: Archivzeitstempel

    Hier nochmal eine Beleuchtung der Organisation einer Public Key Infrastructure (PKI) von einem (von mir) bisher nicht betrachteten Blickwinkel

    Weiterlesen...
  • Security QA mit Kotlin-Bibliotheken und Java

    Über die Probleme und Herausforderungen beim Unit-Testen im Security-Umfeld mit Kotlin-Bibliotheken...

    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.