Return to search

Algoritmų operacijoms su plokščiosiomis geometrinėmis figūromis sudarymas ir tyrimas / Development and investigation of algorithms for performing operations with geometrical objects

Darbe pristatyti sukurti ir ištirti algoritmai operacijoms su plokščiosiomis geometrinėmis figūromis. Tai figūrų sujungimas, sankirta ir atėmimas. Šios operacijos yra labai svarbios ir labai plačiai naudojamos grafinėse projektavimo, technologinio paruošimo sistemose. Algoritmai operacijoms su plokščiosiomis geometrinėmis figūromis yra vertinami pagal šiuos kriterijus: skaičiavimų laikas, rezultatų (gautų figūrų) kokybė. Šio algoritmo išskirtinė savybė yra ta, kad figūrų viršūnės gali būti jungiamos lankais, kvadratinėmis bei kubinėmis bezjė kreivėmis. Šitame darbe nagrinėjamas algoritmas operacijoms su geometrinėmis figūromis, kuris paremtas šluojančios tiesės principu. Horizontali šluojanti tiesė juda per įvykių taškus, kuriuos sudaro pradinių duomenų viršūnės bei segmentų tarpusavio susikirtimo taškai. Suskaičiuojamos šluojančios tiesės ir duomenų segmentų susikirtimo aibės kiekviename įvykio taške. Iš šių susikirtimo aibių yra suformuojami intervalai, kurių pagalba yra konstruojami galutiniai rezultatai. Operacijų rezultatai buvo lyginami su skenavimo algoritmo rezultatais bei su Java2D API paketo rezultatais (Java2D buvo naudojama tik rezultatų kokybei palyginti). Atlikus eksperimentinius tyrimus buvo nustatyti, kad darbe pasiūlyti sprendimai pateikia geresnius rezultatus. Detalesnę tyrimų analizę galima rasti eksperimentinėje darbo dalyje. / An algorithm for polygon set-operations (union, intersection, difference) was introduced. In CAD system these operations are very important and widely used. The most important aspects are speed and quality of results. Previously used and analyzed polygon operations was based on grid calculations. Thus this strategy takes big amount of time to perform operation and generates not exact results. The major idea in presented algorithm for polygon operations was to use sweeplines through calculated event points (all vertexes and intersection points between data segments). For each sweepline the intervals information is generated (depending on amount of up and down directions from crossed segments). Afterward these intervals are connected between each other to construct the final polygon. As additional feature of this algorithm is support of arcs, quadratic and cubic bezier curves, which connects polygon vertexes. The results of this algorithm were compared with results of scanline (grid) based algorithm and Java2D API (this API is not able to process big amount of data, thus this is used only to check the correctness of result for polygon operations). After implementation and experiments it is obvious that this algorithm works and provides better results (speed and quality of resulting polygons). The detailed comparison and analysis of polygons set-operations is presented in experimental part of this paper.

Identiferoai:union.ndltd.org:LABT_ETD/oai:elaba.lt:LT-eLABa-0001:E.02~2010~D_20100826_143708-57589
Date26 August 2010
CreatorsRiepšas, Andrius
ContributorsTelksnys, Laimutis, Maciulevičius, Stasys, Barauskas, Rimantas, Jasinevičius, Raimundas, Mockus, Jonas, Plėštys, Rimantas, Pranevičius, Henrikas, Riškus, Aleksas, Bareiša, Eduardas, Kaunas University of Technology
PublisherLithuanian Academic Libraries Network (LABT), Kaunas University of Technology
Source SetsLithuanian ETD submission system
LanguageLithuanian
Detected LanguageUnknown
TypeMaster thesis
Formatapplication/pdf
Sourcehttp://vddb.laba.lt/obj/LT-eLABa-0001:E.02~2010~D_20100826_143708-57589
RightsUnrestricted

Page generated in 0.0026 seconds