Computer Science ›› 2019, Vol. 46 ›› Issue (6A): 226-229.

• Pattern Recognition & Image Processing • Previous Articles     Next Articles

Delaunay Triangular Mesh Optimization Algorithm

QING Wen-xing, CHEN Wei   

  1. School of Computer Science,Southwest Petroleum University,Chengdu 610500,China
  • Online:2019-06-14 Published:2019-07-02

Abstract: After years of research and development in the petroleum field,some grid-related basic algorithms such as Delaunay triangulation algorithm have gradually matured.However,with the development of technology,the requirements of relevant algorithms and software in the industry are constantly improving,so the existing methods can no longer meet the actual needs.This paper studied and analyzed the characteristics and shortcomings of the conventional triangulation algorithm.It proposed a method by using the idea of point-by-point and divide-and-conquer to quickly gene-rate Delaunay triangle mesh,so that the number of layout points will not have a great impact on the efficiency of network construction.A large number of tests verify that the algorithm has greater advantage compared with traditional algorithms in terms of correctness,stability and efficiency.

Key words: Delaunay triangulation, Divide-and-conquer method, Point by point method

CLC Number: 

  • TP311
[1]陈树强,陈学工,土丽青;判定检测点是否在多边形内的新方法[J].微电子学与计算机,2006,23(8):1-4.
[2]武晓波,土世新,肖春生.Delaunay三角网的生成算法研究[J].测绘学报,1999,28(1):28-35.
[3]TSAI V J D .Delaunay Triangulations in TIN Creation:an Overview and a Linear-time Algorithm[J].International Journal of GIS,1993,7(6):501-524.
[4]BOWYER A.Computing Dirichlet tessellations.The Computer Journal,1981,24(2):162-166.
[5]LAWSON C L.Generation of a Triangular Grid withApplita-tion to Contour Plotting,Technical Memo[R].Jet Propultion Laboratory,Pasadina,Califormia,1972.
[6]WU W Z,RUI Y K,SU F Z,et al.Novel parallel algorithm for constructing Delaunay triangulation based on a twofold-divide-and-conquer scheme[J].GIScience and Remote Sensing,2014,51(5):537-554.
[7]YANG S W,CHOI Y,JUNG C K.A divide-and-conquer Delaunay triangulation algorithm with a vertex array and flip operations in two-dimensional space[J].International Journal of Precision Engineering and Manufacturing,2011,12(3):435-442.
[8]ANDRÉ L M,CAMACHO,GUIMARÃES,S C,et al.A functional language to implement the divide-and-conquer Delaunay triangulation algorithm[J].Applied Mathematics and Computation,2005,168(1):178-191.
[9]黄清华.一种基于逐点插入Delaunay三角剖分生成Voronoi图的算法[J].微型电脑应用,2014,30(6):43-45.
[1] CHEN Shi-jie, ZHANG Sen-lin, LIU Mei-qin, ZHENG Rong-hao. Underwater Terrain Three-dimensional Reconstruction Algorithm Based on Improved Delaunay Triangulation [J]. Computer Science, 2020, 47(11): 137-141.
[2] WANG Hua. Improved Method for Blade Shape Simulation Based on Vein Shape Function [J]. Computer Science, 2019, 46(6A): 234-238.
[3] WANG Dong, MA Chun-yong and CHEN Ge. Fast Image Registration Algorithm for PCB Images [J]. Computer Science, 2016, 43(Z6): 152-155.
[4] LI Chun-xin and PENG Ren-can. Rapid Visualization Method Based on 3D Delaunay Triangulation [J]. Computer Science, 2015, 42(Z6): 236-237.
[5] BI Shuo-ben,CHEN Dong-qi,YAN Jian and GUO Yi. Planar Delaunay Triangulation Algorithm Based on 2D Convex Hull [J]. Computer Science, 2014, 41(10): 317-320.
[6] . [J]. Computer Science, 2008, 35(8): 6-9.
[7] . [J]. Computer Science, 2007, 34(12): 182-183.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!