Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
No Fit Polygon problem: Developing a complete solution to the No Fit Polygon problem
KTH, School of Computer Science and Communication (CSC).
2013 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

This thesis evaluates some of the most recent and promising approaches

for deriving the No Fit Polygon for two simple polygons, possibly with holes,

and verify that the approach works in practice. We have chosen three different

approaches based on the complexity of the input. These approaches

were implemented and benchmarked against CGAL [1], a third party library

which provides solvers for many computational geometry problems.

Our solution solves problems of a higher degree of complexity than that

of the library we benchmarked against and for input of lower complexity we

solve the problem in a more efficient manner.

Abstract [sv]

Den här uppsatsen evaluerar några av de senaste och mest lovande tillvägagånssätt

för att generera No Fit - polygonen för två enkla polygoner, med

och utan hål, och verifiera att de fungerar i praktiken. Vi har valt tre olika

tillvägagångssätt baserat på komplexiteten av indata. Dessa tillvägagångssätt

implementerades och jämfördes med CGAL [1], ett tredjepartsbibliotek

som tillhandahåller lösare av många beräkningsgeometriska problem.

Vår lösning klarar problem av en högre grad av komplexitet än tredjepartsbiblioteket

vi jämför med. För indata av lägre komplexitetsnivåer löser

vi problemet mer effektivt.

Place, publisher, year, edition, pages
2013.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-142353OAI: oai:DiVA.org:kth-142353DiVA: diva2:699750
Educational program
Master of Science in Engineering - Computer Science and Technology
Supervisors
Examiners
Available from: 2014-03-13 Created: 2014-02-28 Last updated: 2014-03-13Bibliographically approved

Open Access in DiVA

fulltext(1188 kB)1042 downloads
File information
File name FULLTEXT01.pdfFile size 1188 kBChecksum SHA-512
d6a3389987f12d246043514c00d64c83e7aa76387b4cd3608a3446653f162351736755e47f2d7b2f5aefd4cb0c0e12ce1bf103b2e275e4551b0a9806ee074045
Type fulltextMimetype application/pdf

By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 1042 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: 78 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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