Return to search

Paprasto skylėto daugiakampio skaidymo algoritmai / Algorithms for decomposition of simple polygon with holes

Baigiamajame magistro darbe nagrinėjama paprasto skylėto daugiakampio skaidymo į dalis, kurių viršūnių skaičius neviršyja nustatyto skaičiaus problema. Apibrėžiamas uždavinys ir jo svarba. Apžvelgiami egzistuojantys skaidymo algoritmai, padedantys išspręsti uždavinį, bei jų realizacijos. Pateikiamos trianguliacijos ir padalinimo į apytiksliai iškilius daugiakampius algoritmų modifikacijos, jų privalumai ir trūkumai. Įvertinamas šių modifikuotų algoritmų sudėtingumas. Eksperimentinėje dalyje pateikiami skaičiavimo eksperimentų rezultatai, jų analizė ir palyginimas su teoriniais algoritmų sudėtingumo įverčiais. Remiantis skaičiavimo eksperimentų rezultatais pateikiamos išvados ir siūlymai. / This study deals with decomposition of simple polygon with holes into components so that every piece does not exceed some defined number of vertices. We define the problem and its appliances. Existing studies and algorithms for polygon decomposition are covered. We propose modifications of polygon triangulation and approximate convex decomposition algorithms. Also the complexity analysis of both algorithms is made. In the experimental part of the work results of computing experiments are presented, analyzed and compared to the theoretical complexity bounds.

Identiferoai:union.ndltd.org:LABT_ETD/oai:elaba.lt:LT-eLABa-0001:E.02~2010~D_20100622_145747-56362
Date22 June 2010
CreatorsMotiejauskas, Danas
ContributorsSuboč, Olga, Meilūnas, Mečislavas, Kirjackis, Jevgenijus, Kaučikas, Algirdas, Krylovas, Aleksandras, Leonavičienė, Teresė, Ilgevičius, Audrius, Vilnius Gediminas Technical University
PublisherLithuanian Academic Libraries Network (LABT), Vilnius Gediminas Technical University
Source SetsLithuanian ETD submission system
LanguageLithuanian
Detected LanguageUnknown
TypeMaster thesis
Formatapplication/pdf
Sourcehttp://vddb.laba.lt/obj/LT-eLABa-0001:E.02~2010~D_20100622_145747-56362
RightsUnrestricted

Page generated in 0.0024 seconds