Delaunay三角网生成的改进算法
|
摘要
在石油领域,经过多年的研究和发展,一些网格相关的基本算法如Delaunay三角网生成算法等已逐渐趋于成熟。然而伴随技术的发展,行业对相关算法和软件的要求也不断提高,现有方法已经不能满足实际需要。文中分析了目前常规三角网生成算法的特点和缺点,提出了一种将逐点和分治相结合的快速生成Delaunay三角网格的方法,使得布点数目对构网效率不会产生较大影响。通过大量测试验证了该算法在正确性、稳定性和效率上较传统算法具有较大优势。
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.
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.
引文
[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[J].The Computer Journal,1981,24(2):162-166.
[5] LAWSON C L.Generation of a Triangular Grid with Applita- 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.
[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[J].The Computer Journal,1981,24(2):162-166.
[5] LAWSON C L.Generation of a Triangular Grid with Applita- 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.