基于STL快速重構(gòu)平面有限元網(wǎng)格邊界

王家林，張德立，何 琳

(重慶交通大學(xué)土木建筑學(xué)院，重慶400074)

在有限元分析中，有時(shí)需要找出模型的邊界進(jìn)行某些特殊的處理，如對于多連通截面的扭轉(zhuǎn)問題，需要在外邊界上施加應(yīng)力函數(shù)為零的約束條件，在內(nèi)邊界上施加應(yīng)力函數(shù)相等的約束條件［1］。如果基于幾何來建立有限元網(wǎng)格，則邊界是預(yù)先已知的;如果直接從其它有限元軟件中導(dǎo)入網(wǎng)格數(shù)據(jù)，則邊界需要根據(jù)網(wǎng)格數(shù)據(jù)分析得到。所以，快速、高效率地根據(jù)有限元網(wǎng)格數(shù)據(jù)找出模型邊界成為算法優(yōu)化的一部分。

筆者針對多連通截面的平面有限元網(wǎng)格，靈活應(yīng)用C++標(biāo)準(zhǔn)模板庫(簡稱 STL)中的 vector、list、set和map容器，研究了快速分析模型邊界的方法，并成功地應(yīng)用于多連通截面扭轉(zhuǎn)問題的有限元分析中。

1 C++STL中基本容器的特點(diǎn)

C++標(biāo)準(zhǔn)模板庫STL是C++的組成部分，提供了大量的可復(fù)用軟件組件，包含了vector、list、set、map等容器及算法，其實(shí)現(xiàn)速度和內(nèi)存利用方面都是高效的［2］。充分利用STL技術(shù)能夠極大地提高應(yīng)用程序的開發(fā)效率，殷際英［3］將STL技術(shù)用于邊界元程序設(shè)計(jì)中，解決大量數(shù)據(jù)的動(dòng)態(tài)存儲和內(nèi)存分配問題;李余江，等［4］運(yùn)用STL技術(shù)以向量模板類的特化繼承對象為變?nèi)萘繑?shù)據(jù)容器編制了面向?qū)ο蟮挠邢拊绦?唐麗玉，等［5］和吳小平，等［6］將 STL 技術(shù)用于Delaunay三角形網(wǎng)格的高效構(gòu)建。

vector是一種連續(xù)存放、可根據(jù)序號隨機(jī)訪問數(shù)據(jù)元素的容器，在所有容器中具有最高的元素訪問效率。不過在插入和刪除元素時(shí)會(huì)產(chǎn)生內(nèi)存塊的拷貝，當(dāng)內(nèi)存空間不夠時(shí)，需要重新申請一塊足夠大的內(nèi)存并進(jìn)行內(nèi)存的拷貝，導(dǎo)致執(zhí)行時(shí)間增加。

list是STL提供的雙向鏈表，它的數(shù)據(jù)元素在內(nèi)存空間不必連續(xù)存放，插入和刪除數(shù)據(jù)元素的效率高。list數(shù)據(jù)結(jié)構(gòu)只具有順序訪問數(shù)據(jù)元素的能力，不能通過序號直接訪問一個(gè)指定的數(shù)據(jù)元素。

set容器使用一種稱為紅黑樹的平衡二叉檢索樹結(jié)構(gòu)來組織泛化的元素?cái)?shù)據(jù)，其每個(gè)節(jié)點(diǎn)包含一個(gè)取值紅色或黑色的顏色域來進(jìn)行樹的平衡處理，不會(huì)將重復(fù)的鍵值插入容器，也不需要指定具體的插入位置，而按元素在樹中的關(guān)聯(lián)關(guān)系，進(jìn)行位置檢索和插入，元素的刪除亦然。元素?cái)?shù)據(jù)的檢索，使用的是二叉檢索樹的中序遍歷算法，檢索的效率高于vector、deque 和 list等容器。

map映照容器由一個(gè)鍵值和其它若干數(shù)據(jù)(映照數(shù)據(jù))組成，鍵值和映照數(shù)據(jù)之間，可建立一個(gè)數(shù)學(xué)上的映照關(guān)系。容器的數(shù)據(jù)結(jié)構(gòu)同樣是采用紅黑樹進(jìn)行管理，插入的元素鍵值不允許重復(fù)，所使用的節(jié)點(diǎn)元素的比較函數(shù)，只對于元素的鍵值進(jìn)行比較，元素的各項(xiàng)數(shù)據(jù)可通過鍵值檢索出來。故它能快速查找、插入、刪除元素。

2 網(wǎng)格邊界的分析方法

2.1 單元節(jié)點(diǎn)編號的存儲方式

對于一個(gè)確定的有限元網(wǎng)格，單元個(gè)數(shù)及每類單元的節(jié)點(diǎn)個(gè)數(shù)是已知的，因此為了提高數(shù)據(jù)訪問效率，對于每個(gè)單元采用了vector＜int＞數(shù)據(jù)類型存儲各節(jié)點(diǎn)編號。

