基于STL快速重構平面有限元網格邊界

王家林，張德立，何 琳

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

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

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

1 C++STL中基本容器的特點

C++標準模板庫STL是C++的組成部分，提供了大量的可復用軟件組件，包含了vector、list、set、map等容器及算法，其實現速度和內存利用方面都是高效的［2］。充分利用STL技術能夠極大地提高應用程序的開發效率，殷際英［3］將STL技術用于邊界元程序設計中，解決大量數據的動態存儲和內存分配問題;李余江，等［4］運用STL技術以向量模板類的特化繼承對象為變容量數據容器編制了面向對象的有限元程序;唐麗玉，等［5］和吳小平，等［6］將 STL 技術用于Delaunay三角形網格的高效構建。

vector是一種連續存放、可根據序號隨機訪問數據元素的容器，在所有容器中具有最高的元素訪問效率。不過在插入和刪除元素時會產生內存塊的拷貝，當內存空間不夠時，需要重新申請一塊足夠大的內存并進行內存的拷貝，導致執行時間增加。

list是STL提供的雙向鏈表，它的數據元素在內存空間不必連續存放，插入和刪除數據元素的效率高。list數據結構只具有順序訪問數據元素的能力，不能通過序號直接訪問一個指定的數據元素。

set容器使用一種稱為紅黑樹的平衡二叉檢索樹結構來組織泛化的元素數據，其每個節點包含一個取值紅色或黑色的顏色域來進行樹的平衡處理，不會將重復的鍵值插入容器，也不需要指定具體的插入位置，而按元素在樹中的關聯關系，進行位置檢索和插入，元素的刪除亦然。元素數據的檢索，使用的是二叉檢索樹的中序遍歷算法，檢索的效率高于vector、deque 和 list等容器。

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

2 網格邊界的分析方法

2.1 單元節點編號的存儲方式

對于一個確定的有限元網格，單元個數及每類單元的節點個數是已知的，因此為了提高數據訪問效率，對于每個單元采用了vector＜int＞數據類型存儲各節點編號。

2.2 邊界的判別方法

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

圖1 平面有限元網格示例Fig.1 Plane finite element mesh

2.3 利用set容器分析邊界

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

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

2)對于單元的每一個邊，按單元順時針方向將邊上的節點編號組成字符串，用該字符串在set中查找有無該字符串:①如果在set中找到該字符串，說明此字符串表示的邊為第2次出現，不是模型邊界，則從set中將該字符串刪除;②如果在set中找不到該字符串，表明此字符串表示的邊為第1次出現，可能是模型邊界，則將該邊上的節點的編號按單元逆時針方向組成字符串后加入set中。

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

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

2.4 利用map容器分析邊界環線

盡管set容器中的字符串標記了模型的邊界，但各個邊處于散亂狀態，沒有連接成邊界環線，扭轉分析需要能識別出每一個邊界環線。在圖1中，處于單元1的邊界(2 7 4)和處于單元2中的邊界(4 9 3)是相連接的。可見兩條相連的邊界，其中一條的末尾節點號正好是另一條的首節點號。基于此特點，即可建立形成邊界環線的算法。

2.4.1 生成邊界map

從前述set中取出各邊界邊組成的字符串，以首節點號為關鍵字、字符串為數據形成map，具體算法步驟為:

1)建立一個以整數為鍵值，數據為字符串的map。

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

對set中每個元素執行完畢后，map中每個元素的鍵值表示了一個邊的起始節點，其數據字符串表明了該邊上的各個節點。

3)清空set容器以節省內存。

2.4.2 利用邊的連接性生成邊界環線

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

1)新增一個list＜int＞類型的鏈表表示一個環線，用于存放一個環線上的各個節點的編號。

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

3)從當前分析邊的字符串中取得各個節點編號，除最后一個節點外，將其余節點的編號順次加入到環線鏈表中。不加入最后一個節點是為了避免環線上節點編號重復，例如:對于圖1中的邊界“2 7 4”，將邊界存入環線時只存放節點號2、7。

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

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

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

3 算法示例

用ABAQUS有限元軟件建立一個含兩個孔洞的平面區域，采用三角形單元進行網格劃分后得到如圖2的有限元網格，寫入inp文件。

圖2 ABAQUS劃分的平面有限元網格Fig.2 Finite element mesh in ABAQUS

ABAQUS的inp文件是關于有限元模型的文本文件，文獻［7-8］對其具體信息進行了介紹。筆者編寫了從inp文件讀取到網格數據并分析邊界的程序，找出了網格邊界并連成了環線，其結果如下:

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

4 結語

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

［1］ 崔振山，劉國燕，劉才.多連通任意截面桿件扭轉問題的有限元法［J］.燕山大學學報，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開發技術導引［M］.北京:人民郵電出版社，2007.

［3］ 殷際英.STL技術在邊界元離散化過程中的運用［J］.北方工業大學學報，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技術在面向對象有限元程序中的應用［J］.應用力學學報，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構建的研究與實現［J］.遙感技術與應用，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］ 吳小平，許天會，趙文光.高效構建Delaunay三角網算法研究及應用解決方案［J］.水電能源科學，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的有限元分析和應用［M］.北京:清華大學出版社，2009.

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