]*>","")" /> Delaunay三角网格的一种快速生成法

• 论文 • 上一篇    下一篇



  1. 北京应用物理与计算数学研究所;计算物理实验室 ;北京应用物理与计算数学研究所;计算物理实验室 ;北京应用物理与计算数学研究所;计算物理实验室
  • 出版日期:2001-04-20 发布日期:2001-04-20

邬吉明,沈隆钧,张景琳. Delaunay三角网格的一种快速生成法[J]. 数值计算与计算机应用, 2001, 22(4): 267-275.


  1. Wu Jiming,Shen Longjun,Zhang Jinglin (Laboratory of Computational Physics, Institute of Applied Physics and Computational Mathematics, Beijing 100088)
  • Online:2001-04-20 Published:2001-04-20
Delaunay triangulation has been widely used in many fields such as compu- tational fluid dynamics, statistics, meteorology solid state physics, computational geometry and so on. Bowyer-Watson algorithm is a very popular one for generating Delaunay triangulation. In generating the Delaunay triangulation of a preassigned set of n points, the complexity of Bowyer-Watson algorithm can at most be reduced to O(n log n) for the simple reason that the complexity of its tree search process is O(nlog n). In this paper we suggest a tree search technique whose complexity is O(n). Noting that the order of point insertion can affect the efficiency of Bowyer- Watson algorithm, we propose a technique to optimize the point insertion process. Based on these two techniques, we obtain a fast algorithm for generating Delaunay triangulation.

[1] J. Peraire, M. Vahdati, K. Morgan and O. Zienkiewicz, Adaptive remeshing for compressible flowcomputations, J Comp. Phys., 72 (1987), 449-466.
[2] R. Lohner and P. Parikh, AIAA 88-0515, Jan., 1988.
[3] P. Parikh, R. Lohner, C. Gumbert and S. Pirzadeh, AIAA 89-0362, Jan., 1989.
[4] G.S. Spragle, W.R. McGrory and J. Fang, AIAA 91-0726, Jan., 1991.
[5] P. J. Green, R. Sibson, Computing Dirichlet tessellations in the plane, The Computer J, 21:2(1978), 168-173.
[6] A. Bowyer, Computing Dirichlet tessellations , The Computer J., 24: 2 (1981), 162-166.
[7] D. F. Wson, Computing the n-dimensional Delaunay tessellation with application to Voronoipolytopes, The Computer J., 24: 2 (1981), 167-172.
[8] N. P. Weatherill, A method for generating irregular computational grids in multiply connectedplanar domains, Int. J Numer. Meth. Fluids, 8 (1988), 181-197.
[9] D. G. Holmes, D. D. Snyder, The generation of unstructured triangular meshes using Delaunaytriangulation, Proc. Int. Con f On Numerical Grid Generation in Computational Fluid Dynamics'88(Pineridge, Swansea, U. K., 1988), 643.
[10] S. Rebay Efficient unstructured mesh generation by means of Delaunay triangulation and Bowyer-Watson algorithm, J. Comp. Phys., 106 (1993), 125-138.
[11] W. K. Anderson, A grid generation and flow solution method for the Euler equations on unstruc-tured grids, J. Comp. Phy8., 11O (1994), 23-38.
[13]曾扬兵,沈孟育,王保国,刘秋生,非结构网格生成Bowyer-Watson方法的改进,计算物理,14:2(1997),      179-184.
[14] G. L. Dirichlet, Uber die Reduction der Positiven Quadratischen Formen mit drei Unbestimmten Ganzen Zahlen, Z. Reine Angew. Math., 40: 3 (1850), 209-227.
[15] C. A. Rogers, Packing and Covering, Cambridge Mathematical Tracts # 54, Cambridge University Press, 1964.
[16] R. Sibson, Locally equiangularity triangulations, The Computer J, 21: 3 (1978), 243-245.
No related articles found!