一類無序細胞結構模型的研究與實現

左常玲，傅廷亮，郭丁云，孫志峰

（安徽三聯學院, 合肥 230601）

1 引 言

在無序細胞結構類計算機仿真中常常使用Voronoi結構做為初始模型，圖1所示的二維Voronoi圖的定義是: 在平面上隨機地撒下n個點，這n個原始點將是n個多邊形的中心（在仿真時也常稱為細胞核）.選定某一點作為參考點，以該點為起點做與其它n-1個點的連線，再作這n-1根連線的垂直平分線，這些垂直平分線必然相交，只有那些圍繞參考點的垂直平分線圍成所需要的多邊形，即這個多邊形內只有唯一的一個參考點做為中心點.重復以上過程，依次用其它n-1個點形成n-1個多邊形，從而構成一個含有n個多邊形的二維隨機結構模型[1][2].

目前Voronoi結構得到了廣泛應用，例如在自然界中各種各樣的生物細胞結構、各種液體泡沫和化工材料等領域都有應用.Zachariase提出另一類模型做為玻璃材料的模型,該模型與voronoi模型相似，它以小三角形順時針螺旋形圍繞而形成各個多邊形，而由這些多邊形構成了另一類網格模型.圖2是該類模型的一個例子[3-4].

圖2 一個Zachariase模型

2 Zachariase模型算法

從圖2可看出玻璃結構模型與Voronoi多邊形結構相似，不同之處是所有多邊形的邊長都相等，各邊長等于小三角形的邊長.同樣也要分析其面積和邊的分布函數，以及它們之間的相關性，由圖2可見，這些多邊形的邊數大多取4至8條邊中的某個值.普通的Voronoi圖可以用細胞生長法或幾何法等方法生成，并且以離散的點為初始生成元.在這里，我們借鑒Voronoi圖的形成方法，但不是先形成各多邊形的中心點，而是將初始生成元設為大小固定的正三角形，并且使用幾何法生成[5-6].

使用正三角形形成上述模型有一些優點，使得它可以方便地應用于玻璃結構的模擬.1873年，Plateau根據能量最小化原則提出有關肥皂泡幾何形狀Plateau定律，其中，在二維情況下，一個頂點只能有三條邊相交，它們相互間的夾角相等，必為120°.在玻璃模型結構中，Voronoi圖的生成元正好可以從隨機頂點異化為正三角形.只不過，它仍然有一些不等于120°的頂角，而且邊的分布也比較窄.

為了區別于通常Voronoi方法，我們通過一個迭代過程方法生成二維玻璃模型.當然，迭代過程同樣必須保證充分的隨機性，從而達到與平面撒點的幾何法一樣的效果，并獲得算法的簡化和性能的改善.

最初，Zachariasen提出如下的玻璃模型：在平面上放置一系列的等邊三角形，這些三角形頂點互連但不重疊，它們以順時針旋轉的方式圍繞著平面上隨機種子點首尾相接形成一個多邊行環.圖3是小三角形重疊的例子.

圖3 小三角形重疊不能形成可用的模型

之后，Shackelford又提出了一種擴展模型，這種模型給出一個更窄的邊數分布，它允許把直線當做正三角形一樣參與多邊行環的構成.由于篇幅限制，本文不討論這種擴展模型.

為了實現Zachariasen以三角形為基本單位進行環繞生成鄰居多邊形的算法，本文實現的算法是以多邊形為基本環繞單位，在此基礎上形成圖2所示的多邊形網絡，其基本流程是：

1）初始化.

2）隨機添加一個安全的多邊形（所謂“安全”，即滿足圖2模型，不出現三角形疊加，并且符合細胞結構的邊數和拓撲結構要求）.（見圖4（a））

3）以多邊形各邊為基礎，每邊都補上三角形.（見圖4（b））

4）隨機選取下一個添加多邊形的位置，繼續環繞補足下一個多邊形，轉（2）（見圖4（c））直到生成的細胞數目滿足要求時，算法終止.

圖4 形成一個多邊形的示意圖

每一步我們都隨機地在數字4至8中選擇一個數作為多邊行環的邊數.如果邊數小于4，容易導致系統崩潰；邊數大于8，對于建模來說，并不增加太多的額外負擔，但模擬結果就會使得各“細胞”邊數和面積差異變大，不符合Zachariase模型的要求.采用順時針方向作為模型構建的主方向，多邊形的生成，三角形的生成以及整個圖的生成過程都沿順時針方向進行，由此引入向前邊函數檢查和向后邊函數檢查，以確保添加的邊或三角形是安全的.

3 Zachariase模型的程序實現

如果要形成有n條邊的多邊形，按順時針方向形成n-2條邊的未封閉凸環后,還缺少構成封閉凸環的最后兩條邊.由于模型中多邊形邊數只能是4～8邊，在已調用sides_random()函數產生了兩條邊后（本節后面介紹sides_random()函數），則再添加的邊數為以下四種情況之一.