2.2 邊界的判別方法

在平面有限元網(wǎng)格中，一條邊如果只在一個(gè)單元中出現(xiàn)，則該邊為邊界上的邊，一條邊如果被兩個(gè)單元共有則不是邊界。例如，對于簡單網(wǎng)格(圖1)，只屬于單元1的邊(2 7 4)是邊界。既屬于單元1又屬于單元2的邊(4 8 5)就不是邊界。

圖1 平面有限元網(wǎng)格示例Fig.1 Plane finite element mesh

2.3 利用set容器分析邊界

在查找模型邊界的過程中，約定單元的每個(gè)邊采用該邊上節(jié)點(diǎn)編號按逆時(shí)針方向組成的字符串表示。例如，對于圖1的平面有限元網(wǎng)格，單元1的邊為“2 7 4”、“4 8 5”和“5 6 2”，單元2的邊為“4 9 3”、“3 10 5”和“5 8 4”。很顯然，不在模型邊界上的邊會(huì)以相反的節(jié)點(diǎn)順序出現(xiàn)兩次，如單元1的邊“4 8 5”和單元2的邊“5 8 4”。于是，可以采用下面步驟來實(shí)現(xiàn)邊界的快速識別:

1)建立一個(gè)存儲字符串的set，用以保存分析過程中識別出來的邊界。

2)對于單元的每一個(gè)邊，按單元順時(shí)針方向?qū)⑦吷系墓?jié)點(diǎn)編號組成字符串，用該字符串在set中查找有無該字符串:①如果在set中找到該字符串，說明此字符串表示的邊為第2次出現(xiàn)，不是模型邊界，則從set中將該字符串刪除;②如果在set中找不到該字符串，表明此字符串表示的邊為第1次出現(xiàn)，可能是模型邊界，則將該邊上的節(jié)點(diǎn)的編號按單元逆時(shí)針方向組成字符串后加入set中。

3)當(dāng)全部單元的所用邊均按照步驟2)分析處理完畢后，則set中的字符串標(biāo)記出的邊為模型的邊界。

按照上述算法，set中不是模型邊界的邊能夠及時(shí)從set中刪除，使set容器中的元素個(gè)數(shù)盡可能少，從而提高查詢效率。

2.4 利用map容器分析邊界環(huán)線

盡管set容器中的字符串標(biāo)記了模型的邊界，但各個(gè)邊處于散亂狀態(tài)，沒有連接成邊界環(huán)線，扭轉(zhuǎn)分析需要能識別出每一個(gè)邊界環(huán)線。在圖1中，處于單元1的邊界(2 7 4)和處于單元2中的邊界(4 9 3)是相連接的。可見兩條相連的邊界，其中一條的末尾節(jié)點(diǎn)號正好是另一條的首節(jié)點(diǎn)號?；诖颂攸c(diǎn)，即可建立形成邊界環(huán)線的算法。

2.4.1 生成邊界map

從前述set中取出各邊界邊組成的字符串，以首節(jié)點(diǎn)號為關(guān)鍵字、字符串為數(shù)據(jù)形成map，具體算法步驟為:

1)建立一個(gè)以整數(shù)為鍵值，數(shù)據(jù)為字符串的map。

2)按順次遍歷的方式訪問set中的每個(gè)元素(即表示每個(gè)邊的字符串)，獲得第1個(gè)節(jié)點(diǎn)編號，以第1個(gè)節(jié)點(diǎn)編號為鍵值、以字符串為映照數(shù)據(jù)生成一個(gè)元素添加到map中。例如，對于單元2中的邊(3 10 5)，在 set存放為字符串“3 10 5”，就以“3”為鍵值、“3 10 5”為映照數(shù)據(jù)插入map中。

對set中每個(gè)元素執(zhí)行完畢后，map中每個(gè)元素的鍵值表示了一個(gè)邊的起始節(jié)點(diǎn)，其數(shù)據(jù)字符串表明了該邊上的各個(gè)節(jié)點(diǎn)。

3)清空set容器以節(jié)省內(nèi)存。

2.4.2 利用邊的連接性生成邊界環(huán)線

基于map中邊的連接性即可形成各條邊界環(huán)線，具體算法步驟為:

1)新增一個(gè)list＜int＞類型的鏈表表示一個(gè)環(huán)線，用于存放一個(gè)環(huán)線上的各個(gè)節(jié)點(diǎn)的編號。

2)從map中取出第一個(gè)元素(即獲得該元素的數(shù)據(jù)字符串，并從map中將該元素刪除)作為當(dāng)前分析邊。

3)從當(dāng)前分析邊的字符串中取得各個(gè)節(jié)點(diǎn)編號，除最后一個(gè)節(jié)點(diǎn)外，將其余節(jié)點(diǎn)的編號順次加入到環(huán)線鏈表中。不加入最后一個(gè)節(jié)點(diǎn)是為了避免環(huán)線上節(jié)點(diǎn)編號重復(fù)，例如:對于圖1中的邊界“2 7 4”，將邊界存入環(huán)線時(shí)只存放節(jié)點(diǎn)號2、7。

