Implementierung von gewichteten Straigt Skeletons

Ein Straight Skeleton ist eine Datenstruktur der algorithmischen Geometrie. Bei einem Poly- gon entsteht sie durch die Ausbreitung einer Wellenfront, die an allen Segmenten des Polygons zur gleichen Zeit startet und sich mit Einheitsgeschwindigkeit nach innen bewegt. Während dieser Ausbreitung können Segmente auf Länge Null schrumpfen oder das Polygon der Wel- lenfront kann sich in zwei Teile aufspalten. Als Straight Skeleton bezeichnet man die Pfade der Ecken dieser Wellenfront, die während deren Ausbreitung entstehen. Straight Skeletons weisen unzählige Anwendungen in Wissenschaft und Technik auf, wie etwa für Werkzeugweggenerie- rung, mathematische Untersuchungen von Origami oder der automatisierten Generierung von Dächern von Gebäuden auf der Basis von deren Grundrissen. Die Definition eines Straight Skeletons kann auf Geradensegmente in der Ebene verallge- meinert werden, welche sich höchstens in gemeinsamen Endpunkten schneiden. In den FWF Projekten L367-N15 und P25816-N15 haben wir dafür additiv und multiplikativ gewichtete Straight Skeletons entwickelt, bei denen diese Segmente zu unterschiedlichen Zeiten starten können und sich mit unterschiedlichen Geschwindigkeiten bewegen können. Ein entsprechen- der Algorithmus wurde von meinem Dissertanten Peter Palfrader als Prototyp implementiert. Damit ist nun etwa die Modellierung von Gebäudedächern möglich, bei denen die Dachflächen verschiedene Neigungen aufweisen und auf unterschiedlichen Höhen beginnen. In diesem Projekt wollen wir nun unsere Erfahrung mit der Implementierung von geometri- schen Algorithmen nutzen, um unsere Algorithmen zur Berechnung von gewichteten Straight Skeletons effizient und zuverlässig zu implementieren. Natürlich werden wir versuchen, Code zu entwickeln, welcher sowohl auf einer gewöhnlichen Gleitkommaarithmetik wie auch in Ver- bindung mit einer Bibliothek für exaktes geometrisches Rechnen (wie etwa CGAL) verwendet werden kann. Die von uns erstellte Implementierung wird unter der GPL der Allgemeinheit zur Verfügung stehen. Außerdem planen wir, unsere Implementierung CGAL zwecks Inklusion in deren Bibliothek anzubieten. Um ein umfassendes Testen unserer Implementierung zu erleichtern, wollen wir auch eine Datenbank mit zufälligen polygonalen Daten erstellen. Wir werden dafür auf frühere Arbeiten des Antragstellers zurückgreifen und Heuristiken für die Generierung von derartigen Daten entwickeln und implementieren. Diese Daten sowie die sie erzeugenden Implementierungen werden ebenfalls der Allgemeinheit zur Verfügung stehen. Obwohl der primäre Zweck das Testen unserer eigenen Implementierung ist, ist davon auszugehen, daß diese Daten auch in anderen praxisorientierten Disziplinen wie etwa GIS, CAD/CAM oder Architektur auf großes Interesse stoßen werden.

Unter Algorithmischer Geometrie versteht man ein Teilgebiet der (Theoretischen) Infor- matik, das sich mit der effizienten algorithmischen Lösung geometrisch formulierter Pro- bleme 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äh- rend 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. In diesem Projekt wurde ein Algorithmus zur Berechnung eines gewichteten Straight Skeleton eines PSLG detailliert entwickelt und in der Programmiersprache C++ implemen- tiert. Weiters wurde ein spezieller Algorithmus zur Lösung dieses Problems für Polygone implementiert, welche monoton sind. (Ein Polygon ist monoton relativ zu einer Gera- de ` falls jede Gerade senkrecht zu ` das Polygon entweder gar nicht oder nur in einem Punkt oder Geradensegment schneidet.) Die beiden resultierenden Implementierungen, Surfer2 und Monos, benutzen exakte Arithmetik, welche durch Einbindung der Com- putational Geometry Algorithms Library (CGAL) bereitgestellt wird. Sowohl Surfer2 wie auch Monos sind auf der Plattform GitHub unter der GPL Lizenz (Version 3) frei und unentgeltlich verfügbar. (GitHub ist ein Onlinedienst, welcher Speicher für Software- Entwicklungsprojekte inklusive Versionsverwaltung auf seinen Servern bereitstellt.) Weiters entwickelten wir umfangreiche Software-Werkzeuge zur Erstellung von poly- gonalen Testdaten. Beispielsweise können unsere Werkzeuge sternförmige oder monotone Polygone generieren sowie Polygone, deren Kanten alle parallel zu den beiden Koordina- tenachsen sind. Wir haben weiters Generatoren für einige bekannte fraktale Kurven (wie etwa die Kochsche Schneeflockenkurve) entwickelt. Auch diese Implementierungen - in den Programmsprachen C++ oder C - sind via GitHub unter der GPL Lizenz (Version 3) frei und unentgeltlich verfügbar. Musterdaten für die damit erzeugten Polygone sind auch in der neuen Salzburg Datenbank frei verfügbar: https://sbgdb.cs.sbg.ac.at/.