Gewichtete Voronoi Diagramme und Variable Offsets

Ein Voronoi Diagramm ist eine geometrische Datenstruktur aus dem Bereich der Algorithmischen Geometrie, welche ein weites Anwendungsfeld in Wissenschaft und Praxis aufweist. Kurz gesagt unterteilt ein Voronoi Diagramm einer Menge von Eingabepunkten die Ebene in überlappungsfreie Teilbereiche, wobei jeder Teilbereich jene Punkte der Ebene enthält, welche näher beim den Bereich definierenden Eingabepunkt als bei irgendeinem anderen Eingabepunkt liegen. Verschiedene Verallgemeinerungen von Voronoi Diagrammen sind bekannt, wie etwa modifizierte Abstandsbegriffe, Gewichte oder Geradensegmente zusätzlich zu den Punkten als Eingabeobjekte. Die Berechnung von Parallelkurven von Polygonzügen gehört zu den bekannteren Anwendungen von Voronoi Diagrammen. In vorausgegangener Arbeit haben wir gewichtete Skelettstrukturen untersucht und sie als Werkzeug für die Charakterisierung und effiziente Berechnung von Parallelkurven von allgemeinen planaren Unterteilungen. Parallelkurven können unter anderem zur Modellierung von Pinselstrichen verwendet werden aber nur dann, wenn der Pinsel mit gleichmäßigem Druck gegen den Untergrund bewegt wird. Denn sonst überdeckt der Pinsel einen Bereich, dessen Dicke nicht konstant ist. Ein derartiger Bereich ist als Parallelkurve mit nicht-konstantem Radius bekannt ist und die konventionellen Algorithmen zur Berechnung von Parallelkurven sind nicht mehr anwendbar. In diesem Projekt wollen wir eine Verallgemeinerung von Voronoi Diagrammen untersuchen, welche die Berechnung derartiger Parallelkurven erlaubt: verallgemeinerte gewichtete Voronoi Diagramme. Vereinfacht gesagt ist unser Ziel, die mathematischen Grundlagen für eine erstmalige algorithmische Behandlung von Parallelkurven mit nicht-konstantem Radius zu schaffen. Dazu wollen wir verallgemeinerte gewichtete Voronoi Diagramme untersuchen. Abgesehen von der Erarbeitung einer soliden algorithmischen Basis für gewichtete verallgemeinerte Voronoi Diagramme und Parallelkurven mit nicht-konstantem Radius werden wir unser Augenmerk auch ganz wesentlich der Überführung unserer Algorithmen in entsprechende eigenständige Programmmodule widmen. Die Bereitstellung von zuverlässigen und effizienten Programmen ist nicht nur ein wichtiger Dienst an der Forschergemeinde, sondern stellt insbesondere für Anwender in Industrie und Gewerbe meist eine wesentliche und unabdingbare Voraussetzung für den tatsächlichen Einsatz neuer Algorithmen dar. Wobei unsere Algorithmen natürlich nicht auf die Algorithmische Geometrie beschränkt sind, sondern neben CAD/CAM, Architektur und GIS in vielen technisch/naturwissenschaftlichen Gebieten zum Einsatz kommen können.

Unter Algorithmischer Geometrie versteht man ein Teilgebiet der (Theoretischen) Informa- tik, das sich mit der effizienten algorithmischen Lösung geometrisch formulierter Probleme beschäftigt. Dabei ist das sogenannte Voronoi Diagramm eine wichtige Datenstruktur, da sich mit seiner Hilfe effiziente Lösungen für etliche geometrische Fragestellungen erarbei- ten lassen. Die Anwendungen reichen von Werkzeugwegplanung im computergestützten Fertigen über die Rekonstruktion dreidimensionaler Objekte in der medizinischen Bildver- arbeitung, das Modellieren von Dachflächen in der Architektur bis zur Berechnung von Mittellinien von Flüssen und sogar dem Modellieren von Habitatzonen in der Zoologie. Voronoi Diagramme können gemäß der Prärie-Feuer Analogie definiert werden: Für ei- ne Menge S von Punkten der Ebene ("Prärie") starten wir gleichzeitig in allen Punkten ein Feuer. Wir nehmen an, dass sich alle Feuer gleichförmig und gleich schnell in alle Richtun- gen ausbreiten. Dann gehört ein Punkt der Ebene zur Voronoi Region jenes Punktes von S dessen Feuerfront ihn zuerst erreicht. Punkte, wo zwei Feuerfronten aufeinander treffen, gehören zu den Kanten des Voronoi Diagrammes. Wenn man zusätzlich multiplikative und additive Gewichte bei den Punkten erlaubt, dann sind die Geschwindigkeiten sowie die Startzeitpunkte der sich ausbreitenden Feuerfronten unterschiedlich. Dieses Prinzip kann auch auf eine Menge von Geradensegmenten, die sich nur in den Endpunkten schneiden, verallgemeinert werden. Es ergeben sich damit Feuerfronten, welche pro Geradensegment einer Fahrradkette ähnlich sind, und man erhält ein verallgemeinertes gewichtetes Voronoi Diagramm. In diesem Projekt haben wir die mathematischen und algorithmischen Details von ver- allgemeinerten gewichteten Voronoi Diagrammen erarbeitet. Weiters haben wir uns mit der effizienten Berechnung einzelner (Feuer-)Fronten beschäftigt. Wir haben unsere Algo- rithmen in der Programmiersprache C++ implementiert. Einige unserer Implementierun- gen basieren auf konventioneller Gleitkommaarithmetik gemäß IEEE 754, wogegen andere auf exakter Arithmetik beruhen und unter Einbindung der Computational Geometry Algo- rithms Library (CGAL) erstellt wurden. Unsere Implementierungen sind auf der Plattform GitHub unter GPL Lizenz frei und unentgeltlich verfügbar. (GitHub ist ein Onlinedienst, welcher Speicher für Software-Entwicklungsprojekte inklusive Versionsverwaltung auf sei- nen Servern bereitstellt.) Zum Zeitpunkt des Schreibens dieser Zusammenfassung hat unsere Arbeit bereits Auf- merksamkeit erregt und zu einem Folgeprojekt mit einer internationalen Firma geführt. Die große Anzahl an Anfragen zu derartigen Themen in der Vergangenheit gibt uns Zuver- sicht, dass unsere Ergebnisse auch diesmal breit gefächert in Wissenschaft und Wirtschaft ihre Anwendungen finden werden.