Delaunay三角网生成的改进算法

计算机科学 ›› 2019, Vol. 46 ›› Issue (6A): 226-229.

Delaunay三角网生成的改进算法

青文星, 陈伟

西南石油大学计算机科学学院成都610500

出版日期:2019-06-14 发布日期:2019-07-02
通讯作者: 陈伟(1965-),男,博士,主要研究方向为科学计算可视化与石油工程计算,E-mail:ncchenwei@163.com(通信作者)。
作者简介:青文星(1993-),男,硕士生,主要研究方向为GIS与计算几何;

Delaunay Triangular Mesh Optimization Algorithm

QING Wen-xing, CHEN Wei

School of Computer Science,Southwest Petroleum University,Chengdu 610500,China

Online:2019-06-14 Published:2019-07-02

摘要/Abstract

摘要： 在石油领域,经过多年的研究和发展,一些网格相关的基本算法如Delaunay三角网生成算法等已逐渐趋于成熟。然而伴随技术的发展,行业对相关算法和软件的要求也不断提高,现有方法已经不能满足实际需要。文中分析了目前常规三角网生成算法的特点和缺点,提出了一种将逐点和分治相结合的快速生成Delaunay三角网格的方法,使得布点数目对构网效率不会产生较大影响。通过大量测试验证了该算法在正确性、稳定性和效率上较传统算法具有较大优势。

关键词: Delaunay三角网, 分治法, 逐点法

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

中图分类号:

TP311

青文星, 陈伟. Delaunay三角网生成的改进算法[J]. 计算机科学, 2019, 46(6A): 226-229. https://doi.org/

QING Wen-xing, CHEN Wei. Delaunay Triangular Mesh Optimization Algorithm[J]. Computer Science, 2019, 46(6A): 226-229. https://doi.org/

参考文献

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed