基于Delaunay算法含定解條件的三角單元網(wǎng)格生成

宋小鵬 古小敏 何秀錦 吳國(guó)珊 王斌武

（桂林航天工業(yè)學(xué)院能源與建筑環(huán)境學(xué)院， 廣西 桂林 541004）

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

關(guān)鍵詞： Delaunay算法; 網(wǎng)格生成; 有限元; 定解條件

中圖分類號(hào)：TP301.6? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：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三角化算法被廣泛用于有限元分析，很多學(xué)者對(duì)其算法做了大量研究：劉琴琴[1]對(duì)比了幾個(gè)平面域Delaunay三角網(wǎng)生成算法，并做了改進(jìn)工作;馮斌斌[2]等改進(jìn)了Delaunay三角網(wǎng)格的生成方法，可自適應(yīng)加密從而提高有限元計(jì)算精度;張晶飛[3]等討論了基于Delaunay三角化的最優(yōu)化網(wǎng)格節(jié)點(diǎn)生成算法。

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

1 基于Delaunay三角化的三角單元網(wǎng)格剖分

1.1 Delaunay三角化算法

對(duì)于二維平面內(nèi)的點(diǎn)集[S]內(nèi)的[p]點(diǎn)，存在一個(gè)區(qū)域，使得任意一個(gè)[S]點(diǎn)集內(nèi)的[q]點(diǎn)到平面上任意一點(diǎn)[x]的距離都不小于[x]點(diǎn)到[p]點(diǎn)的距離，那么，該區(qū)域稱為點(diǎn)[p]的Voronoi區(qū)域，如圖1（a）。根據(jù)參考文獻(xiàn)[8] ，無(wú)限大二維平面Voronoi區(qū)域的定義為：

Voronoi圖是點(diǎn)集內(nèi)所有點(diǎn)的Voronoi區(qū)域合集，也是由所有相鄰點(diǎn)構(gòu)成的線段的垂直平分線所組成的連續(xù)多邊形集合。Delaunay圖是Voronoi圖的對(duì)偶圖，被中垂線分割的線段所組成的三角單元系列即為Delaunay圖，如圖1（b）。由點(diǎn)集生成Delaunay三角單元系列（普通三角單元不一定是Delaunay三角單元）的算法稱為Delaunay三角剖分算法。

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