Delaunay三角网格的一种快速生成法  

A FAST ALGORITHM FOR GENERATING DELAUNAY TRIANGULATION

作　　者：邬吉明[1] 沈隆钧[1] 张景琳[1] 

机构地区：[1]北京应用物理与计算数学研究所,计算物理实验室

出　　处：《数值计算与计算机应用》2001年第4期267-275,共9页Journal on Numerical Methods and Computer Applications

基　　金：中国工程物理研究院预先研究基金资助项目

摘　　要：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.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.

关 键 词：流体力学 Delaunay三角网格 Bowyer-Watson算法 树搜索方法 加点过程优化 

分 类 号：O351[理学—流体力学]