No description available.

We present a new algorithm for computing the straight skeleton of a polygon. For a polygon with n vertices, among which r are reflex vertices, we give a deterministic algorithm that reduces the straight skeleton computation to a motorcycle graph computation in O(n (log n) log r) time. It improves on the previously best known algorithm for this reduction, which is randomised, and runs in expected O(n √(h+1) log² n) time for a polygon with h holes. Using known motorcycle graph algorithms, our result yields improved time bounds for computing straight skeletons. In particular, we can compute the straight skeleton of a non-degenerate polygon in O(n (log n) log r + r^(4/3 + ε)) time for any ε > 0. On degenerate input, our time bound increases to O(n (log n) log r + r^(17/11 + ε))

No description available.

The objective of this study is to explore the methods used for automatic roof reconstruction so far and on the basis of this analysis purpose a methodology, which uses the geometric structure of Straight Skeleton for an initial approximation of the roof shape. In the first part of this thesis issues of automatic detection and extraction of building roof planes from laser scanning data are explored. Also, the Straight Skeleton is described in detail here and its potential for the construction of hip and saddle roofs is explained. An iterative approach which consists of deleting or moving appropriate points between roof planes using the principles of orthogonal regression is specified as an optimization method. In the second part of this thesis the proposed algorithm was implemented using CGAL (an open source library) and then it was tested on different data sets. In the very end, it is concluded that the use of the proposed algorithm on more complex types of roofs is inappropriate. The excellent results of the optimization of hip and saddle-shaped roof types are highlighted simultaneously.

This master thesis is focused on cartography generalization of a rivers using collapse and partial collapse method with the usage of straight skeleton data structure. The proposed method was designed for large scale maps in geographical view and for medium scale maps in cartographic view (till 1 : 100 000). The thesis is focusing on width of a river as stand alone criteria for generalization decision. The presented solution represents set of a criteria which decides on generalization of a river. The presented thesis also solves problematic situations that exist on a river such as islands, junctions, shoulders or bifurcation. The thesis also includes proposed generalization algorithm which is using straight skeleton data structure. The algorithm is implemented in C++ programming language in Microsoft Visual Studio IDE. The algorithm uses external libraries Qt and CGAL (Computational Geometry Algorithms Library) for functioning. Algorithm results are saved in ESRI geodatabase with the usage of Python 2.7 programming language and external library ArcPy. Water areas from ZABAGED were chosen as appropriate data for testing. Achieved results of generalization are presented on test data for various scales and they are compared with base maps of Czech Republic. Keywords: digital cartography, cartography...

Nach einer Betrachtung der bestehenden Ansätze zur automatischen Graphgenerierung wurde eine Möglichkeit entwickelt, auf der Grundlage von OpenStreetMap-Innenraumkarten mit Hilfe einer bereits existierenden Implementierung des Straight Skeleton in Python automatisch Wege zu berechnen und diese wieder ins OpenStreetMap-Format zu überführen.:1. Einleitung 2. Überblick zur aktuellen Forschung 3. Anwendung des Straight Skeleton auf OpenStreetMap-Daten 3.1. Polyskel 3.2. Einlesen der Daten und Extrahieren der Türen und Räume 3.3. Kombination von Türen und Räumen 3.4. Generierung von Wegen mit Hilfe von polyskel 3.5. Kurze Wege zu längeren zusammenfassen 3.6. Wege vereinfachen 3.7. Wege im OpenStreetMap-Format speichern 4. Fazit und Ausblick Literaturverzeichnis Anhang