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

（安徽三聯(lián)學(xué)院, 合肥 230601）

1 引 言

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

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

圖2 一個Zachariase模型

2 Zachariase模型算法

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

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

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

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

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

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

為了實(shí)現(xiàn)Zachariasen以三角形為基本單位進(jìn)行環(huán)繞生成鄰居多邊形的算法，本文實(shí)現(xiàn)的算法是以多邊形為基本環(huán)繞單位，在此基礎(chǔ)上形成圖2所示的多邊形網(wǎng)絡(luò)，其基本流程是：

1）初始化.

2）隨機(jī)添加一個安全的多邊形（所謂“安全”，即滿足圖2模型，不出現(xiàn)三角形疊加，并且符合細(xì)胞結(jié)構(gòu)的邊數(shù)和拓?fù)浣Y(jié)構(gòu)要求）.（見圖4（a））

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

4）隨機(jī)選取下一個添加多邊形的位置，繼續(xù)環(huán)繞補(bǔ)足下一個多邊形，轉(zhuǎn)（2）（見圖4（c））直到生成的細(xì)胞數(shù)目滿足要求時，算法終止.

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

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

3 Zachariase模型的程序?qū)崿F(xiàn)

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

case 2: 隨機(jī)sides_random()產(chǎn)生：(環(huán)端距poledis/△ 邊長edgelength+1+2～5)

如果結(jié)果是：

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

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

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

case 3:隨 機(jī) random()產(chǎn) 生 :(poledis/edgelength+1+3～6)

如果結(jié)果是：

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

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

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

case 4：隨機(jī)random()產(chǎn)生：(poledis/edgelength+1+4～7)

如果結(jié)果是:

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

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

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

case 5：隨機(jī)random()產(chǎn)生：(poledis/edgelength+1+5～8)

如果結(jié)果是：

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

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

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

程序中兩個典型的數(shù)據(jù)結(jié)構(gòu)是小三角形的數(shù)據(jù)結(jié)構(gòu)和多邊形的數(shù)據(jù)結(jié)構(gòu).小三角形的數(shù)據(jù)結(jié)構(gòu)：

class triangle

{

屬性:(private)

double x[4];//其中x[0],y[0]為小三角形的中心坐標(biāo)，其余為三個頂點(diǎn)坐標(biāo)

double y[4];

bool edgestate[3];//三邊各自狀態(tài)，是否已經(jīng)配對

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

}triangle[800];

多邊形的數(shù)據(jù)結(jié)構(gòu):

class polygon

{

int sides;//邊數(shù)

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

}polygon[200]

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

圖5 一次失敗的圖形生成

4 仿真結(jié)果

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

圖6 使用本文系統(tǒng)產(chǎn)生的幾個仿真模型

5 結(jié)束語

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

[1]傅廷亮.計算機(jī)模擬技術(shù)[M].合肥:中國科學(xué)技術(shù)大學(xué)出版社, 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]車武軍,楊勛年,汪國昭.動態(tài)骨架算法[J].Journal of Software,2003, 14(4):818-823.

[6]杜永強(qiáng),李清玲.多連通域Voronoi圖是算法及數(shù)據(jù)存儲結(jié)構(gòu)[J].計算機(jī)工程與設(shè)計, 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.