1、一種改進的全四邊形網格生成方法及優化李曉輝 , 李昌華(西安建筑科技大學 信息與控制工程學院 , 陜西 西安 710055)摘 要 :在任意二維區域的全四邊形網格生成方法中 ,鋪砌法是目前較好的一種方法 。但是當邊界出現不規則區域時 ,網格生成完畢后內部會產生一些質量較差的單元 ,且判斷網格交叉現象是否發生和解決網格交叉問題比較困難 。為了提高 該方法的適應性和可靠性 ,提出一種新的改進算法 ,它對邊界不規則區域網格生成和解決網格交叉問題等關鍵技術進行改 進 ,并加入四邊形網格優化方法 ,將改進后的鋪砌法應用于船舶有限元網格劃分中 ,取得了較好的應用效果 ,最后給出算例 進行了驗證 。關鍵詞

2、:網格生成 ; 四邊形單元 ; 網格優化 ; 鋪砌法中圖分類號 : t p391 . 7文獻標識碼 : a文章編號 :10042373 x (2010) 0820119204modif ied method and optimization of generating all2qua drilateral meshl i xiao2hui , l i chang2hua( info rmatio n and co nt rol enginee ring school , xian u nive r sit y of a rchitect ure and technolo gy , xian 7

3、10055 , china)ab stract : the paving met ho d a mo ng t he quadrilat eral me sh generatio n met ho ds in t he ar bit ra r y t wo2dimensio nal i s bet ter . ho wever , when ir regula r area i s appea red at t he bo r der , so me poo r me shes a re generated in t he inter nal a rea af ter me sh gen2 e

4、ratio n , a nd it i s difficult to deter mi ne cro ss2bo r der p heno meno n in ir regula r regio n and resolve t he cro ss2cut ting i ssue s. a mo dified al go rit hm i s p ropo sed to enha nce t he adap tabilit y and reliabilit y of t he met ho d. it imp ro ve s t he key technolo gie s of generati

5、ng me shes in ir regula r regio n a nd re solving t he cro ss2bo r der p ro blem. in co mbinatio n wit h t he quadrilateral mesh op ti2 mizatio n algo rit hm , t he i mp ro ved p aving met ho d wa s applied i n t he finite element meshing fo r a ship and a goo d eff ect wa s o b2 t ained. a n exa mp

6、le i s given fo r verif ying t he efficiency of t he p ropo sed met ho d.ke ywords : me sh generatio n ; quadrilateral element ; mesh op ti mizatio n ; paving met ho d里在該方法的基礎上進行了一些改進 ,即在每個新單元的生成過程中 ,隨時判斷有無交叉 ,現象發生 ,若出現交 叉則進行相交和縫合處理 ,而不是等待層生成完畢再處理 ,這樣相交判斷和處理就得到了很大的簡化。同時對小角度縫合處理做了改進 ,增強了邊界適應性。最后加 入網格

7、優化模塊 ,進一步提高了區域內部的網格質量 。0引言隨著計算機科學技術的快速發展 ,以有限元技術為代表的數值方法得到了廣泛應用 。然而 ,制約其進一步 發展的主要因素之一是網格劃分技術和優化技術 ,特別 是在船舶板架的有限元網格劃分中 ,由于精度和質量上 的考慮 ,要求網格單元盡量是四邊形。目前 ,網格生成 方法 1 主要有 dela una y 三角化方法、鋪砌法 ( pa vi ng) 、四 (八) 叉樹法、行波法等 2 。其中 , 鋪砌法是由 t. d . blacke r 和 m . b . st ep he n so n 提出的 3 ,該算法重復地 在區域邊界內部放一層或者鋪一層單元

8、 ,從區域邊界開 始向內部形成四邊形單元。whit e 4 重新設計了鋪砌 算法 ,單元不是生成一排 ,而是一個接一個的生成 ,它生 成的網格質量和靈活性要優于其他算法 ,尤其是邊界單 元 (接近正方形) 5 。方興、張武等 6 在 whit e 的基礎上 對鋪砌法做了改進 ,主要是提出一種節點計算方法 ,但 是在復雜區域的相交和縫合處理等方面仍有不足 。這1鋪砌法網格生成算法鋪砌法是一種全自動的網格生成方法 ,它不要求預先配置好內部節點 ,單元和節點都在網格劃分的過程中 自動生成。1 . 1輸入初始條件與起始點的選擇為了保證在區域內生成的單元全部為四邊形單元 , 要求初始邊界上的節點數目為偶

