基于Delaunay三角網(wǎng)的三維Voronoi單胞體積計(jì)算

丁道紅,章 青

(1.河海大學(xué)水文水資源與水利工程科學(xué)國家重點(diǎn)實(shí)驗(yàn)室,江蘇南京 210098;2.河海大學(xué)力學(xué)與材料學(xué)院,江蘇南京 210098)

Voronoi單胞是以自然相鄰插值法進(jìn)行形函數(shù)構(gòu)造的自然單元法的基礎(chǔ)[1-2]。自然單元法形函數(shù)的構(gòu)造方法有Sibson法[3]和Laplace法[4]2種,其中Sibson法是以插值點(diǎn)對(duì)應(yīng)于某一結(jié)點(diǎn)的二階Voronoi單胞的勒貝格測(cè)度與插值點(diǎn)的一階Voronoi單胞的勒貝格測(cè)度的比值作為形函數(shù)。三維Voronoi單胞的勒貝格測(cè)度即為Voronoi單胞的體積,目前關(guān)于Voronoi單胞體積的計(jì)算最常用的方法是Lasserre方法[5-8]。Lasserre方法是在已知凸多面體控制方程的前提下,通過遞推公式求得凸多面體的體積。該方法因具有簡單可行、操作方便等優(yōu)點(diǎn)而得到廣泛的應(yīng)用,但該方法在應(yīng)用過程中要求控制方程不能存在冗余的方程。本文在與Voronoi單胞相對(duì)應(yīng)的Delaunay三角網(wǎng)的啟示下,通過Delaunay三角網(wǎng)將三維Voronoi單胞劃分成若干個(gè)不重疊且充滿Voronoi單胞的四面體,從而可簡單地通過四面體的體積計(jì)算得到Voronoi單胞的體積。

1 Voronoi單胞

對(duì)于Voronoi單胞的概念[9],可通過數(shù)學(xué)方式進(jìn)行描述。記Rn空間上任意2點(diǎn)xI和xJ的歐氏距離為d(xI,xJ),設(shè)P={x1,…,xn}為Rn空間上任意n個(gè)互異的點(diǎn),則與其中任意一點(diǎn)xI對(duì)應(yīng)的Voronoi單胞的定義為

二階Voronoi單胞是在Rn空間上任意n個(gè)互異的點(diǎn)P={x1,…,xn}的基礎(chǔ)上,增加一新的待插值點(diǎn)x′,形成新的一階Voronoi單胞,其中結(jié)點(diǎn)xI為插值點(diǎn)x′的自然鄰點(diǎn),結(jié)點(diǎn)xI的二階Voronoi單胞為結(jié)點(diǎn)xI的一階Voronoi單胞與插值點(diǎn)x′的一階Voronoi單胞重疊的部分,即

將具有公共邊界的Voronoi單胞所對(duì)應(yīng)的結(jié)點(diǎn)稱為自然鄰點(diǎn),其公共邊界為該2點(diǎn)的中垂面(二維問題為2點(diǎn)的垂直平分線),即2自然鄰點(diǎn)xI和xJ的Voronoi單胞公共邊界所在的平面(或直線)L為

其法線方向?yàn)榻Y(jié)點(diǎn)xI指向xJ。與結(jié)點(diǎn)xI對(duì)應(yīng)的Voronoi單胞在平面(或直線)L的結(jié)點(diǎn)xI所在的一側(cè),即結(jié)點(diǎn)xI對(duì)應(yīng)的Voronoi單胞滿足

假設(shè)結(jié)點(diǎn)xI(xI,yI,zI)為插值點(diǎn)xp(xp,yp,zp)的1個(gè)自然鄰點(diǎn),與結(jié)點(diǎn)xI(xI,yI,zI)對(duì)應(yīng)的自然鄰點(diǎn)共有m個(gè),分別為(x1,y1,z1),…,(xm,ym,zm),則與結(jié)點(diǎn)xI對(duì)應(yīng)的二階Voronoi單胞可寫成

令

則式(5)可寫為

式(6)描述了二階Voronoi單胞的控制域,若能得到二階Voronoi單胞的頂點(diǎn),則可通過Delaunay三角網(wǎng)將控制域劃分成若干個(gè)小域進(jìn)行分析。因此若要得到二階Voronoi單胞的勒貝格測(cè)度,首先需要得到二階Voronoi單胞的頂點(diǎn)。二階Voronoi單胞的頂點(diǎn)是邊界的交點(diǎn),即式(6)取等號(hào)時(shí)所得的滿足式(6)的點(diǎn)。對(duì)于n維空間問題,通過聯(lián)立式(6)中n個(gè)方程,建立1個(gè)新的方程組

若|A|≠0,則式(7)必有解

若x=A-1b滿足式(6),則為二階Voronoi單胞的1個(gè)頂點(diǎn)。

2 Delaunay三角網(wǎng)

Delaunay三角網(wǎng)的概念是建立在Voronoi單胞基礎(chǔ)之上的。將具有公共邊界的Voronoi單胞所對(duì)應(yīng)的結(jié)點(diǎn)連接所得到的三角形,稱作Delaunay三角形,將Rn空間上任意n個(gè)互異的點(diǎn)通過Delaunay三角形劃分,可形成Delaunay三角網(wǎng)。

文獻(xiàn)[10]證明了Delaunay三角網(wǎng)具有如下性質(zhì)。

a.唯一性：不論從區(qū)域何處開始構(gòu)建,最終都得到一致的結(jié)果。

b.最優(yōu)性：任意2個(gè)相鄰三角形形成的凸四邊形的對(duì)角線如果可以互換,那么2個(gè)三角形6個(gè)內(nèi)角中最小的角度不會(huì)變大。

c.最規(guī)則：如果將三角網(wǎng)中每個(gè)三角形的最小角進(jìn)行升序排列,則Delaunay三角網(wǎng)的排列得到的數(shù)值最大。

d.具有凸多邊形的外殼：三角網(wǎng)最外層的邊界形成1個(gè)凸多邊形的外殼。

以上這些性質(zhì)保證了Delaunay三角網(wǎng)所劃分的區(qū)域不具有重疊部分,且能覆蓋結(jié)點(diǎn)所占的凸區(qū)域。

目前關(guān)于Delaunay三角網(wǎng)劃分的方法很多[11-12],如Lawson算法、Bowyer-Watson算法等。此外,一些商業(yè)軟件具有成熟的Delaunay三角網(wǎng)劃分的功能,如MATLAB軟件中,可通過Delaunay命令進(jìn)行相關(guān)工作。

在三維問題中,通過Delaunay三角網(wǎng)劃分所得的基本體為四面體,四面體的體積可通過簡單的幾何方法得到,如已知某四面體的4個(gè)頂點(diǎn)分別為(x1,y1,z1),(x2,y2,z2),(x3,y3,z3),(x4,y4,z4),則該四面體的體積為

3 算 例

已知三維空間8結(jié)點(diǎn)1(0,0,0),2(1,0,0),3(1,0,1),4(0,0,1),5(0,1,0),6(1,1,0),7(1,1,1),8(0,1,1),插值點(diǎn)xp(0.7236,0.1382,0.1382),則結(jié)點(diǎn)6為插值點(diǎn)的自然鄰點(diǎn)。結(jié)點(diǎn)6的自然鄰點(diǎn)有3個(gè),分別為2,5,7。結(jié)點(diǎn)6的二階Voronoi單胞為

其中

通過式(10)中任取3個(gè)方程并取等號(hào)進(jìn)行聯(lián)立方程,代入上式進(jìn)行判斷是否符合要求,可得結(jié)點(diǎn)6的二階Voronoi單胞的頂點(diǎn)為(0.5,0.5,-1.0854),(1.2927,0.5,0.5),(0.5,0.7542,0.5),(0.5,0.5,0.5)共4個(gè)結(jié)點(diǎn),通過Delaunay三角網(wǎng),可劃分成1個(gè)四面體,通過式(8)可知其體積為0.0533。

4 結(jié) 語

在已知Voronoi單胞頂點(diǎn)的前提下,利用Delaunay三角網(wǎng)將Voronoi單胞劃分成若干四面體,通過求解四面體的體積得到Voronoi單胞的體積。該方法具有原理簡單、可行性強(qiáng)、理解性好等優(yōu)點(diǎn)。

此外,該方法不僅可以應(yīng)用于三維Voronoi單胞的體積計(jì)算,對(duì)于任意1個(gè)已知邊界頂點(diǎn)的凸多面體均可應(yīng)用該方法進(jìn)行體積的計(jì)算。

[1]BRAUN J,SAMBRIDGEM.A numerical method for solving partial differential equations on highly irregular evolving grids[J].Nature,1995,376：655-660.

[2]SUKUMAR N,MORAN B,BELYTSCHKO T.The natural element method in solid mechanics[J].International Journal for Numerical Methods in Engineering,1998,43(5)：839-887.

[3]SIBSON R.A brief description of natural neighbour interpolation[G]//BARNETT V.Interpreting Multivariate Data.New York：Wiley,1981：21-36.

[4]BELIKOV V V,SEMENOV A Y.Non-Sibsonian interpolation on arbitrary system of points in Euclidean space and adaptive isolines generation[J].Applied Numerical Mathematics,2000,32(4)：371-387.

[5]LASSERRE JB.An analytical expression and an algorithm for the volume of a convex polyhedron inRn[J].Journal of Optimization Theory and Applications,1983,39(3)：363-377.

[6]LASSERREJB.A laplace transform algorithm for the volume of a convex polytope[J].Journal of the ACM,2001,48(6)：1126-1140.

[7]王建華,張英新,高紹武.三維彈塑性自然單元法算法實(shí)現(xiàn)[J].計(jì)算力學(xué)學(xué)報(bào),2006,23(5)：594-598.(WANG Jianhua,ZHANG Yingxin,GAO Shaowu.The computational methods of natural element method in three dimensional elasto-plastic analysis[J].Chinese Journal of Computational Mechanics,2006,23(5)：594-598.(in Chinese))

[8]江濤,章青.基于Lasserre算法的自然單元法形函數(shù)計(jì)算[J].力學(xué)與實(shí)踐,2008,30(4)：1-5.(JIANG Tao,ZHANGQing.The shape functions in the natural element method based on Lasserre's algorithm[J].Mechanics in Engineering,2008,30(4)：1-5.(in Chinese))

[9]楊永清,馮鈞,王志堅(jiān).基于Voronoi圖的復(fù)雜對(duì)象空間方位關(guān)系的推理計(jì)算[J].河海大學(xué)學(xué)報(bào)：自然科學(xué)版,2008,36(3)：414-417.(YANG Yongqing,FENG Jun,WANG Zhijian.Reasoning and calculation of spatial direction relationship between complex objects based on Voronoi diagram[J].Journal of Hohai University：Natural Sciences,2008,36(3)：414-417.(in Chinese))

[10]SEIDEL R.The upper bound theorem for polytopes：an easy proof of its asymptotic version[J].Computational Geometry,1995,5(2)：115-116.

[11]王建華,徐強(qiáng)勛,張銳.任意形狀三維物體的Delaunay網(wǎng)格生成算法[J].巖石力學(xué)與工程學(xué)報(bào),2003,22(5)：717-722.(WANG Jianhua,XUQiangxun,ZHANG Rui.Delaunay algorithm and related procedure to generate the tetrahedron mesh for an object with arbitrary boundary[J].Chinese Journal of RocKMechanics and Engineering,2003,22(5)：717-722.(in Chinese))

[12]WATSON D F.Computing then-dimensional delaunay tessellation with application to Voronoi polytopes[J].The Computer Journal,1981,24(2)：167-172.