An Improved Parallel Computation Method for Delaunay Triangulation

Abstract:

Amongst the flourishing Delaunay Triangulation methods, growth algorithm has been widely accepted because of its reputation of being simple and elegant. However, the parallelization of growth algorithm has not been fully exploited. In this work, a novel Growth algorithm of Delaunay Triangulation is proposed. The point cloud is first divided into two parts by a suitable curve and the separated areas are calculated by incremental algorithm. Triangles which cross with the curve are generated by a growth algorithm associated with uniform grid. At the process of merging, these grew triangles are used to detect incorrect triangles of the incremental algorithm areas. Method about generating triangles on curve is elaborated and a simple way to detect interferential triangles is also explained. With above method, triangulation calculation can be parallelized. Unlike the traditional divide-and-conquer method, no flip operation is needed in the proposed methodology. Thus, three dimensional applications are also made possible. A comparative research between tradition incremental algorithm and the proposed method has been conducted. Results show, the algorithm has a higher performance with less computation time.

• Periodical: Advanced Materials Research (Volume 819)
• Pages: 299-303
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.819.299
• Online since: September 2013
• Authors: Zhi Yu Chen, Jian Zhong Fu, Hong Yao Shen, Wen Feng Gan
• Keywords: Compound Algorithm, Delaunay Triangulation, Parallel Computation, Uniform Grid

References

[1] C.J. Du, An algorithm for automatic Delaunay triangulation of arbitrary planar domains. Advances in Engineering Software[J], 1996. 27(1-2): pp.21-26.

DOI: 10.1016/0965-9978(96)00004-x

[2] J. Yu, J. LU, C.W. ZHENG, A Comparative Research on Methods of Delaunay Triangulation. Journal of Image and Graphics[J] in Chinese, 2010(08): pp.1158-1167.

[3] D.T. Lee, B.J. Schachter, Two algorithms for constructing a Delaunay triangulation. International Journal of Computer & Information Sciences[J], 1980. 9(3): pp.219-242.

DOI: 10.1007/bf00977785

[4] M. Zadravec, B. Zalik, An almost distribution-independent incremental Delaunay triangulation algorithm. Visual Computer[J], 2005. 21(6): pp.384-396.

DOI: 10.1007/s00371-005-0293-3

[5] S.W. Yang, Y. Choi, C.K. Jung, A divide-and-conquer Delaunay triangulation algorithm with a vertex array and flip operations in two-dimensional space. International Journal of Precision Engineering and Manufacturing[J], 2011. 12(3): pp.435-442.

DOI: 10.1007/s12541-011-0056-1

[6] M.B. Chen, T.R. Chuang, J.J. Wu, Parallel divide-and-conquer scheme for 2D Delaunay triangulation. Concurrency and Computation-Practice & Experience[J], 2006. 18(12): pp.1595-1612.

DOI: 10.1002/cpe.1007

[7] Z. Gao, Z. Yu, M. Holst, Quality tetrahedral mesh smoothing via boundary-optimized Delaunay triangulation. Computer Aided Geometric Design[J], 2012. 29(9): pp.707-721.

DOI: 10.1016/j.cagd.2012.07.001

[8] P. Cignoni, C. Montani, R. Scopigno, DeWall: A fast divide and conquer Delaunay triangulation algorithm in E-d. Computer-Aided Design[J], 1998. 30(5): pp.333-341.

DOI: 10.1016/s0010-4485(97)00082-1

[9] T.P. Fang, L.A. Piegl, Delaunay triangulation using a uniform grid. IEEE Computer Graphics and Applications[J], 1993. 13(3): pp.36-47.

DOI: 10.1109/38.210490