Subject of this paper is triangulation of given domain also called as mesh generation. Overview of main mesh types (structured, unstructured and hybrid) is given. Groups of triangulation methods are defined and include collective triangulation, incremental triangulation, pliant mesh generation with post-triangulation and plaint mesh generation with retriangulation. Delaunay triangulation is described in greater detail and variuos Delaunay triangulation algorithms are presented including use of Delaunay triangulation for anisotropic mesh generation and method to generate Constrained Delaunay triangulation. Greedy insertion Delaunay and data dependent allgorithms are developed for hight fields surface aproximation. Significant improvements are made to these algorithms including faster recalculation, node selection and use of supplementary data sets in order to maximise efficiency of calculations. Main criteria to evaluate developed algorithms is overall error of approximation and speed of calculation. Data dependent algorithm generates better quality mesh (less approximation error), however Delaunay triangulation algorithm is significantly faster. Results and conclusions are presented at the end of paper.

Šiame darbe yra nagrinėjamas piršto antspaudo atpažinimo uždavinio viena iš sudedamųjų dalių: skaitmeninės informacijos apie piršto antspaudą gavimas. Aprašomas metodas, paremtas kreivių kreivumų įvertinimu bei minimalaus žiedo sąvoka. Taip pat, aprašytas naujas Delaunė trianguliacijos radimo, minimalaus žiedo skaičiavimo bei kreivių kreivumų įvertinimo algoritmai. Darbo tikslas - pagerinti piršto antspaudo atpažinimo algoritmo kokybę, bei greitį. / The recognition of fingerprint is discussed in this article. The goal of this work is to increase the quality of fingerprint recognition method, and to improve algorithm speed. The new method of fingerprint data for fingerprint matching is analyzed. It concentrates on calculating values of curve curvatures, and minimum-width annuli. Some new methods of evaluation of this properties are described step by step.

Magistro baigiamajam darbui pasirinkta tema yra Trimačiai objektai: atvaizdavimo ir deformacijos algoritmai. Ši tema nagrinėja paviršiaus rekonstrukciją iš taškų debesies ir galimybes pritaikyti paviršiaus deformacijos algoritmus. Analizės etapo metu išsiaiškinta, kad pagrindinė paviršiaus atstatymo iš taškų debesies problema yra lėtas algoritmų veikimas. Šiame darbe siūlomas atvirkštinės inžinerijos metodas, veikiantis 2D Delaunay trianguliacijos pagrindu. Pateikiami algoritmai padalina taškų debesį į kelias dalis, tada iš trimatės erdvės taškų debesies dalys yra transformuojamos į dvimatę erdvę, suskaičiuojama 2D Delaunay trianguliacija ir gautas trikampių tinklelis vėl transformuojamas į trimatę erdvę. Taip pat pateikiamos teorinės galimybės gautą paviršių transformuoti jau žinomu algoritmu. Po algoritmų praktinio įgyvendinimo buvo nustatyta, kad jie veikia taip kaip tikėtasi, rezultatas gaunamas greičiau nei naudojant kitus žinomus algoritmus. Taip pat buvo pastebėta, kad 2D Delaunay trianguliaciją geriau naudoti kai taškų skaičius taškų debesyje yra labai didelis, o kai taškų skaičius neviršija 2000 geriau naudoti 3D Delaunay trianguliaciją. / The chosen theme of the Master of Science degree paper is “Three dimensional objects: visualization and deformation algorithms“. This subject considers surface reconstruction from point clouds and the possibilities to apply surface deformation algorithms. During the analysis phase we found that the main problem of the algorithms of surface reconstruction from scanned point clouds is the lack of speed. So in this paper a method, based on 2D Delaunay triangulation, for reverse engineering is proposed. This method divides point clouds into several parts, and then maps all the points of those point cloud parts to the plane. Then a 2D Delaunay triangulation is computed and the mesh is mapped back to the point cloud. We also give theoretical possibilities to apply a known algorithm for surface deformation. During the implementation phase we found that our algorithms work as expected, but quicker than the other methods proposed earlier. We also noticed that it’s better to use 2D Delaunay triangulation for bigger point clouds and 3D Delaunay triangulation for point clouds, which contains no more than approximately 2000 points.

Nagrinėjama GPS prietaiso Trimble R8 GNSS tikslumas. Tirta sudaryto geodezinio pagrindo tikslumo charakteristikos, remiantis atliktais GPS (globalinės padėties taškų nustatymo sistema) matavimais ir išskaičiuotomis geodezinio pagrindo punktų koordinatėmis. Atlikta analizė rodo, kad anksčiau sudarytas trianguliacijos tinklas yra aukšto tikslumo ir pilnai tenkina bei ateityje tenkins Kauno miesto geodezinio pagrindo reikalavimus, todėl punktų koordinates keisti būtų netikslinga. Apskaičiuotąsias GPS matavimais punktų koordinates vietinėje sistemoje tikslinga būtų taikyti, vykdant tik aukšto tikslumo geodezinius darbus. / The analysis GPS instrument Trimble R8 GNSS accuracy. Precision characteristics of performed geodesic basis were examined according to GPS (global location point determination) measurement and calculated coordinates of points of geodesic basis. The analysis showed, that triangulation net that was made earlier is of high precision and meets completely and will meet in the future the needs of city geodesic basis, therefore it is not expedient to change the coordinates of the points. The application of point coordinates calculated according to GPS (global location point determination) measurement in local system would be expedient when prosecuting geodesic works of high precision only in the city and coordinates of old planimetric net should be used for performance of gross scale topographical photos, for land cadastral works and other works of applied geodesy.

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.