4)當(dāng)前分析邊的最后一個(gè)節(jié)點(diǎn)的編號指出了與之相連的下一個(gè)邊的起始節(jié)點(diǎn)，因此以其作為鍵值在map中查找相連邊:①如果在map中找到了與當(dāng)前分析邊相連的下一邊，則將該邊從map中取出(即獲得該元素的數(shù)據(jù)字符串，并從map中將該元素刪除)作為新的分析邊，回到步驟3);②如果在map中找不到相連的邊，則表明環(huán)線已閉合，保存當(dāng)前邊界環(huán)線。

5)查看map中是否還有未分析邊:①如果map非空，則表明邊界環(huán)線還沒有分析完畢，回到步驟1);②如果map已空，則表明邊界環(huán)線已經(jīng)分析完畢，結(jié)束邊界環(huán)線的分析。

上述算法中，從map中逐步取出邊的措施及時(shí)刪除了已經(jīng)分析過的邊，使map中元素個(gè)數(shù)遞減，此策略有助于提高map中元素的查找效率。

3 算法示例

用ABAQUS有限元軟件建立一個(gè)含兩個(gè)孔洞的平面區(qū)域，采用三角形單元進(jìn)行網(wǎng)格劃分后得到如圖2的有限元網(wǎng)格，寫入inp文件。

圖2 ABAQUS劃分的平面有限元網(wǎng)格Fig.2 Finite element mesh in ABAQUS

ABAQUS的inp文件是關(guān)于有限元模型的文本文件，文獻(xiàn)［7-8］對其具體信息進(jìn)行了介紹。筆者編寫了從inp文件讀取到網(wǎng)格數(shù)據(jù)并分析邊界的程序，找出了網(wǎng)格邊界并連成了環(huán)線，其結(jié)果如下:

與圖2對比可見，成功地獲得了圖中網(wǎng)格的3條邊界，驗(yàn)證了前述算法的正確性。

4 結(jié)語

本文方法利用了set和map容器能夠快速查找數(shù)據(jù)的特點(diǎn)，能達(dá)到快速、高效地從網(wǎng)格中找出邊界并將邊界連成環(huán)線。程序量小、簡單、適用，解決了基于平面有限元網(wǎng)格快速分析模型邊界的問題。

［1］ 崔振山，劉國燕，劉才.多連通任意截面桿件扭轉(zhuǎn)問題的有限元法［J］.燕山大學(xué)學(xué)報(bào)，2001，25(4):297-300.

Chui Zhenshan，Liu Guoyan，Liu Cai.Finite element method for torsional bar with arbitrary shaped and multiple-connected crosssections［J］.Journal of Yanshan University，2001，25(4):297-300.

［2］ 葉至軍.C++STL開發(fā)技術(shù)導(dǎo)引［M］.北京:人民郵電出版社，2007.

［3］ 殷際英.STL技術(shù)在邊界元離散化過程中的運(yùn)用［J］.北方工業(yè)大學(xué)學(xué)報(bào)，2001(1):64-67.

Yin Jiying.Application of STL technique to discretion by boundary element method［J］.Journal of North China University of Technology，2001(1):64-67.

［4］ 李余江，殷際英，賴錫煌，STL技術(shù)在面向?qū)ο笥邢拊绦蛑械膽?yīng)用［J］.應(yīng)用力學(xué)學(xué)報(bào)，2005，22(1):146-149，170.

Li Yujiang，Yin Jiying，Lai Xihuang.STL C++in finite element programming with applications［J］.Chinese Journal of Applied Mechanics，2005，22(1):146-149，170.

［5］ 唐麗玉，朱泉鋒，石松.基于STL的Delaunay TIN構(gòu)建的研究與實(shí)現(xiàn)［J］.遙感技術(shù)與應(yīng)用，2005(3):40-43.

Tang Liyu，Zhu Quanfeng，Shi Song.Research and implementation of constructing delaunay TIN based on STL［J］.Remote Sensing Technology and Application，2005(3):40-43.

［6］ 吳小平，許天會(huì)，趙文光.高效構(gòu)建Delaunay三角網(wǎng)算法研究及應(yīng)用解決方案［J］.水電能源科學(xué)，2009(1):96-98，108.

Wu Xiaoping，Xu Tianhui，Zhao Wenguang.Research on effective construction of delaunay TIN algorithm and its solution［J］.Water Resources and Power，2009(1):96-98，108.

［7］ 莊茁.基于ABAQUS的有限元分析和應(yīng)用［M］.北京:清華大學(xué)出版社，2009.

［8］ 劉展.ABAQUS6.6基礎(chǔ)教程與實(shí)例詳解［M］.北京:水利水電出版社，2008.