基于Delaunay算法含定解條件的三角單元網格生成

宋小鵬 古小敏 何秀錦 吳國珊 王斌武

（桂林航天工業學院能源與建筑環境學院， 廣西 桂林 541004）

摘? 要： 有限元分析過程中，網格剖分除了要對計算域進行剖分，也要對網格單元的定解條件進行標識。文章探討用Delaunay算法對二維計算域進行剖分，并生成包含定解條件（邊界條件和材料屬性等）的三角網格單元。對復雜幾何圖形采用分塊策略，將計算域分為若干凸多邊形，并對網格質量進行評估。以二維擴散方程為例，使用該算法生成的三角單元網格求解Laplace偏微分方程，計算結果與解析解吻合較好，表明該算法能夠生成較高質量的網格單元。

關鍵詞： Delaunay算法; 網格生成; 有限元; 定解條件

中圖分類號：TP301.6? ? ? ? ? 文獻標識碼：A? ? ?文章編號：1006-8228（2020）12-29-04

Abstract： In the process of finite element analysis， in addition to generating mesh for the computational domain， it is necessary to identify the solvability conditions of the mesh. Delaunay algorithm has been used to divide the two-dimensional computational domain and generate triangular mesh elements with solvability conditions （boundary conditions， material properties， etc.）. The complex computational domain is divided into several convex polygons， and the mesh quality is also calculated. Taking the two-dimensional diffusion problem as an example， the triangular element mesh has been generated using the Delaunay algorithm， and the Laplace partial differential equation has been solved. The numerical results are in good agreement with the analytical solution， which shows that the algorithm can generate high-quality mesh elements.

Key words： Delaunay algorithm; mesh generation; finite element method; solvability condition

0 引言

Delaunay三角化算法被廣泛用于有限元分析，很多學者對其算法做了大量研究：劉琴琴[1]對比了幾個平面域Delaunay三角網生成算法，并做了改進工作;馮斌斌[2]等改進了Delaunay三角網格的生成方法，可自適應加密從而提高有限元計算精度;張晶飛[3]等討論了基于Delaunay三角化的最優化網格節點生成算法。

很多學者對基于Delaunay算法的網格剖分算法進行了改進：李建平[4]等利用點角對Delaunay三角網格生成算法進行改進，提高了效率;陳明晶[5]等提出一種改進的Delaunay三角網生成算法，通過建立新的幾何拓撲關系提高網格生成效率;青文星[6]等提出了結合逐點和分治的快速Delaunay三角網格生成的方法。Gmsh[7]是一款開源網格剖分工具，可對2D/3D計算域進行網格剖分，但是該軟件目前并沒有支持直接生成邊界條件信息，如使用Gmsh生成的網格進行有限元分析，九需要額外的計算工作量指定邊界條件和材料信息。本文基于Delaunay算法，對計算域進行三角單元剖分，對計算域分塊，以支持對凹多邊形網格剖分，并在剖分過程直接生成邊界條件和材料信息，以便后期有限元計算使用。

1 基于Delaunay三角化的三角單元網格剖分

1.1 Delaunay三角化算法

對于二維平面內的點集[S]內的[p]點，存在一個區域，使得任意一個[S]點集內的[q]點到平面上任意一點[x]的距離都不小于[x]點到[p]點的距離，那么，該區域稱為點[p]的Voronoi區域，如圖1（a）。根據參考文獻[8] ，無限大二維平面Voronoi區域的定義為：

Voronoi圖是點集內所有點的Voronoi區域合集，也是由所有相鄰點構成的線段的垂直平分線所組成的連續多邊形集合。Delaunay圖是Voronoi圖的對偶圖，被中垂線分割的線段所組成的三角單元系列即為Delaunay圖，如圖1（b）。由點集生成Delaunay三角單元系列（普通三角單元不一定是Delaunay三角單元）的算法稱為Delaunay三角剖分算法。

Delaunay算法[8]可以將點集三角化，主要有“局部變換法”與“增量算法”，其中Bowyer-Watson算法是一種“增量算法”，步驟為：①構造一個包含所有點集在內的超級三角形（super triangle），該三角形既第一個剖分出來的三角單元;②將離散點逐個插入，查找包含該點的所有三角形的外接圓，標記這些三角單元;③刪除第②步中所標記的三角單元，連接插入點與第②步中標記的三角單元節點，形成新的三角單元;④插入其他新點，執行步驟②和③，直到插入所有點;⑤刪除超級三角形及其邊。