Wang Tiling implementiert und optimiert

vorhergehende Artikel in: Verschiedenes
11.03.2021

Ich habe mich - inspiriert durch Operation Mindfuck beim letztjährigen Chaos-Congress - mit Tilings in der Ebene beschäftigt.

Meine Beschäftigung danmit sah so aus, dass ich zunächst das von bleeptrack vorgestellte Erweiterung des Truchet-Tiling implementierte:

Screenshot Skalierbare Truchet Tilings

Der Gist, der dieses und ähnliche Bilder erzeugt ist hier zu finden.

Da ich mich inzwischen an dem Thema festgelesen hatte wollte ich als nächstes das Tiling mittels Wang-Dominos ausprobieren.

Mittels dieses Gists kam unter anderem dieses Ergebnis heraus:

Screenshot Wang Domino Tiling

Dieser Gist hat aber einen Nachteil: Ich bin hier naiv herangegangen und erzeuge diese Tilings, indem ich in jeder Zeile von links nach rechts fortschreite und für jede Zelle des Grid bestimme wie die obere und linke Kachel an der angrenzenden Seite eingefärbt ist. Anschließend bestimme ich alle möglichem Konfigurationen (Kacheln und Orientierungen), die unter Beachtung der Regeln an diese Stelle im Grid passen würden, wähle aus allen diesen Kandidaten zufällig einen aus und platziere ihn im Grid. Danach gehts mit der nächsten Position weiter. Tut man das so, laufen viele Versuche in Sackgassen, die dadurch definiert sind, dass sich Stellen im Grid finden, für die keine Kandidaten gefunden werden können. Im nächsten Bild sieht man für 1000 Tilings wie viele Fehlversuche zu verschmerzen waren: die Fehlversuche verden aufakkumuliert bis ein Tiling erfolgreich abgeschlossen werden konnte. Jedes Tiling bestand dabei aus horizontal 35 und vertikal 24 Kacheln:

Screenshot Darstellung der Anzahl von Versuchen für ein erfolgreiches Wang-Dominop Tiling mit dem naiven Verfahren.

Das Verfahren hatte klare Defizite - ich hatte aber keine Lust, hierfür ein komplettes Backtracking zu implementieren und legte das Ganze daher zur Seite. Später kam mir allerdings noch eine Idee, wie ich das Verfahren ohne Backtracking verbessern könnte. Nachdem ich diese Idee implementiert hatte, ergab sich - wieder für 1000 Renderings - die Anzahl der Fehlversuche wie folgt (man beachte die geänderte Y-Skala!):

Screenshot Darstellung der Anzahl von Versuchen für ein erfolgreiches Wang-Dominop Tiling mit dem verbesserten Verfahren.

Damit sank der "Ausschuss" deutlich ab - in einen Bereich, den ich tolerieren kann. Anschließend probierte ich noch einige Strategien aus wie etwa eine, die die Ausbildung großer zusammenhängender Farbflächen begünstigen sollte - Ergebnisse davon sind weiter unten zu sehen:

Im folgenden Bild kann man sehen, dass das Verhältnis von Fehlversuchen zu erfolgreichen Renderings von dieser Strategie nicht ungünstig beeinflusst wird:

Screenshot Darstellung der Anzahl von Versuchen für ein erfolgreiches Wang-Dominop Tiling mit dem verbesserten Verfahren und dem Versuch der Erzeugung möglichst großer zusammenhängender Farbflächen.


Screenshots

Artikel, die hierher verlinken

GeoJson Stadtplan-Generator

10.04.2021

Ich habe mich wieder einmal mit dem Generieren von Testdaten beschäfigt - dieses Mal sollte es eine Karte eines urbanen Gebietes, sozusagen ein Stadtplan sein.

Spielen mit Perspektive

14.03.2021

Und wieder habe ich mich mit einer netten kleinen Spielerei beschäftigt, aus der man hübsche Bilderchen erzeugen kann...

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


Vor 5 Jahren hier im Blog

  • Mandelbrot-Sets mittels Shadern berechnen

    17.05.2019

    Nachdem ich in den letzten verregneten Tagen auf Youtube in den Videos von Numberphile versunken bin, hat mich eines davon angestachelt, mich selbst mit dem Mandelbrotset zu beschäftigen. Als ich dann noch Code fand, der behauptete, das auf einer Graphikkarte mittels Shadern berechnen zu können, war es um mich geschehen...

    Weiterlesen...

Neueste Artikel

  • Erste Vor-Version eines Gis-Plugin für die sQLshell

    Wie bereits in einem früheren Artikel erwähnt plane ich, demnächst ein Plugin für die sQLshell anzubieten, das eine Visualisierung von Daten mit räumlichem Bezug im Stil eines Geoinformationssystems erlaubt.

    Weiterlesen...
  • bad-certificates Version 2.1.0

    Das bereits vorgestellte Projekt zur automatisierten Erzeugung von Zertifikaten mit allen möglichen Fehlern hat eine Erweiterung erfahren und verfügt über ein Partnerprojekt - beide sind nunmehr in der Version 2.1.0 freigegeben

    Weiterlesen...
  • SQLite als Geodatenbank

    Wie bereits in einem früheren Artikel beschrieben treibe ich derzeit Anstrengungen voran, die sQLshell attraktiver für Nutzer zu machen, die mit Geodatenbanken arbeiten.

    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.