A faster circle-sweep Delaunay triangulation algorithm

被引：16

作者：

Biniaz, Ahmad ^{[1
]}

Dastghaibyfard, Gholamhossein ^{[2
]}

机构：

[1] Islamic Azad Univ, Lamerd Branch, Dept Comp Engn, Lamerd, Iran

[2] Shiraz Univ, Dept Comp Sci & Engn, Shiraz, Iran

来源：

ADVANCES IN ENGINEERING SOFTWARE | 2012年 / 43卷 / 01期

关键词：

Computational geometry; Delaunay triangulation; In-circle test; Recursive edge-flipping; Sweep-line; Sweep-circle; INCREMENTAL CONSTRUCTION; MESH; INTERPOLATION; TERRAINS;

D O I：

10.1016/j.advengsoft.2011.09.003

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

This paper presents a new way to compute the Delaunay triangulation of a planar set P of n points, using sweep-circle technique combined with the standard recursive edge-flipping. The algorithm sweeps the plane by an increasing circle whose center is a fixed point in the convex hull of P. Empirical results and comparisons show that it reduces the number of in-circle tests and edge-flips, and it is efficient in practice. (C) 2011 Elsevier Ltd. All rights reserved.

引用

页码：1 / 13

页数：13

共 40 条

[1]

[Anonymous], 1990, Introduction to Algorithms

[2] Generation of a finite element MESH from stereolithography (STL) files [J].

Béchet, E ;

Cuilliere, JC ;

Trochu, F .

COMPUTER-AIDED DESIGN, 2002, 34 (01) :1-17

[3]

Berg M., 2008, COMPUTATIONAL GEOMET, V3rd, DOI DOI 10.1007/978-3-540-77974-2

[4]

BINIAZ A, 2008, P WSCG

[5] Drainage reality in terrains with higher-order Delaunay triangulations [J].

Biniaz, Ahmad ;

Dastghaibyfard, Gholamhossein .

ADVANCES IN 3D GEOINFORMATION SYSTEMS, 2008, :199-211

[6] VORONOI DIAGRAMS FROM CONVEX HULLS [J].

BROWN, KQ .

INFORMATION PROCESSING LETTERS, 1979, 9 (05) :223-228

[7] Three-dimensional Delaunay mesh generation [J].

Cheng, Siu-Wing ;

Poon, Sheung-Hung .

DISCRETE & COMPUTATIONAL GEOMETRY, 2006, 36 (03) :419-456

[8] Generating realistic terrains with higher-order Delaunay triangulations [J].

de Kok, Thierry ;

van Kreveld, Marc ;

Loffler, Maarten .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2007, 36 (01) :52-65

[9] A weak characterisation of the Delaunay triangulation [J].

de Silva, Vin .

GEOMETRIAE DEDICATA, 2008, 135 (01) :39-64

[10] HIGHER-DIMENSIONAL VORONOI DIAGRAMS IN LINEAR EXPECTED TIME [J].

DWYER, RA .

DISCRETE & COMPUTATIONAL GEOMETRY, 1991, 6 (04) :343-367

← 1 2 3 4 →