Research on Algorithm of the Point Set in the Plane Based on Delaunay Triangulation

DOI: 10.4236/ajcm.2012.24046   PDF   HTML     3,785 Downloads   5,930 Views   Citations


In the paper, an improved algorithm is presented for Delaunay triangulation of the point-set in the plain. Based on the original algorithm, we propose the notion of removing circle. During the process of triangulation, and the circle dynamically moves, the algorithm which is simple and practical, therefore evidently accelerates the process of searching a new point, while generating a new triangle. Then it shows the effect of the algorithm in the finite element mesh.

Share and Cite:

B. Yang and S. Shang, "Research on Algorithm of the Point Set in the Plane Based on Delaunay Triangulation," American Journal of Computational Mathematics, Vol. 2 No. 4, 2012, pp. 336-340. doi: 10.4236/ajcm.2012.24046.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] Q.-L. Li, “Three-Dimensional Modeling Based on the Statue of Point Cloud Data,” Master’s Thesis, Tongji University, Shanghai, 2009.
[2] G.-H. Peng, “Technical Research on Surface Reconstruction Based on Scattered Data,” Master’s Thesis, Northwestern Polytechnical University, Fremont, 2006:
[3] Y. Huang, W. Yu and T. Chen, “Three-Dimensional Body Scanning System for Apparel Mass Customization,” Optical Engineering, Vol. 41, No. 7, 2002, pp. 1475-1479. doi:10.1117/1.1478700
[4] W. Sun, C. Bradley, Y. E. Zhang and H. T. Loh, “Cloud Data Modeling Employing a Unified Non-Redundant Triangular Mesh,” Computer-Aided Design, Vol. 33, No. 2, 2001, pp. 183-193.
[5] R. Sibson, “Locally Equiangular Triangulation,” Computer Journal, Vol. 21, No. 3, 1977, pp. 243-245. doi:10.1093/comjnl/21.3.243
[6] H.-B. Ling and B. Wu, “An Improved Algorithm for Auto-Connection Delaunay Triangulation,” Computer Application, Vol. 19, No. 12, 1999, pp. 10-12.
[7] L. Guibas, “Basic Algorithms and Combinatorics in Compu-Tatinal,” Worksh on Computational Geometry, 1986, p. 119.
[8] Z. Zhou and R.-T. Liu, “A New Triangulation Algorithm of the Point Set in the Plane,” Journal of Harbin University of Science and Technology, Vol. 12, No. 2, 2007, pp. 78-80.
[9] P.-D. Zhou, “The Algorithm for Triangulation of the Pint Set in the Plane,” Journal of Computer Aided Design and Computer Graphics, Vol. 8, No. 4, 1996, pp. 259-264.
[10] X.-D. Li, “Algorithm Implementation of Two-Dimension and Multi-Dimension Linked Lists,” Journal of Foshan Institute of Science and Technology, Vol. 21, No. 3, 2003, pp. 35-38.
[11] A.-J. Chen, J.-D. Li and D.-D. Li, “Improved Randomized Algorithm for Circle Detection,” Opto-Electronic Engineering, Vol. 33, No. 12, 2006, pp. 92-93.
[12] J.-R. Wang and H.-T. Zheng, “The Projection Model and Application Based on Oval and Round,” Mathematics of Shanghai Middle School, Vol. 6, 2007, p. 47.

comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.