9、數個 。在鋪砌過程中 , 首先要在邊界上選擇網格生成的起始點 ,為了方便生成 網格節點 , 本文取鋪砌邊界上內角最小的節點為起 始點。1 . 2網格單元的生成 新節點一般是以邊界上相鄰的三點為基礎的 ,并以一定的角度和方向向區域內部投射而生成。如 :新節點119收稿日期 :2009211226基金項目 :國家自然科學基金資助項目( 50878176)的生成是以當前邊界上 n i - 1 , n i , n i +1 這 3 個節點為基礎的 , 假設節點 n i 的內角為; 節點 n i - 1 到節點 n i 的距 離為 d1 ; 節點 n i 到 n i +1 的距離為 d2 , 則根據節點

10、夾角的不同可分為四種類型 , 即 :終止節點 : 120°+; 邊界節點 :120°+ < 240°+; 角節點 :240°+ < 300°+; 轉角節點 : > 300°+。其中 , 取 5°< < 10°。界上 n i 的前一節點和后一節點。如果 n i - 1 也為終止節點 , 則 n j , n i - 1 , n i , n i +1 就構成一個單元 。以邊節點為基點的生成方法1 . 2 . 1如圖 1 (a) 所示 , 由節點 n i - 1 , n i , n i +1

11、組成當前鋪砌邊界 , 生成新節點 n j , 同時這四個節點形成了一個新 單元。設新節點是由矢量 v 所決定的 ,v 平分內角, 長 度由下式定義 :圖 2 角節點生成法圖 3 轉角節點生成法d1 + d2( 1)| v | =2 si n (/ 2)對于兩節點皆為邊節點的特殊情況下新節點的生成如圖 1 ( b) 所示。按照邊節點的生成算法 ,由節點 n i 生成新節點 n j , 由節點 n i +1 生成新節點 n k , 同時這 四個節點形成一個新單元。圖 4 終止節點生成法2相交處理在網格生成過程中 ,本文對邊界相交處理順序進行了調整。在新單元的生成過程中 ,隨時判斷有無交叉現 象的發

12、生 ,若出現交叉則立即進行相交處理 ,這樣只是 局部個別網格的交叉和重疊 ,簡化了對交叉重疊問題的 處理 ,也使算法更加穩定可靠 。2 . 1 相交判斷在鋪砌過程中 ,當鋪砌邊界與自己或其他鋪砌邊界 相交時 ,則至少存在一對邊相交如圖 5 ( a ) 所示。通過 判斷線段是否相交即可確定鋪砌邊界是否相交 , 假設 a b 與 cd 為兩條相交線段 , a 表示為從原點到 a 點的矢量; b 表示為從 a 點到 b 點的矢量; c表示為從原點到 c 點的矢量; d 表示為從 c 點到 d 點的矢量 , 則線段 a b 上 p 點的位置矢量和線段 cd 上 q 點的位置矢量分別 表示為 :圖 1

13、邊界點生成法1 . 2 . 2以角節點為基點的生成方法如圖 2 所示 ,由 n i - 1 , n i , n i +1 生成三個新節點 n j , n k , n i , 同時形成了兩個新單元。三個節點分別由矢量v j ,v k ,v l 決定 。矢量 v j ,v k ,v l 與 n i - 1 n i 的夾角分別為/ 3 ,/ 2 , 2/ 3 , 長度由下式定義 :d1 + d22 | v j | , | v l | v j |= 2 si n (/ 3) , | v k |= | v j |= a + ub , u 0 , 1 = c + w d , w 0 , 1 ( 2)p (

14、 u)q ( u)( 4)1 . 2 . 3以轉角節點為基點的生成方法如圖 3 所示 ,由 n i - 1 , n i , n i +1 三點生成五個新節 點 n j , n k , n l , n m , n n 同時形成了三個單元。五個新節點分別由矢量 v j ,v k ,v l ,v m ,v n 決定。矢量 v j ,v k ,v l ,v m ,v n 與 n i - 1 n i 的夾角分別為/ 4 , 3/ 8 ,/ 2 , 5/ 8 ,3/ 4 , 長度由下式定義 :當線段 a b 和 cd 相交時 ,則在交點處有 :p ( u) = q ( u)或a + ub = c + w

15、d由式 (5) 轉化為線性方程組 ,可得 :ax + ub x = cx + w d x( 5)d1 + d22 | v j | ,( 6)| v j |= 2 si n (/ 4) , | v k |=ay + ub y =cy + w d y( 3)| v l | = | v j | , | v m | = | v k | , | v n |1 . 2 . 4以終止節點為基點的生成方法= | v j |令 :b xby- d x- dy( 7)h =如圖 4 所示 ,在網格生成過程中 ,遇到終止節點時線段相交 ,相交的相對位置由式 ( 7 ) 解得的 u , w 值而定。有了這些信息 ,就

16、可以計算出適當的方式進行相交 處理。上生成的網格將會產生畸變。此時可以通過嵌入單元 ,改變節點連接來處理。如圖 7 所示 ,如果兩相鄰邊的長 短比值大于設定值 ( 本文取 2) 時 , 則應該在長邊插入 一個楔形單元來改善相鄰邊的過渡。在長邊中點增加 一節點 d , 且節點 d 在 2/ 3 位置處 。圖 5 相交判斷圖示2 . 2相交處理在生成新單元的過程中 ,一旦判斷到相交情況的發 生 ,就立即轉入相交處理模塊進行相交的處理。根據最 近原則重新連接 ,形成新的鋪砌邊界 。如果當前邊界與 自己發生相交 ,則邊界分割后形成兩個新的鋪砌邊界 ; 如果是與其他邊界相交 ,則兩條邊界連接后合并為一條

17、 鋪砌邊界 ,如圖 5 ( b) 所示。但前提是保證新生成的鋪 砌邊界上的節點數為偶數 ,若為奇數 ,則通過調整相應 的參數 u 和 w 來調整分割或連接的位置 。相交處理完 之后要進行縫合和光順處理。圖 7 過渡縫合處理4網格質量優化一般情況下 , 用上述算法生成的網格并不是最優的 ,其中包含有一些質量較差的單元 ,要對其進行網格 優化 ,以便盡量減少不規則單元的數目。網格優化技術 大致可分為兩類 :拓撲優化和幾何優化 8 。幾何優化是 調整網格中的節點位置 ,提高單元的幾何質量 ,而節點之間連接關系保持不變 。與此相對 ,改變節點之間的連 接關系的網格優化技術則稱為拓撲優化。4 . 1 網

18、格拓撲優化拓撲關系是指網格節點的連接關系 ,拓撲關系的調 整是指改變節點之間的連接關系 ,也包含通過增加或刪3縫合處理網格生成的過程中 ,可能會出現內角較小的節點 ,這時可以通過小角度縫合處理來消除此夾角 ,有時也可 能會出現相鄰邊長短懸殊較大的情況 ,此時可通過過渡縫合處理的辦法使過渡更加均勻化 7 。3 . 1小角度縫合處理 當浮動邊界上節點的內角小于某一給定的閾值時 ,將會在網格中形成一道細縫 ,此時應該進行小角度縫合 處理 , 以便于后續網格的生成和提高網格的質量 , 如 圖 6所示。 9 除網格中的節點。對四邊形網格而言 ,四邊形單元的最佳形狀是正方 形 ,其內角為 90°

19、,因而 ,其內部節點的相鄰單元個數 n e (節點周圍的單元數目) 最好為 4 ,這樣可以使這一結點 的周圍單元在此點的平均內角為 90°。當某一個內部 節點的 n e 比 4 大或小很多時 ,環繞該節點的單元就會 產生很大的畸變 ,此時 ,就應該對其調整 ,主要的調整方 法有單元刪除和單元交換 。4 . 1 . 1單元刪除 通過刪除某些單元可以改變局部的網格質量 ,單元刪除涉及到三個檢測 :節點檢測 、邊檢測和單元檢測。 (1) 節點檢測 。如果某一節點周圍只有兩個單元 , 并且該節點不在約束邊界上 ,則該節點刪除 ,以該節點 為端點的兩條邊也同時刪除 , 兩個單元合并為一個單 元

20、 ,如圖 8 (a) 所示。通過刪除這些節點 ,可以很好地刪除對網格質量有重要影響的凹四邊形 。(2) 邊檢測。如果某一邊的兩個端點周圍都是圖 6 小角度縫合處理圖 6 中 : n e 為節點內角頂點處與節點相連的邊數 ; 為 節點內角; n n 為縫合后與縫合節點相連的邊數 , 其 選取準則是根據節點內角大小和 n e 決定 ,即 : 15°, n e 5 30°, 其他 分別采取圖 5 (a) , ( b) 的方法。3 . 2過渡縫合處理當網格生成單元的相鄰邊長比例過大時 ,在此基礎三個單元 , 如圖 8 ( b) 所示 , 刪除該邊和兩個單元e1 ,e2 。新四邊形有

21、兩種選擇 , 取 n e 值最小的為最終邊。121(3) 單元檢測。如果某一四邊形單元 e1 的對角線上兩端的節點 n 1 , n 2 周圍都是三個單元 , 則應該刪除 四邊形單元 e1 應該刪除 , 同時 n 1 和 n 2 合并為一個節點 ,如圖 8 (c) 所示。n i1= x jx ini j = 1( 8)n i 1 =y jy ini j = 1式中 : n i 是與節點 i 相鄰的節點總數 ; j 是與 i 相連的節點 ; x j 和 y j 是節點 j 的坐標值。使用這種方法簡單可 靠 ,計算效率高 ,對網格質量的提高起到了非常重要的作用。但是 l ap lace 修勻同樣也具

22、有準則法所固有的 不足 ,最根本的問題在于不能確定修勻后的網格是否為 最優網格。圖 10 給出網格優化前后的比較 。由于鋪砌 法由于是從邊界向區域內部生成單元 ,所以內部單元的 質量比較差 。圖中經 l ap lace 修勻后 ,中心的網格質量得到提高。圖 8 節點刪除 、邊刪除和單元刪除4 . 1 . 2單元交換 依次對所有由內部節點連接的單元邊進行檢驗 ,如圖 9 (a) 所示 ,若滿足 n e ( a ) + n e ( b ) 9 , 公共邊 a b將被調換成 cd 或者 e f , 單元邊滿足以下關系 :n e ( a ) + n e ( b ) ; n 2n 3 = n e ( e

23、)n e ( c) + n e ( d) ;n 1=+ n e ( f)圖 10 網格修勻(1) n 1 n 2 + 3 且 n 3cd , 如圖 9 ( b) 所示。( 2) n 1 n 3 + 3 且 n 2e f , 如圖 9 (c) 所示。 n 2 公共邊 a b 調換成5網格生成實例 n 3 公共邊 a b 調換成圖 11 給出用上述鋪砌法生成的網格圖 。由圖中可以看出 ,區域邊界幾何形狀復雜 ,截面變化較大 ,屬于復 雜邊界情況 。但從生成的網格來看 , 不僅邊界擬合良 好 ,而且網格質量較高。圖 9 單元交換4 . 2 網格幾何優化網格的幾何優化處理指網格生成后進行的網格調 整

24、,在保證單元尺寸、單元節點的拓撲關系的基礎上 ,進行單元節點的重新布置。大部分的幾何優化算法都是以某種順序遍歷網格中的節點 ,逐個調整節點位置 ,提 高單元質量。在網格幾何優化過程中 ,普遍采用的技術 是拉普拉斯光順處理 (l ap lacia n smoo t hi ng) 。目前為止拉普拉斯光順處理應用得最廣泛 、最有 效 ,同時也是最成熟的網格優化方法 10 。拉普拉斯光 順算法的基本原理是保持網格拓樸關系不變 ,將整個內 部節點的位置移動到由其相鄰節點組成的多邊形形心 位置 ,從而優化每個單元的形狀。將這個移動過程遍歷所有內部節點若干次 ,可較大地提高網格質量。拉普拉圖 11 網格生成

25、實例6結語通過對鋪砌法進行了的改進 ,實現了對任意復雜區域全四邊形網格的自動劃分。與原算法相比 ,本算法的 優越性主要體現在 :在網格生成之前對初始邊界進行先處理 ,增強了程序的適應性 ; 原算法中待一層單元生成 完畢后再進行相交處理 ,本文采用邊生成邊進行相交判 斷 ,一旦發現相交情況 ,立即轉入相交處理模塊 ,使相交 處理極為方便 ;縫合處理時 ,對不同小角度進行分組縫 合處理 ,提高了網格單元的質量 ; 最后通過幾何優化和此 ,本文將截集 fcm ( sfcm ) 聚類算法和特征加權fcm ( w fcm) 聚類算法相結合 ,提出了截集型特征加 權模糊 c2均值 ( sw fcm ) 聚

26、類算法 。實驗結果表明 , sw fcm不僅具有良好的特征選擇能力和很強的抗噪 聲性能 ,而且具有較高的收斂速度 ,是一種經濟有效、可 供選擇的聚類算法。to t yp es and at t ribute weight s j . pat ter n reco gnitio n ,2004 , 37 (3) : 5672581 . 5 李潔 , 高新波 , 焦李成. 基于特征加權的模糊聚類新算法j . 電子學報 , 2006 , 34 (1) : 89292 . 6 h u n g w l , ya n g m s , c h en d h . boo t st rapping ap2 p

27、roach to f eat ure2weight selectio n in f uzzy c2mea ns algo2 rit hms wit h a n applicatio n i n colo r i mage segmentatio n j . pat ter n reco gnitio n l et ter s , 2008 , 29 (9) : 131721325 . 7 陳新泉. 特征加權的模糊 c 聚類算法j . 計算機工程與設計 , 2007 , 28 (22) : 532925333 . 8 裴繼紅 , 范九倫 , 謝維信. 一種新的高效軟聚類算法 : 截集 模糊 c2

28、均值聚類算法j . 電子學報 ,1998 , 26 (2) : 83286 . 9 ya n g miin2shen , wu kuo2l ung. alp ha2cut implement ed f uzzy cl ustering algo rit hms and switching regre ssio ns j . ie e e tra ns. o n systems , ma n a nd cyber netic s , part b ,2008 , 38 (3) : 5882603 . 10 l i y h , don g m , h u a j . localized f eat

29、 ure selectio n fo r cl ustering j . pat t er n reco gnitio n l et ter s , 2008 , 29 (1) : 10218 . 11 bl a ke c l , m erz c j . u ci repo sito r y of machine lea r ning databa ses eb/ ol . 1998207220 . ht tp : / / a r2chive . ic s. uci . edu/ ml/ .參 考 文 獻 1 c h ie h yu a n tsai , c h iu chua ng2chen

30、g. developing a f eat ure weight self2adj ust ment mecha ni sm fo r a k2mea ns cl ustering algo rit hmj . co mp utatio nal stati stic s a nd data a nalysi s ,2008 , 52 (10) : 465824672 . 2 j in g l , n g m k , h u a n g j z. a n ent rop y weighting k2means algo rit hm fo r subspace cl ustering of hi

31、gh2dimen2 sio nal spa r se dat a j . ie e e tra ns. o n kno wledge and da2 t a engineering , 2007 , 19 (8) : 102621041 . 3 wa n g x z , wa n g y d , wa n g l j . imp ro ving f uzzy f eat ure c2means cl ustering ba sed o n f eat ure2weight lea r ning j . pat ter n reco gnitio n l et ter s , 2004 , 25

32、 ( 10 ) :112321132 . 4 fr i gu i h , n a srao u i o . u nsup ervi sed lea r ning of p ro2作者簡介 : 支曉斌 男 ,1976 年出生 ,內蒙古巴彥淖爾人 ,在職博士研究生 , 講師 。研究方向為模式識別 、模糊集理論及其應用 。范九倫 男 ,1964 年出生 ,陜西西安人 ,教授 ,博士生導師 。研究方向為模糊集理論、模式識別與圖像處理、智能信息 處理 。element meshing c / / proce ssi ngs of 6t h inter natio nal me s2hing ro undta ble s. l : s. n. , 1997 : 3232335 . 5 龔光彩 , 張文宏 , 孫培雷 , 等. 網格自動生成技術進展綜論j . 建筑熱能通風空調 , 2006 , 25 (1) :26231 . 6 方興 , 張武 , 唐錦春 , 等. 一種改進的生成有限元全四邊形 網格 的 鋪 砌 法 j . 浙 江 理 工 大 學 學 報 , 2005 , 22 ( 1 ) :70273 . 7 賈虹 , 盧炎麟 , 高發興 , 等. 高品質全四邊形有限元網格生 成的 鋪 砌 法 j .