ǂAn ǂalmost distribution-independent incremental Delaunay triangulation algorithm

Mirko Zadravec (Avtor), Borut Žalik (Avtor)

Povzetek

This paper presents a new incremental insertion algorithm for constructing a Delaunay triangulation. Firstly, the nearest point is found in order to speed up the location of a triangle containing a currently inserted point. A hash table and 1-3 deterministic skip lists, combined with a walking strategy, are used for this task. The obtained algorithm is compared with the most popular Delaunay triangulation algorithms. The algorithm has the following attractive features: it is fast and practically independent of the distribution of input points, it is not memory demanding, and it is numerically stable and easy to implement.

Ključne besede

Delaunajeva triangulacija;inkrementalni algoritmi;računalniška grafika;Delaunay triangulation;incremental algorithm;computational geometry;skip list;hash table;

Podatki

Jezik:	Angleški jezik
Leto izida:	2005
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
UDK:	004.92
COBISS:	9766422
ISSN:	0178-2789
Št. ogledov:	1771
Št. prenosov:	88
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarne ključne besede:	Delaunajeva triangulacija;inkrementalni algoritmi;računalniška grafika;
URN:	URN:SI:UM:
Strani:	str. 384-396
Letnik:	ǂVol. ǂ21
Zvezek:	ǂNo. ǂ6
Čas izdaje:	jul. 2005
ID:	8718311