Efficient Calculation and Visualisation of Range Polygons

This bachelor thesis focuses on determining and visualizing the reachable vertices of a graph. A vertex is considered reachable if its distance from a given source vertex is smaller than or equal to given a maximal range. To formalize the problem we introduce the RangePolygon problem, which is solved by a set of polygons delimiting the area containing reachable vertices. To enforce an accurate representation we also define the boundary of the reachable area. We solve the problem in two steps by first determining the boundary from the given inputs and then using the boundary to create a visualization. For the routing part of the problem we adapt Dijkstra’s algorithm to return the boundary and introduce Customizable Route Planning [DGPW11] as a speedup technique. For visualization we develop and present exact solutions and a conservative heuristic to generate range polygons from the boundary. We then show that our approaches are faster and generate less complex polygons than Alpha Shapes [EKS83], an algorithm used for surface reconstruction. Deutsche Zusammenfassung Diese Bachelorarbeit befasst sich mit der Bestimmung und visuellen Darstellung von erreichbaren Knoten eines Graphens. Ein Knoten ist erreichbar wenn seine Entfernung zu einem bestimmen Startknoten eine bestimmte Distanz nicht uberschreitet. Um das Problem zu formalisieren fuhren wir das RangePolygon Problem ein. Die Losung fur deses Problem ist eine Menge an Polygonen, die die erreichbaren von den unerreichbaren Knoten trennt. Wir definieren zusatzlich die Grenze des erreichbaren Bereiches um eine genaue Darstellung der Reichweitenpolygone zu erzwingen. Wir losen das Problem in zwei Schritten: Zuerst bestimmen wir die Grenze aus den Eingabedaten, und anschliesend eine visuelle Darstellung mit Hilfe der Grenze. Zur Bestimmung der Grenze passen wir Dijkstras Algorithmus an unsere Problemstellung an und stellen Customizable Route Planning [DGPW11] als eine mogliche Beschleunigungstechnik vor. Fur die Darstellung entwerfen wir Algorithmen zur exakten Wiedergabe der Grenze, sowie eine Heuristik es erlaubt erreichbare Flache als unerreichbar zu makieren, aber nicht unerreichbare Flache als erreichbar. Anschliesend vergleichen wir unsere Algorithmen mit Alpha Shapes [EKS83], einem Algorithmus zur Oberflachenrekonstruktion, und kommen zu dem Schluss, dass unsere Algorithmen sowohl schneller sind, als auch weniger komplexe Polygone berechnen.