多塊網(wǎng)格連接信息搜索算法-ver14

1、多塊結(jié)構(gòu)網(wǎng)格連接信息搜索算法李新亮中國科學(xué)院力學(xué)研究所， HYPERLINK mailto: 2010年12月第一版；2011年1月2日修改版；數(shù)據(jù)結(jié)構(gòu)說明【目的】根據(jù)坐標文件Mesh3d.dat構(gòu)建出網(wǎng)格連接信息bc_in,其中Mesh3d.dat是多塊結(jié) 構(gòu)網(wǎng)格，PLOT3D格式。【算法簡介】在各塊面網(wǎng)格之間進行搜索匹配，匹配連接?！久Q解釋】塊（Block）：立方體（三維數(shù)組）結(jié)構(gòu)的數(shù)據(jù)點的集合。塊內(nèi)的網(wǎng)格為普通的結(jié)構(gòu) 網(wǎng)格。塊內(nèi)物理量（如坐標）的數(shù)據(jù)格式為：f（i,j,k），i=1,Nx; j=1,Ny; k=1,Nz面（face）:每個塊立方體結(jié)構(gòu)的六個表面。約定1-6號面分別為i=

2、1 ; j=1; k=1; i=Nx; j=Ny 和 k=Nz 面。子面（subface）：面上的矩形區(qū)域，該區(qū)域點的連接對應(yīng)點在同一塊的同一面 連接對應(yīng)點：與該點坐標完全相同的點。【數(shù)據(jù)結(jié)構(gòu)】定義了“點”，“子面”，“面”，“塊”等結(jié)構(gòu)（類），分別具有如下屬性（數(shù)據(jù)成員）：點Point具有如下屬性：坐標x,y,z;連接點的個數(shù)Num_link （如為0表示無連接點）；連接點的塊號 block_link（:）、面號 face_link（:）、下標號 n1_link（:）,n2_link（:）。 由于可 能有多個連接點，這些參數(shù)都是數(shù)組。下標號記錄連接點在面上的相對下標（二維）。 其他標記信息。

3、如是否被搜索過If_search,是否為子面內(nèi)點If_inner,顏色color （染 色時用）。子面Subface具有如下屬性：子面號 subface_no;起始下標ib,jb、終止下標ie,je.即，面上 活 i ie,jb j d + d（1）則說明這兩個面不肯能有公共點，則可排除在搜索范圍之外。2）對于面的內(nèi)點，優(yōu)先搜索已經(jīng)找到的連接面（Ver 1.3采用）例如，m塊nf面的點（i,j）=（2,3）通過搜索，找到了連接點：mt塊nft面的（it,jt）點。 則該面（i+1,j）點的連接點在mt塊nft面上的可能性很大，因此應(yīng)當(dāng)優(yōu)先搜索mt塊的nft 面。如果搜索成功，找到匹配點，則搜索

4、結(jié)束。否則進行普通搜索。注：假設(shè)內(nèi)點和內(nèi)點之間只能有一對連接。不可能出現(xiàn)三個內(nèi)點坐標相同的情況。3）樹狀多級搜索：分割面法（Ver 1.4.1使用）圖3示意圖：將面切割成面元為了實現(xiàn)快速搜索，將面切割成多個面元（注意與前文定義的“子面”區(qū)別開）。采用 前文的方法（公式（1）快速判斷是否存在連接的可能，排除掉不存在連接可能的面元。染色算法描述標記“子面內(nèi)點”和“子面邊界點”do j=2,Ny-1do i=2,Nx-1若該點有不止一個連接點，則標記該點為“子面邊界點；判斷周圍點(i+1,j)，(i-1,j), (i,j+1), (i,j-1)是否與該點有相同的連接塊號、連接面號。如相同，則標記為“

5、子面內(nèi)點”；如不同，則標記為“子面邊界點”。 注：搜索時，如果周圍點有多個連接信息，則均需判斷。無連接點的按照 block_t=0, face_t=0 計算。無連接的點一律標記為內(nèi)點(2010-12-30日Ver 1.2版本修改)。enddoenddo給子面染色染色前，設(shè)定每個內(nèi)點Color =0設(shè)定塊的Color_now=0do j=2,Ny-1do i=2,Nx-1判斷是否“子面內(nèi)點”。如不是，則跳過；判斷是否被染過色(該點的color =0 ?)，如已被染過，則跳過；如a,b條件均滿足，則執(zhí)行如下操作：令該塊的 Color_now=Color_now+1(當(dāng)前色)找出矩形區(qū)域內(nèi)與該點聯(lián)通

6、的內(nèi)點，算法如圖2所示。以(i,j)點為起始點， 向下方(i增加的方向)推進，直到遇到子面邊界點為止，然后整列向右 推進，直到遇到子面邊界點為止。從(i,j)到(i+m,j+n)圍成的矩形區(qū)域內(nèi)的點是聯(lián)通的內(nèi)點，該區(qū)域的點全部染上顏色:Color_now(該點的color設(shè)定為Color_now)。記錄該子面的號(subface_no)為被染的顏色號(color_now);記錄下該子面的起始位置(ibJb)=(i-1,j-1)、終止位置(ieJe)=(i+m+1,j+n+1)記錄下該子面的連接塊、連接面；給該子面各點的至接點染色(使用連接面上的Color_now值)，同時登記 該鏈接子面的信息

7、；即：令該子面連接塊勺Color_now增加1；給該子面連接面編號為(該子面連接塊的Color_now；設(shè)定點P的連接點Pt的Color為Pt所在塊勺Color_now值設(shè)定子面連接面勺邊界(ib,jb) , (ie, je)記錄下子面的連接面編號enddoenddo注：同時給子面與子面的連接面染色(各自用自己的顏色)；從(i,j)點開始，向下及右方染色為止。(先向下推進，再整列向右推進)，直到遇到“子面邊界點” 然后加上外框，就形成了一個子面子塊連接方向的確定:Figure 2: Face-to-face orientations as specified by parameter ori.圖2：染色算法示意圖圖2.4.1相鄰塊之間的對應(yīng)關(guān)系表1 (f, m , n )與(l , m , n )的對應(yīng)關(guān)系111222Ori含義1l=l，m =m，n=n2121122l=m，m = l，n =n2121123l=l，m = m，n =n2121124l=m，m = l，n=n212112步驟：找出子面左上點(ib,jb)在連接子面中的對應(yīng)點(ibt,jbt) 根據(jù)面號，確定子面的l方向，選取該方向的終點(i1,j1)。如下圖所示，如果 Face_no 為 1,3,5,貝01 從(ib,jb)指向(ib,je)點，則(i1,j1)=(ib,je)； 如果 F