diplomsko delo
Domen Mori (Author), Borut Žalik (Mentor), Niko Lukač (Co-mentor)

Abstract

Delaunayeva triangulacija je eden izmed najbolj uporabnih elementarnih algoritmov v računalniški geometriji. V tem diplomskem delu se ukvarjamo s spremembo Delaunayeve triangulacije pri premikanju že vstavljenih točk v realnem oziroma v doslednem času. V diplomskem delu predstavimo inkrementalni algoritem Delaunayeve triangulacije ter predlagano rešitev za pospešitev dinamičnega spreminjanja triangulacije s pomočjo štiriškega drevesa. Predlagano rešitev smo testirali na različnih množicah točk, štiriško drevo primerjali z naivno metodo in prikazali rezultate. Iz njih je razvidno, pri koliko točkah je še možno posodabljanje v realnem času ter učinkovitost štiriškega drevesa v primerjavi z naivno metodo.

Keywords

računalniška geometrija;realni čas;Delaunayeva triangulacija;štiriško drevo;sprememba Delaunayeve triangulacije;

Data

Language: Slovenian
Year of publishing:
Typology: 2.11 - Undergraduate Thesis
Organization: UM FERI - Faculty of Electrical Engineering and Computer Science
Publisher: D. Mori
UDC: 004.925(043.2)
COBISS: 19078934 Link will open in a new window
Views: 1166
Downloads: 150
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: MODIFICATIONS OF DELAUNAY TRIANGULATION IN REAL-TIME
Secondary abstract: Delaunay triangulation is one of the most useful algorithms in computational geometry. In this thesis, we are dealing with the change of Delaunay triangulation when we modify already inserted points in real-time or in reasonable time. In this thesis we present the incremental algorithm for Delaunay triangulation and our solution for supporting dynamic modification by using quad-tree data structure. We tested the proposed method on different point sets, compared quad tree to naive approach, and presented results. They show us how many points can be updated to achieve the real-time response and suitability of the quadtree data structure against the naive approach.
Secondary keywords: computational geometry;real-time triangulation;Delaunay triangulation;quadtree;modification of Delaunay triangulation;
URN: URN:SI:UM:
Type (COBISS): Bachelor thesis/paper
Thesis comment: Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Računalništvo in informacijske tehnologije
Pages: VII, 32 str.
ID: 8887383
Recommended works:
, diplomsko delo
, diplomska naloga visokošolskega strokovnega študijskega programa
, diplomsko delo univerzitetnega študijskega programa
, no subtitle data available
, diplomsko delo