A Real-Time Algorithm for Convex Hull Construction and Delaunay Triangulation of Scattered Points Data

Abstract:

Article Preview

Convex hull is a very important data structure of computational geometry design. This paper presents an algorithm to construct the convex hull of a set of scattered points by coordinates and relative angle method. The algorithm determines the convex vertexes and eliminates some non-convex vertexes, which greatly reduces the searching scope and the complexity. Delaunay triangulation is widely used in 3D surface reconstruction. Due to its duality, Delaunay triangulation is usually constructed through Voronoi diagram. Delaunay triangulation is directly constructed in this paper. The algorithm is simple, stable and easy to implement, especially for less data points.

Info:

Periodical:

Advanced Materials Research (Volumes 181-182)

Edited by:

Qi Luo and Yuanzhi Wang

Pages:

661-666

DOI:

10.4028/www.scientific.net/AMR.181-182.661

Citation:

X. M. He et al., "A Real-Time Algorithm for Convex Hull Construction and Delaunay Triangulation of Scattered Points Data", Advanced Materials Research, Vols. 181-182, pp. 661-666, 2011

Online since:

January 2011

Export:

Price:

$35.00

In order to see related information, you need to Login.

In order to see related information, you need to Login.