Change search
ReferencesLink to record
Permanent link

Direct link
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
National Category
Computer Science
URN: urn:nbn:se:kth:diva-142353OAI: diva2:699750
Educational program
Master of Science in Engineering - Computer Science and Technology
Available from: 2014-03-13 Created: 2014-02-28 Last updated: 2014-03-13Bibliographically approved

Open Access in DiVA

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

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 496 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

Total: 63 hits
ReferencesLink to record
Permanent link

Direct link