Paprasto skylėto daugiakampio skaidymo algoritmai

Abstract

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.