Aproksimacijski algoritem gradnje srednje osi enostavnih mnogokotnikov, temelječ na omejeni Delaunayevi triangulaciji : doktorska disertacija

slovenian

doktorska dela

2014

Univerza v Mariboru, Fakulteta za elektrotehniko računalništvo in informatiko

In this doctoral dissertation a new method for approximating a polygon's medial axis is introduced. As shown by experiments, the new method is more efficient than the existing methods. Firstly the definition of the main problem is given. This is fol-lowed by the description of fields, where the medial axis is used, and finished with the hypotheses. In the next chapter, the connection between the Voronoi diagram and the Delaunay triangulation is mentioned, which is followed by the description of the constrained Delaunay triangulation. In the next chapter, algorithms for medial axis construction are described and classified into groups of exact and approximate algorithms. This is followed by definitions and an overview of existing methods. The core of this doctoral dissertation is composed of the description of a new algorithm for medial axis construction of a simple polygon. In this chapter, the triangulation, heuristics and the step for medial axis construction out of the triangles circumcentres are described. The next chapter is devoted to the analysis of our algorithm. Here the time and space complexity are derived and the comparison of our algorithm with the existing ones is given. This is followed by the description of a metric, which evaluates the exactness of a polygon's medial axis. The doctoral dissertation is concluded with evaluation of the hypotheses and an overview of the scientific contributions.

07.08.2023