Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
En topologisk representation av en polygon;det rakkantiga skelettet
KTH, School of Engineering Sciences (SCI).
2011 (Swedish)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

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.

Abstract [sv]

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

Place, publisher, year, edition, pages
2011.
National Category
Learning
Identifiers
URN: urn:nbn:se:kth:diva-93303OAI: oai:DiVA.org:kth-93303DiVA: diva2:515607
Subject / course
Technology and Learning
Educational program
Master of Science in Engineering - Engineering and of Education
Uppsok
Technology
Examiners
Available from: 2012-04-13 Created: 2012-04-13 Last updated: 2013-03-26Bibliographically approved

Open Access in DiVA

fulltext(807 kB)107 downloads
File information
File name FULLTEXT01.pdfFile size 807 kBChecksum SHA-512
12ce8be29ad07284674d5ccc138ec18650bf1f8a9baaef701b23f3cce269f5737c6c3f7453eee03359a56de5ebc276ff1336ab0159990ced610aa92dd123385b
Type fulltextMimetype application/pdf

By organisation
School of Engineering Sciences (SCI)
Learning

Search outside of DiVA

GoogleGoogle Scholar
Total: 107 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 84 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf