• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

      2012-04-17 09:30:22丁道紅
      關(guān)鍵詞:鄰點(diǎn)單胞三角網(wǎng)

      丁道紅,章 青

      (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.

      猜你喜歡
      鄰點(diǎn)單胞三角網(wǎng)
      基于單胞模型的三維四向編織復(fù)合材料力學(xué)性能研究
      基于NURBS的點(diǎn)陣材料參數(shù)化建模方法
      復(fù)合材料周期結(jié)構(gòu)數(shù)學(xué)均勻化方法的一種新型單胞邊界條件
      圍長為5的3-正則有向圖的不交圈
      考慮界面層影響的三維機(jī)織復(fù)合材料單胞模型研究
      針對(duì)路面建模的Delaunay三角網(wǎng)格分治算法
      特殊圖的一般鄰點(diǎn)可區(qū)別全染色
      清華山維在地形圖等高線自動(dòng)生成中的應(yīng)用
      笛卡爾積圖Pm×Kn及Cm×Kn的鄰點(diǎn)可區(qū)別E-全染色研究
      在AutoCAD環(huán)境下不規(guī)則三角網(wǎng)構(gòu)建及等高線生成
      茂名市| 昌宁县| 通化县| 浦东新区| 汶上县| 桃源县| 肇源县| 方城县| 辽源市| 老河口市| 固阳县| 巴林右旗| 台前县| 曲松县| 合作市| 海南省| 江城| 湟中县| 新巴尔虎左旗| 陆河县| 武鸣县| 白朗县| 安岳县| 康马县| 平阴县| 罗田县| 弋阳县| 新巴尔虎左旗| 绥阳县| 南平市| 双城市| 大荔县| 阳江市| 蓬莱市| 化隆| 长泰县| 龙山县| 诸暨市| 西安市| 河津市| 长丰县|