case 2: 隨機sides_random()產生：(環端距poledis/△ 邊長edgelength+1+2～5)

如果結果是：

case 3：檢查poldis=edgelength，是，則連上第3邊；不是，出錯

case 4：別無選擇，只能組成菱形

case 5：關鍵是隨機edge_random()產生第3邊的選擇，第4、5邊別無選擇，只能取中垂線作圖

case 3:隨 機 random()產 生 :(poledis/edgelength+1+3～6)

如果結果是：

case 4：檢查poldis=edgelength，是，則連上第4邊；不是,出錯

case 5：別無選擇，只能取中垂線作圖

case 6：關鍵是隨機edge_random()產生第4邊的選擇，第5、6邊別無選擇，只能取中垂線作圖

case 4：隨機random()產生：(poledis/edgelength+1+4～7)

如果結果是:

case 5：檢查poldis=edgelength，是，則連上第5邊；不是，出錯

case 6：別無選擇，只能取中垂線作圖

case 7：關鍵是隨機edge_random()產生第5邊的選擇，第6、7邊別無選擇，只能取中垂線作圖

case 5：隨機random()產生：(poledis/edgelength+1+5～8)

如果結果是：

case 6：檢查poldis=edgelength,是,則連上第6邊；不是，出錯

case 7：別無選擇，只能取中垂線作圖

case 8：關鍵是隨機edge_random()產生第6邊的選擇，第7、8邊別無選擇，只能取中垂線作圖

程序中兩個典型的數據結構是小三角形的數據結構和多邊形的數據結構.小三角形的數據結構：

class triangle

{

屬性:(private)

double x[4];//其中x[0],y[0]為小三角形的中心坐標，其余為三個頂點坐標

double y[4];

bool edgestate[3];//三邊各自狀態，是否已經配對

int neibour[9];//neibour[0/1/2]表示鄰居多邊形及與構成該多邊形的兩個鄰居小三角形的數組下標,neibour[3/4/5]和neibour[6/7/8]類似于neibour[0/1/2]的描述

}triangle[800];

多邊形的數據結構:

class polygon

{

int sides;//邊數

int neibourtri[8];//(至多8個)鄰居小三角形的數組下標

}polygon[200]

edge_random()函數是一個關鍵的函數，它必須考慮每隨機擴展一條邊(一個小三角形)，都有可能導致后面的順時針弧無法形成凸多邊形.edge_random()函數內的條件限制有：每個三角形有且僅有三個鄰居，構成凸多邊形的相鄰的兩條邊夾角為[60°,180°]，同樣，推廣到任意兩個三角形的鄰邊夾角也為[60°,180°]，小三角形的兩個鄰居三角形的“距離”應該大于edgelength.如圖5所示，最下面兩個三角形距離過近是不允許的（雖然兩個夾角都大于60°，符合角度要求），每次擴展一個凸多邊形時，最后兩條邊總是別無選擇的，只能取中垂線作圖.如果最后兩條邊作完后發現與前幾條規則有沖突的話，則必須往回調整以前隨機產生的邊的夾角.

圖5 一次失敗的圖形生成

4 仿真結果

本文系統的仿真結果見圖6所示，圖中給出四個二維模型圖，由于在圖中對多邊形邊數做了限制，可知這類多邊形網絡的邊數分布二次矩不會太大，也不會太小.（見圖6中的四個圖例）邊數分布二次矩定義如下，其中n是多邊形的邊數，f(n)是圖中多邊形的邊數分布函數.

圖6 使用本文系統產生的幾個仿真模型

5 結束語

二維玻璃模型是無序細胞結構的一類模型，與Voronoi模型相比有其自身的特點.由于玻璃材料結構的無序特點，影響其結構的因素很多，故Zachariase的玻璃結構模型可以作為一種研究方法，它簡化了此類模型的生成，為使用計算機程序仿真這類材料提供了一種新手段.

[1]傅廷亮.計算機模擬技術[M].合肥:中國科學技術大學出版社, 2001:21-32.

[2]Weaire D and Fu T L.The Mechanical Behavior of Foams and 3Emulsions [J].Journal of Rheology , 1988, 32(3):271～283.

[3]Glazier J A, Gross S P and Stavans J.Dynamics of Two-Dimensional Soap Froths [J].Physical Review A, 1987,36:306-312.

[4]Shackelford J F.Triangle Rafts-Extended Zachariase Schematics for Structure Modeling[J].Journal of Noncrystalline Solids,1982, 49:19-28.

[5]車武軍,楊勛年,汪國昭.動態骨架算法[J].Journal of Software,2003, 14(4):818-823.

[6]杜永強,李清玲.多連通域Voronoi圖是算法及數據存儲結構[J].計算機工程與設計, 2006,27(8):1468-1471.

[7]James Alexander Glazier.Dynamics of Cellular Patterns [D].The University of Chicago, Chicago Illinois, 1989:91-98,189-191.