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

Xue Ming He; Yi Lu; Cheng Gang Li; Min Min Ni; Chen Liang Hua

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

Paper Titles

A New Optic Senor for Real-Time Bath Temperature Measurement in a BOF
p.642

Equidistant Five Wavenumbers Selection for NIR Spectroscopy Analysis of Glucose in Human Serum
p.647

The Semantic Study on Infant Washing Product Based on Humanistic Care
p.651

A Simiple Method to Speed up the Calculation of a Computer-Generated Hologram
p.656

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

A Concept Lattice Merger Approach for Ontology Construction
p.667

Formal Reconfiguration of Enterprise Information System Flow Based on OKM and Binary Tree
p.673

Influences of Surfactants on Gloss of Aluminum Paste Printing Ink
p.679

Lengthening Steel-Work Hole Processing Machine Design Based on Open CNC System
p.685

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 181-182A Real-Time Algorithm for Convex Hull Construction...

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

Abstract:

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.

You might also be interested in these eBooks

Advanced Materials Science and Technology, ICMST 2010

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 181-182)

Pages:

661-666

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.181-182.661

Citation:

Cite this paper

Online since:

January 2011

Authors:

Xue Ming He, Yi Lu, Cheng Gang Li, Min Min Ni, Chen Liang Hua

Keywords:

Computation Geometry, Convex Hull, Delaunay Triangulation, Scattered Points

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] Zhang Xiangjing. Research on the Algorithm for Constructing Convex Hull of Scattered Point data. Journal of Geomatics, 2000, 4: 9-11.

Google Scholar

[2] Wu Xiaobo, Wang Shixin, Xiao Chunsheng. Research on the Algorithm for Delaunay Triangulation. Acta Geodaetica et Cartographic Sinica, 1999, 28(1): 28-34.

Google Scholar

[3] Yang Xunnian. A Quick Algorithm for Convex Hull in 3D. Journal of Zhejiang University (Natural Sciences), 1999, 33(2): 111-113.

Google Scholar

[4] Zhou Jie, Ding Xianrong, Wang Dguan. An Efficient Delaunay Triangulation Algorithm for Planar Sattered Point Data. Journal of Geomatics, 2003, 28(6): 21-23.

Google Scholar

[5] Green P J. and Sibson R. Computing Dirichlet Tessellations in the Plane. The Computer Journal, 1978, 21 (2): 168-173.

DOI: 10.1093/comjnl/21.2.168

Google Scholar

[6] Brassel K E. and Reif D. Procedure to Generate Thiessen Polygons. Geophysical Analysis, 1979(11): 289-303.

DOI: 10.1111/j.1538-4632.1979.tb00695.x

Google Scholar

[7] McCaullaghM T. and Ross CG. Delaunay Triangulation of a Random Data Set For Iirarithmic Mapping. The Cartographic Journal, 1980 (17): 93-99.

DOI: 10.1179/caj.1980.17.2.93

Google Scholar

[8] Maus A. Delaunay Triangulation and the Convex Hull of n Points in Expected Linear Time. BIT, 1984 (24): 151-163.

DOI: 10.1007/bf01937482

Google Scholar

[9] Ying Sun. Surface reconstruction using Gamma Shapes. (2007).

Google Scholar