Paper Title:
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.

  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, Y. Lu, C. G. Li, M. M. Ni, C. L. Hua, "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
$32.00
Share

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

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

Authors: Jiang Yuan, Zi Xue Qiu, Jin Wei Cao
Abstract:Because of the disadvantages in evaluating straightness error of the traditional method, such as high algorithm complexity, low evaluating...
18
Authors: Sheng Wu Dong, Dong Wang, Yun Peng Wang
Chapter 12: Computer-Aided Design, Manufacturing and Engineering
Abstract:A new algorithm for position relationship between detecting point and polygon is proposed based on the research of radial method, and as the...
4248
Authors: Li Guo, Hai Ying Zheng, Yong Hong Wang, Bin Zhang
Chapter 2: Architectural Environment and Equipment Engineering
Abstract:Data matching technology is a key technology for spatial data integration and fusion. This paper represents a solution to the complex polygon...
252
Authors: Yu Ping Zhang, Zhao Ri Deng, Rui Qi Zhang
Chapter 8: Software Design and Development
Abstract:The triangulation of convex hull has the characteristics of point-set and polygon triangulation. According to some relative definitions, this...
1605
Authors: Xiu Sheng Duan, Yao Xuan Zhu, Jing Xiao, Jian Dong Su
Chapter 1: Mechatronics, Automation and Information Technologies
Abstract:As a familiar mark in applications of computer vision, checkerboard can be used in camera calibration and pose measurement of dimensional...
19