多块网格连接信息搜索算法-ver14

1、多块结构网格连接信息搜索算法李新亮中国科学院力学研究所， HYPERLINK mailto: 2010年12月第一版；2011年1月2日修改版；数据结构说明【目的】根据坐标文件Mesh3d.dat构建出网格连接信息bc_in,其中Mesh3d.dat是多块结 构网格，PLOT3D格式。【算法简介】在各块面网格之间进行搜索匹配，匹配连接。【名称解释】块（Block）：立方体（三维数组）结构的数据点的集合。块内的网格为普通的结构 网格。块内物理量（如坐标）的数据格式为：f（i,j,k），i=1,Nx; j=1,Ny; k=1,Nz面（face）:每个块立方体结构的六个表面。约定1-6号面分别为i=

2、1 ; j=1; k=1; i=Nx; j=Ny 和 k=Nz 面。子面（subface）：面上的矩形区域，该区域点的连接对应点在同一块的同一面 连接对应点：与该点坐标完全相同的点。【数据结构】定义了“点”，“子面”，“面”，“块”等结构（类），分别具有如下属性（数据成员）：点Point具有如下属性：坐标x,y,z;连接点的个数Num_link （如为0表示无连接点）；连接点的块号 block_link（:）、面号 face_link（:）、下标号 n1_link（:）,n2_link（:）。 由于可 能有多个连接点，这些参数都是数组。下标号记录连接点在面上的相对下标（二维）。 其他标记信息。

3、如是否被搜索过If_search,是否为子面内点If_inner,颜色color （染 色时用）。子面Subface具有如下属性：子面号 subface_no;起始下标ib,jb、终止下标ie,je.即，面上 活 i ie,jb j d + d（1）则说明这两个面不肯能有公共点，则可排除在搜索范围之外。2）对于面的内点，优先搜索已经找到的连接面（Ver 1.3采用）例如，m块nf面的点（i,j）=（2,3）通过搜索，找到了连接点：mt块nft面的（it,jt）点。 则该面（i+1,j）点的连接点在mt块nft面上的可能性很大，因此应当优先搜索mt块的nft 面。如果搜索成功，找到匹配点，则搜索

4、结束。否则进行普通搜索。注：假设内点和内点之间只能有一对连接。不可能出现三个内点坐标相同的情况。3）树状多级搜索：分割面法（Ver 1.4.1使用）图3示意图：将面切割成面元为了实现快速搜索，将面切割成多个面元（注意与前文定义的“子面”区别开）。采用 前文的方法（公式（1）快速判断是否存在连接的可能，排除掉不存在连接可能的面元。染色算法描述标记“子面内点”和“子面边界点”do j=2,Ny-1do i=2,Nx-1若该点有不止一个连接点，则标记该点为“子面边界点；判断周围点(i+1,j)，(i-1,j), (i,j+1), (i,j-1)是否与该点有相同的连接块号、连接面号。如相同，则标记为“

5、子面内点”；如不同，则标记为“子面边界点”。 注：搜索时，如果周围点有多个连接信息，则均需判断。无连接点的按照 block_t=0, face_t=0 计算。无连接的点一律标记为内点(2010-12-30日Ver 1.2版本修改)。enddoenddo给子面染色染色前，设定每个内点Color =0设定块的Color_now=0do j=2,Ny-1do i=2,Nx-1判断是否“子面内点”。如不是，则跳过；判断是否被染过色(该点的color =0 ?)，如已被染过，则跳过；如a,b条件均满足，则执行如下操作：令该块的 Color_now=Color_now+1(当前色)找出矩形区域内与该点联通

6、的内点，算法如图2所示。以(i,j)点为起始点， 向下方(i增加的方向)推进，直到遇到子面边界点为止，然后整列向右 推进，直到遇到子面边界点为止。从(i,j)到(i+m,j+n)围成的矩形区域内的点是联通的内点，该区域的点全部染上颜色:Color_now(该点的color设定为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；设定点P的连接点Pt的Color为Pt所在块勺Color_now值设定子面连接面勺边界(ib,jb) , (ie, je)记录下子面的连接面编号enddoenddo注：同时给子面与子面的连接面染色(各自用自己的颜色)；从(i,j)点开始，向下及右方染色为止。(先向下推进，再整列向右推进)，直到遇到“子面边界点” 然后加上外框，就形成了一个子面子块连接方向的确定:Figure 2: Face-to-face orientations as specified by parameter ori.图2：染色算法示意图图2.4.1相邻块之间的对应关系表1 (f, m , n )与(l , m , 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)在连接子面中的对应点(ibt,jbt) 根据面号，确定子面的l方向，选取该方向的终点(i1,j1)。如下图所示，如果 Face_no 为 1,3,5,贝01 从(ib,jb)指向(ib,je)点，则(i1,j1)=(ib,je)； 如果 F