En topologisk representation av en polygon;det rakkantiga skelettet

Autor: Wallin, Hanna
Jazyk: švédština
Rok vydání: 2011
Předmět:
Druh dokumentu: Text
Popis: The aim of this thesis project is to produce an algorithm for finding a topologicalrepresentation of a polygon, called a straight skeleton, using floating pointarithmetic. Various straight skeleton algorithms are examined and discussed witha focus on time complexity and one is chosen for implementation. This implementationis then compared with the open source library CGAL with regards torunning time. The result is an algorithm which is based on an algorithm by Felkeland Obdrzalek and which, for polygons with more than five thousand vertices andthree significant digits representing points, runs around 25% faster than CGALsimplementation. Complications regarding the use of floating-point arithmetic arealso discussed.
Syftet med detta examensarbete är att producera en algoritm för att finna entopologisk representation av en polygon, som kallas det rakkantiga skelettet, genomatt använda flyttalsaritmetik. Olika algoritmer diskuteras med avseende främst påtidskomplexitet och en väljs för implementation. Denna implementation jämförssedan med ett öppet källkodsbibliotek, CGAL, med avseende på körtid. Resultatetär en algoritm som är baserad på en algoritm av Felkel och Obdrzalek och som, förpolygoner med fler än fem tusen hörn och tre värdesiffror hos punkter, har ungefär25% snabbare körtid än CGALs implementation. Komplikationer som uppstår pågrund av användandet av flyttalsaritmetik diskuteras också.1
Databáze: Networked Digital Library of Theses & Dissertations