Delaunay

Delaunay und Bildpunkt-Triangulierung

Der russische Mathematiker und Kristallograph Boris Delaunay (Boris Delone) entwickelte in den 1930ern ein Verfahren zur Triangulierung von Punktmengen. Es ist leicht zu verstehen, relativ effizient und erfreut sich bis heute in leichten Abwandlungen in der Gittererzeugung großer Beliebtheit.

Den Algorithmus testet fortschreitend Dreierpaare (A,B,C) von gegebenen Punkten der Ebene und prüft, ob der sie umschließende eindeutige Kreis (Circumcircle) keinen weiteren Punkt enthält. Wenn ja, dann bilden diese Punkte A, B und C ein minimales, nicht weiter durch andere Punkte zerlegbares Dreieck der gewünschten Triangulierung.

Wird diese Dreiecksbildung so lange durchgeführt, bis keine Punkte mehr im umschließenden Kreis anderer Punkte liegen und kein Punkt mehr isoliert steht, ist die Triangulierung abgeschlossen und die Menge aller gefundenen Dreiecke bildet eine zusammenhängede, lückenlose Kachelung der Punktemenge :D

Diese Implementierung ist in HTML5/Javascript geschrieben, erzeugt zufällige Punktemengen und ist inspiriert von einem Code von travellermap.com.

Achja: das Javascript ist außerdem in der Lage, den durchschnittlichen Farbwert eines Dreiecks zu ermitteln, wenn ein Hintergrundbild verwendet wird. Damit lassen sich Fotos in schicke Dreiecksparkettierungen umwandeln.

Zum Code geht's hier (Github).

Und zur Demo geht's hier. Sie kann auch SVG-Grafiken exportieren.

Im Übrigen findet die Berechnung des Hintergrundbildes dieser Webseite mittels einer Delaunay-Triangulierung statt. Boah, ist das nicht toll? Fünf Jahre nach der Gründung von Polygon-Berlin erkläre ich die Hintergrundgrafik!

Delaunay und Voronoi

Funfact: verbindet man nun in der Delaunay-Triangulierung die zentralen Punkte aller jeweils aneinandergrenzenden Dreiecke, so erhält man das Voronoi-Diagramm der Punktmenge (im unten abgebildeten Screenshot mit Paper.js). In der Kristallographie wird dieses Verfahren im 3-dimensionalen verwendet, um die Elementarkristalle von Festkörpern und Pulvern zu bestimmen. Toll, was?

To-do

Sind für ein Dreieck drei Farben vorgegeben — eine für jede Ecke, z.B. aus der Hintergrundgrafik —, so kann das Dreieck mit einem wunderschönen Dreier-Farbverlauf gezeichnet werden. Der Algorithmus ist hier auf kitsumegames.com beschrieben.

Das wäre toll, wenn die Dreiecke hier noch so gezeichnet werden. Müsste ich mal machen; mein nächstes To-do.

Verwendete Bibliotheken

* jQuery
* modifizierte Color.js von neolitec
* modifizierte delaunay.js
* dat.gui