Delaunay Clustering für Aggregationen

Abstract

In dieser Arbeit wurden, am Beispiel von OSM-Gebäudedaten, Delaunay-Triangulierungen aller vorkommenden Cluster bestimmt. Für die Bestimmung der Cluster der Kruskal-Algorithmus für minimale Spannbäume verwendet wurde. Die vorgestellten Algorithmen lassen sich jedoch auf eine Vielzahl an möglichen Cluster-Aufteilungen generalisieren. Ziel der Berechnung der Delaunay-Triangulierungen ist es, die Form von Orten, Städten und Ländern dynamisch, mithilfe von 𝛼-Shapes, zu rendern. Es wurde eine Linearzeit-Routine für die Berechnung der Delaunay-Triangulierungen aller 𝑛-1 nicht trivialen Cluster gefunden. Linearzeit bezieht sich hierbei auf die Anzahl an verschiedenen Dreiecken 𝑘 über alle Triangulierungen hinweg, was der Ausgabegröße entspricht. Die Gesamtlaufzeit, unter der Verwendung des Kruskal-Algorithmus, liegt dann in 𝑂(𝑘 + 𝑛 · 𝑙𝑜𝑔(𝑛)). Durch die Ausführung auf echten Gebäudedaten konnte beobachtet werden, dass hier 𝑘 ungefähr linear mit 𝑛 wächst. Zudem wurde eine zweistufige Datenstruktur für Anfragen, die 𝛼-Shapes ausgibt, aufgesetzt. Da viele 𝛼-Shapes als unschön bezeichnet werden können, wurden mehrere Methoden vorgestellt, diese zu verhindern. Eine dieser Option benötigt keine weitere Vorverarbeitung und liefert für die Ausgabe auf realen Daten trotzdem schnelle Antwortzeiten.