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
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-93303 |
| Date | January 2011 |
| Creators | Wallin, Hanna |
| Publisher | KTH, Skolan för teknikvetenskap (SCI) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | Swedish |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0021 seconds