Theorie und Anwendung von Straight Skeletons in 2D und 3D

Ein Straight Skeleton ist eine Datenstruktur der algorithmischen Geometrie, welche seit Mitte der 90er Jahre untersucht wird und welche unzählige Anwendungen in Wissenschaft und Technik aufweist. Die breite Palette an Anwendungen steht in scharfem Kontrast zum Fehlen von adequaten Wissen über Straight Skeletons. Und dies wird besonders augenscheinlich, wenn man Verallgemeinerungen wie gewichtete Straight Skeleton und Straight Skeletons von dreidimensionalen Polyedern betrachtet. Für gewichtete Straight Skeletons ist nur wenig über deren geometrische Charakterisierung bekannt und effiziente Algorithmen zur praktischen Berechnung sind nicht verfügbar. Über die Geometrie von Straight Skeletons von Polyedern weiß man nahezu gar nichts. Algorithmen zur Berechnung sind nicht bekannt und selbst triviale Implementierungen zur Berechnung von Straight Skeletons von Polyedern existieren nicht. In den letzten Jahren konnten wir erfolgreich den sogenannten Motorcycle Graph generalisieren und als Werkzeug zur geometrischen Charakterisierung und effizienten Berechnung von gewöhnlichen Straight Skeletons von beliebigen planaren geradlinigen Graphen einsetzen. Unsere Vorarbeiten gipfelten in der Entwicklung und Implementierung von Bone, dem derzeit effizientesten Code zur Berechung von Straight Skeletons. Im vorliegenden Projektantrag legen wir dar, wie wir die gewonnenen Erkenntnisse dazu nutzen wollen, um das Konzept des Motorcycle Graphen auch auf (1) gewichtete Straight Skeletons und (2) Straight Skeletons von Polyedern zu erweitern. Unser Ziel ist, vergleichbare Resultate für diese beiden Arten von verallgemeinerten Straight Skeletons zu erreichen. Die Effizienzsteigerung bei der Berechnung von Motorcycle Graphen stellt dabei einen wichtigen Aspekt dar, der in Folge zur praktischen Beschleunigung aller weiteren Algorithmen führen wird, die auf Motorcycle Graphen aufbauen. Die Arbeit an diesen beiden Projektschwerpunkten soll durch weitere Themenkomplexe ergänzt werden, die damit in inhaltlichem Zusammenhang stehen. Erstens wollen wir Bone so erweitern, daß die sogenannte linearen Achse berechnet werden kann. Zweitens wollen wir die Rekonstruktion von Unstetigkeitsstellen von Straight Skeletons untersuchen, um kanonische Repräsentanten von Straight Skeletons bei Vorliegen numerisch ungenauer Daten zu ermitteln. Drittens werden wir die Charakterisierung von Straight Skeletons als untere Hüllfläche bestimmter planarer Flächen zu einer approximativen Berechnung mittels Graphik-Hardware nutzen. Abgesehen von der Erarbeitung einer soliden algorithmischen Basis für Straight Skeletons in 2D und 3D 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) Informatik, das sich mit der effizienten algorithmischen Lösung geometrisch formulierter Probleme beschäftigt. Dabei ist der sogenannte Straight Skeleton (geradliniges Skelett) eine wichtige Datenstruktur, da sich mit seiner Hilfe effiziente Lösung für etliche geometrische Fragestellungen erarbeiten lassen. Ein Straight Skeleton eines Polygons entsteht prozedural als das Ergebnis eines ge- dachten Schrumpfens des Polygons. Die Polyonkanten bewegen sich dabei parallel zum Ausgangspolygon mit gleicher konstanter Geschwindigkeit inwärts. Dadurch entsteht ein stetig kleiner werdendes Polygon, bei dem sich allerdings die Form ändern kann: Kanten können verschwinden, und mehrere Teilpolygone können entstehen. Der Straight Skeleton des Polygons entspricht nun der Vereinigung aller Pfade der Ecken des Polygons während dieses Schrumpfens. Dieses Prinzip kann auch auf eine Menge von Geradensegmenten (PSLG ), die sich nur in den Endpunkten schneiden, verallgemeinert werden. Wenn man nun zusätzlich multiplikative Gewichte bei den Geradensegmenten erlaubt, dann sind die Geschwindigkeiten der sich bewegenden Geradensegmente unterschiedlich and als Resultat erhält man ein (multiplikativ) gewichtetes Straight Skeleton. Analog bewirkt eine Einführung von additiven Gewichten, dass die Startzeitpunkte der Bewegungen unterschiedlich sind. In diesem Projekt wurde eine mathematische Charakterisierung von additiv und multiplikativ gewichteten Straight Skeletons erarbeitet. Insbesondere wurde eine Vorgehensweise entwickelt, um Mehrdeutigkeiten in der Interaktion der sich bewegenden Eingabesegmente aufzulösen. Für spezielle Klassen von Eingabepolygonen konvexe und sogenannte monotone Polygone konnten Algorithmen entworfen werden, deren Laufzeitkomplexitäten deutlich unter den besten bisher bekannten Resultaten liegen. Neben der Entwicklung von theoretischen Grundlagen samt Algorithmen (wie etwa Surfer) zur Berechnung von gewichteten Straight Skeletons wurden auch praxisorientiertere Anwendungen dieser Skelett-Strukturen untersucht. Etwa können wir auf der Basis von gewichteten Straight Skeletons Gebäudedächer für Gebäude mit polygonalem Grundriß vollautomatisch erzeugen. Die multiplikativen und additiven Gewichte resultieren dabei in Dachflächen unterschiedlicher Steilheit und unterschiedlicher Höhe. Auf ähnliche Art und Weise lassen sich verschiedenste Abfassungen auch dann realisieren, wenn komplexe Gerungen involviert sind. So wie Surfer wurden auch alle anderen im Projekt erstellten Algorithmen implementiert und ausführlich getestet. Die so entstandenen Programme werden mittlerweile von Kollegen an anderen Universitäten verwendet und von der Universität Salzburg an Firmen lizensiert, sodaß das Projekt auch aus praktischer Sicht und mit Blick auf einen wünschenswerten Technologietransfer von der Forschung in die Praxis ein Erfolg ist.