An efficient sweep-line Delaunay triangulation algorithm

被引：30

作者：

Zalik, B ^{[1
]}

机构：

[1] Univ Maribor, Fac ELect Engn & Comp Sci, SI-2000 Maribor, Slovenia

来源：

COMPUTER-AIDED DESIGN | 2005年 / 37卷 / 10期

关键词：

computational geometry; Delaunay triangulation; sweep-line paradigm;

D O I：

10.1016/j.cad.2004.10.004

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

This paper introduces a new algorithm for constructing a 2D Delaunay triangulation. It is based on a sweep-line paradigm, which is combined with a local optimization criterion - a characteristic of incremental insertion algorithms. The sweep-line status is represented by a so-called advancing front, which is implemented as a hash-table. Heuristics have been introduced to prevent the construction of tiny triangles, which would probably be legalized. This algorithm has been compared with other popular Delaunay algorithms and it is the fastest algorithm among them. In addition, this algorithm does not use a lot of memory for supporting data structure, it is easy to understand and simple to implement. (c) 2004 Elsevier Ltd. All rights reserved.

引用

页码：1027 / 1038

页数：12

共 19 条

[1]

[Anonymous], 1977, Mathematical Software, DOI [DOI 10.1016/B978-0-12-587260-7.50011-X, DOI 10.1016/B978-0-12-587260-7.50011-X2]

[2]

AURENHAMMER F, 1991, COMPUT SURV, V23, P345, DOI 10.1145/116873.116880

[3]

BOISSONNAT JD, 2000, COMPUTATIONAL GEOMET, P11

[4]

De Berg M., 2000, COMPUTATIONAL GEOMET, DOI DOI 10.1007/978-3-662-03427-9