Paper
A Simple Sweep-line Delaunay Triangulation Algorithm
- Authors:
- Liu Yonghe; Feng Jinming; Shao Yuehong
- Abstract
- A simple sweep-line algorithm for constructing 2D Delaunay triangulation is proposed in this paper. It includes following steps: sort the given points according to x coordinates or y coordinates, then link a point each time into the triangulation sequentially, and legalize the new triangles using Lawson’s method. Each point is processed by constructing triangles linking the point with all valid edges on the border – the convex hull of points passed by the sweep-line. The border edges are collected using a linked list and the point in it can be searched without consuming much time, since usually only 20-30 edges are in it. The algorithm is faster than incremental insertion algorithm and Fortune’s sweep-line algorithm. It is slower than the Zalik’s sweep-like algorithm, but is simpler and easier to implement, and can be regarded as another alternative choice to the Zalik’s algorithm or the divide-and-conquer algorithm.
- Keywords
- Delaunay Triangulation; Sweep-line Algorithm; Digital Elevation Models; Triangulated Irregular Networks
- StartPage
- 30
- EndPage
- 38
- Doi