曲面生成和交叉处理

Question

如题所述

Answer 1

一、曲面生成

空间曲面存储在一个曲面文件中，该文件的结构如表4-10所示。一个空间曲面由多个曲面片组合而成，所以生成空间曲面之前首先要生成空间曲面片。空间曲面片由两闭合曲线或两条非闭合曲线连接而成。生成实体表面的方法有很多，如遗传算法、模拟退火法和插值算法等。其中遗传算法和模拟退火法基于图论的原理来完成曲面生成任务。本系统中采用了遗传算法来生成曲面片，曲面和曲面片用非规则三角网TIN(triangle irregurlar network）来表示。

表4-10 曲面文件

续表

1.遗传算法的基本原理

遗传算法（genetic algorithm）简称GA，它是建立在自然选择和群体遗传学机理基础上的随机迭代和进化，是具有广泛适用性的搜索方法。在遗传算法中，所有的自然种类适应环境而得以生存，这一自然适应性是GA的主旋律。GA搜索结合了达尔文适者生存和随机信息交换，前者消除了各种不适应因素，后者利用了原有解中已有的认识，从而加快了搜索过程。下面说明基本方法。

对于一个给定的优化问题，设定目标函数：

F=f(x,y,z）,（x,y,z）∈Ω，F∈R

求空间点（x₀,y₀,z₀）使得（不失一般性，假设求最大值）

F=f(x₀,y₀,z₀)=maxf(x,y,z）

其中（x,y,z）为自变量，Ω是（x,y,z）的定义域，x,y,z可以是数值，也可以是符号，F为实数，是解的优劣程度或适应度的一种度量，f为解空间点（x,y,z）∈Ω到实数域F ∈ R的一种映射，那么GA的求解步骤如下：

（1）编码

用一定比特数的0,1二进制编码对自变量x,y,z进行编码形成基因码链，每一码链代表一个个体，表示优化问题的一个解，如x有16种可能取值x₀,x₁,x₂，…，x₁₅，则可用4bit的二进制编码0000-1111来表示，将x,y,z的基因码组合在一起则形成码链。

（2）产生群体

t=0，随机产生n个个体组合成一个群体P(t），该群体代表优化问题的一些可能解的集合，当然，一般来说，它们的素质都很差。GA的任务是要从这些群体出发，模拟进化过程，择优汰劣，最后得出非常优秀的群体和个体，满足优化的要求。

（3）评价

按编码的规则，将群体P(t）中的每一个体的基因码所对应的自变量（x_i,y_i,z_i）代入（1）式，算出其函数值F_i,i=0,1,2，…，N_oF_i越大，表示该个体有较高的适应度，更适应于f所定义的生存环境，适应度Fi为群体进化时的选择提供了依据。

（4）选择（复制）

按一定概率从群体P(t）中选取M对个体，作为双亲用于繁殖后代，产生新的个体加入下一代群体P(t+1）中。一般P_i与F_i成正比，就是说，适合于生存环境的优良个体将有更多的繁殖后代的机会，从而使优良特性得以遗传。选择是遗传算法的关键，它体现了自然界中适者生存的思想。

（5）交叉

对于选中的用于繁殖的每一对个体，随即选择同一整数n，将双亲的基因码链在此位置相互交换。如个体X,Y在位置3经交叉产生新个体X´，Y´，它们组合了父辈个体X,Y的特征，即

X=X₁X₂X₃X₄X₅[00011]

Y=Y₁Y₂Y₃Y₄Y₅[11100]

X´＝X₁X₂X₃X₄X₅[00000]

Y´＝Y₁Y₂Y₃Y₄Y₅[11111]

交叉体现了自然界中信息交换的思想。

（6）变异

以一定概率P_m从群体P(t+1）中随机选取若干个体，对于选中的个体，随机选取某一位进行反运算，即由1->0由0->1。同自然界一样，每一位发生变异的概率是很小的，变异模拟了生物进化过程中的偶然基因突变现象。GA的搜索能力主要是由选择和交叉赋予的，变异算子则保证了算法能搜索到问题解空间的每一点，从而使算法具有全局最优，它进一步增强了GA的能力。

（7）迭代

对于交叉和变异产生的新一代群体进行重新评价和选择，然后再进行交叉和变异操作，如此循环往复。当群体中最优个体的适应度和平均适应度值不再提高，或迭代次数达到预设次数时，迭代过程结束。

2.生成曲面片的遗传算法

曲面片生成算法描述如下：

step1：初始化点列P₁和P₂，初始化交叉概率P_c，初始化变异概率P_m，初始化迭代计数器count为0。

step2：在P₁,P₂之间随机产生N个三角划分，其中每个三角划分称为一个串，这些串构成了第一代群体。

step3：对群体中的串随机地配对并按概率P_c进行交叉，将得到的新串添加到群体中。

step4：对群体中的串按概率P_m进行变异，将得到的新串添加到群体中。

step5：用选择算子筛选保留串形成下一代群体。

step6：修改迭代计数值，令count=count+1，如果迭代次数达到预设次数，转step7，否则转step3。

step7：返回群体中的最优串，结束。

3.倒转地层建模

使用前面的曲面生成算法，可以对如图4-4所示的倒转地层面进行建模，图4-5是通过这种方法进行建模得到的结果。

图4-4 倒转地层

图4-5 倒转地层建模

二、曲面交叉处理

在矿体出现分叉的情况下，需要把一个剖面上的一条轮廓线与另一个剖面上的多条轮廓线相连接。在本系统中，用以下方式来处理这种情况：首先用剖面1上的一条轮廓线分别与剖面2上的多条轮廓线分别相连得到多个连接曲面，取其中第一个曲面作为目标曲面；然后依次取其他曲面与目标曲面进行交叉处理，每次交叉处理的结果作为下一次交叉处理的目标曲面；最后一次交叉处理所得的曲面即所求实体曲面片。从一条轮廓线出发，分别与另外两条轮廓线相连得到两个空间曲面，对这两个曲面进行交叉处理的算法描述如下：

step1：初始化表示曲面1的三角形数组TA1，初始化表示曲面2的三角形数组TA2，初始化表示曲面1边界的线段数组BLA1，使其长度为0，初始化表示曲面2边界的线段数组BLA2，使其长度为0，初始化表示曲面1和曲面2共同边界的线段数组BLA使其长度为0。

step2：从三角形数组TA1搜索曲面边界线（段），结果存入线段数组BLA1中，从三角形数组TA2搜索曲面边界线（段），结果存入线段数组BLA2中，求BLA1和BLA2的交集，结果存入BLA中，求BLA1与BLA的差集，结果存入BLA1中，求BLA2与BLA的差集，结果存入BLA2中，初始化曲线BLA所在平面的单位法向量N,N从曲线BLA指向曲线BLAl。

step3：初始化循环控制变量I为0。

step4：如果I等于TA1中的三角形的个数，即TA1中的每个三角形都被处理过，转step9，否则从TA1中取（从0开始计数的）第I个三角形T₁。

step5：初始化循环控制变量J为0。

step6：如果J等于TA1中的三角形的个数，即TA2中的每个三角形都被处理过，转step8，否则从TA2中取（从0开始计数的）第J个三角形T₂。

step7：如果三角形T₁和T₂不相交或交线在这两个三角形的边上，令J=J+1，转step6，否则把这两个三角形分别分裂成多个三角形，使得这两个三角形的交线是分裂后的某两个三角形的公共边，从TA1中删除T₁，在T₁原来的位置处插入由T₁分裂后得到的三角形，从TA2中删除T₂，在T₂原来的位置处插入由T₂分裂后得到的三角形，转step4。

step8：令I=I+1，转step4。

step9：计算三角形数组TA1和TA2中三角形的公共边，将它们存入临时线段数组LA中，LA表示曲面I和曲面2的交线。

step10：计算TA1中顶点都不在边界线BLA上或有一个顶点在边界线BLA1的三角形，这些三角形的存储在临时三角形数组TA11中，计算TA2中顶点都不在边界线BLA上或有一个顶点在边界线BLA2的三角形，这些三角形存储在临时三角形数组TA21中。

step11：设置临时三角形数组TA12和TA22，令TA12=TA1-TA11,TA22=TA2-TA21。

step12：改变公共边界线BLA中线段的方向，使其正向相对于平面法向量N为逆时针方向。

step13：从TA12和TA22中提取相交于公共边界BLA上的三角形面片对，选择这对面片中相对于公共边界线BLA正向处于外侧的三角形面片，将TA12中外侧三角形保存在临时三角形数组TA13中，将TA22中外侧三角形保存在临时三角形数组TA23中。令TA12=TA12-TA13,TA22=TA22-TA23。

step14：以交线LA为约束边界，在TA12中搜索与TA13中相邻的三角形，将这些三角形添加到TA13中，在TA22中搜索与TA23中相邻的三角形，将这些三角形添加到TA23中。

s_tep15 返回TA11+TA13+TA21+TA23，结束。

使用如上所述曲面交叉处理算法，可以对如图4-6所示的矿体分叉情况进行建模，图4-7是通过这种方法建模得到的结果。

图4-6 分叉矿体截面图

图4-7 分叉矿体建模