有限元设计软件生成网格的PAVING算法 一、简介 使用有限元软件分析计算几何体的物理性质，其计算的过程可以划分为几个大的模块，输入几何体区域→为该区域生成一个网格→对生成的网格施加一个干扰→从受到干扰的网格开发分析数据→确定几何体的物理行为。分析计算流程图如图1所示。 图1 有限元分析的模块 在有限元分析的前处理模块中，网格生成时很重要的一个步骤。生成网格的质量会影响后处理计算结果的精度。当前，行业内流行多种网格生成的算法，各有各自的特点，该部分内容在本文国内外研究现状一节中已经详细阐述。其中paving算法健壮性良好，计算速度快，而且生成的网格质量好。本节主要阐述采用C++语言实现paving算法的实现过程。如图2所示，采用paving算法生成网格的算法流程图，从输入边界数据到最后输出划分好的网格，其中主要有生成新行，平滑处理，缝合处理，边界相交处理等几个子模块。
图2 Flow chart of paving algorithm 为了清晰理解上述paving算法的流程，以图3所示为例，图a当中为输入的原始外边界数 据，围成待划分网格的区域。选择边界上的一行节点为基础，添加生成一行新的浮动节点， 生成顺序为沿着外边界按逆时针方向进行。对新生成的浮动节点进行平滑处理， 使节点围成的单元的internal angle以及aspect ratio变得更为合理，单元更趋近于规则四边形。对剩余的待划分网格区域进行缝合，检查单元是否相交，对相交的单元进行处理，对单元进行调整，直到整个区域生成高质量的网格为止。 图3 paving算法铺筑单元示意图 依据图2所示流程图，生成相应的伪代码： Do Row choise While add row is not complete Add row portion Smooth row portion Seam boundary If intersection occurs then Connect overlaps Seam boundary End if Row adjustment
广州有道资料网https://www.doczj.com/doc/cf11738166.html, ANSYS中简化模型和划分网格的方法 本文介绍了ANSYS中简化模型和划分网格的相关方法。 使在建立仿真模型时，经验是非常有助于用户决定哪些部件应该考虑因而必须建立在模型中，哪些部件不应该考虑因而不需建立到模型中，这就是所谓的模型简化。此外，网格划分也是影响分析精度的另外一个因素。本文将集中讨论如何简化模型以获得有效的仿真模型以及网格划分需要注意的一些问题。 理想情况下，用户都希望建立尽可能详细的仿真模型，而让仿真软件自己来决定哪些是主要的物理现象。然而，由于有限的计算机资源或算法限制，用户应该简化电磁仿真的模型。 模型简化 模型简化主要取决于结果参数及结构的电尺寸。例如，如果用户希望分析安装在某电大尺寸载体上的天线的远场方向图，那么模型上距离源区超过一个波长的一些小特征和孔径(最大尺度小于/50)就可以不考虑。另一方面，如果用户希望分析从源到用带有小孔的屏蔽面屏蔽的导线之间的耦合，那么必须对小孔、靠近源的屏蔽面以及导线进行精确建模。另外一个常用的简化是用无限薄的面来模拟有限厚度的导体面。一般而言，厚度小于/100的金属面都可以近似为无限薄的金属面。有限导电性和有限厚度的影响可以在SK卡中设置。对于比较厚的导体面，如果这种影响是次要的，那么用户仍然可以采取这种近似。例如，当建立大反射面天线的馈源喇叭模型时，喇叭壁的有限厚度对于反射面天线主波束的影响就是次要的。然而，如果喇叭天线用于校准标准时，那么喇叭壁的有限厚度就不能忽略。 网格划分 一般而言，网格划分的密度设置为最短波长的十分之一。然而，在电流或电荷梯度变化剧烈的区域，如源所在区域、曲面上的缝隙和曲面的棱边等，必须划分得更密。一个实用的指导原则是网格大小应该与结构间的间隔距离(d)相比拟(%26lt;=2d)。同样地，如果需要计算近场分布，那么网格大小应该同场点到源点间距离(d)相比拟。 总之，用户建立的几何模型应该抓住主要的物理现象，而网格划分则需要权衡输出结果相对于网格大小的收敛性。 广州有道资料网https://www.doczj.com/doc/cf11738166.html,
基于变分网格的曲面简化高效算法? 金勇, 吴庆标+, 刘利刚 (浙江大学数学系,浙江杭州 310027) An Efficient Method for Surface Simplification Based On Variational Shape Approximation* JIN Yong, WU Qing-biao+, LIU Li-gang (Department of Mathematics, Zhejiang University, Hangzhou 310027, China) + Corresponding author: E-mail:qbwu@https://www.doczj.com/doc/cf11738166.html, Abstract:Providing fast and accurate simplification method for large polygon mesh is one of the most important research focuses in computer graphics. Approximating mesh model with a few polygons can improve the rendering speed, and reduce the storage of the model. The paper presents a local greedy algorithm to minimize the energy defined by variational shape approximation. The algorithm simplifies the mesh by controlling the number of the target polygons, while attempting to get ideal effect by adaptive seed triangles selection. The algorithm has intuitive geometric meaning. The method is efficient enough to be efficiently adopted in the geometric modeling system. Key words: Polygon mesh simplification; variational shape approximation; greedy algorithm; geometric modeling 摘要: 为大型的多边形网格模型提供快速、准确的简化算法是计算机图形学中的一个重要的研究方面.以较少的多边形逼近表示网格模型,能够提高模型的绘制速度,减小模型的存储空间.本文根据变分网格逼近表示所定义的全局误差能量,提出一种局部贪心优化算法,该算法通过控制目标网格分片数来简化网格,通过种子的自适应选取以达到理想的简化效果,具有直观的几何意义.本文方法计算量少,效率较高,能够有效应用于几何造型系统中. 关键词:多边形网格简化;变分网格逼近;贪心算法;几何造型 中图法分类号: TP391文献标识码: A 1 引言 三维多边形网格模型,包括三角形网格、四边形网格等,在计算机辅助几何设计、计算机动画、虚拟现实、计算机游戏和医学影像等领域有着大量的应用.随着三维扫描技术的发展,顶点数为数万的模型已经非常常见, ?Supported by the National Natural Science Foundation of China under Grant No.10871178, 60776799 (国家自然科学基金); Technology Department of Zhejiang Province Grant No. 2008C01048-3(浙江省重大科技创新项目) 作者简介: 金勇(1985－),男,上海人,博士研究生,主要研究领域为数字几何处理和计算机辅助几何设计;吴庆标(1963－),男, 浙江台州人,博士,教授,博士生导师,主要研究领域为图形与图像处理,数值计算方法,高性能并行计算和计算机模拟; 刘利刚(1975－),男,江西吉安人,博士,副教授,博士生导师,主要研究领域为数字几何处理,计算机辅助几何设计,计算机图形学和图像处理.
I 目录 1 概述 (1) 2 结构网格 (3) 2.1 贴体坐标法 (3) 2.2 块结构化网格 (11) 3 非结构网格 (16) 3.1 概述 (16) 3.2 阵面推进法 (16) 3.3 Delaunay三角划分 (19) 3.4 四叉树（2D）/八叉树（3D）方法 (21) 3.5 阵面推进法和Delaunay三角划分结合算法 (22) 4 其他网格生成技术 (23) 4.1 自适应网格 (23) 4.2 混合网格 (25) 4.3 动网格 (26) 4.4 曲面网格 (27) 4.5 重叠网格 (28) 5 网格生成软件 (29) 5.3 Gambit (29) 5.2 ICEM CFD (30) 5.1 TrueGrid (32) 5.2 Gridgen (34)
1 概述 计算流体力学作为计算机科学、流体力学、偏微分方程数学理论、计算几何、数值分析等学科的交叉融合，它的发展除依赖于这些学科的发展外，更直接表现于对网格生成技术、数值计算方法发展的依赖。 在计算流体力学中，按照一定规律分布于流场中的离散点的集合叫网格（Grid），分布这些网格节点的过程叫网格生成（Grid Generation）。网格生成是连接几何模型和数值算法的纽带，几何模型只有被划分成一定标准的网格才能对其进行数值求解，所以网格生成对CFD至关重要，直接关系到CFD计算问题的成败。一般而言，网格划分越密，得到的结果就越精确，但耗时也越多。1974年Thompson等提出采用求解椭圆型方程方法生成贴体网格，在网格生成技术的发展中起到了先河作用。随后Steger等又提出采用求解双曲型方程方法生成贴体网格。但直到20世纪80年代中期，相比于计算格式和方法的飞跃发展，网格生成技术未能与之保持同步。从这个时期开始，各国计算流体和工业界都十分重视网格生成技术的研究。上个世纪90年代以来迅速发展的非结构网格和自适应笛卡尔网格等方法，使复杂外形的网格生成技术呈现出了更加繁荣发展的局面。现在网格生成技术已经发展成为CFD的一个重要分支，它也是计算流体动力学近20年来一个取得较大进展的领域。也正是网格生成技术的迅速发展，才实现了流场解的高质量，使工业界能够将CFD的研究成果——求解Euler/NS方程方法应用于型号设计中。 随着CFD在实际工程设计中的深入应用，所面临的几何外形和流场变得越来越复杂，网格生成作为整个计算分析过程中的首要部分，也变得越来越困难，它所需的人力时间已达到一个计算任务全部人力时间的60%左右。在网格生成这一“瓶颈”没有消除之前，快速地对新外形进行流体力学分析，和对新模型的实验结果进行比较分析还无法实现。尽管现在已有一些比较先进的网格生成软件，如ICEM CFD、Gridgen、Gambit等，但是对一个复杂的新外形要生成一套比较合适的网格，需要的时间还是比较长，而对于设计新外形的工程人员来说，一两天是他们可以接受的对新外形进行一次分析的最大周期。要将CFD从专业的研究团体中脱离出来，并且能让工程设计人员应用到实际的设计中去，就必须首先解决网格生成的自动化和即时性问题，R.Consner等人在他们的一篇文章中，详细地讨论了这些方面的问题，并提出：CFD研究人员的关键问题是“你能把整个设计周期缩短多少天？”。而缩短设计周期的主要途径就是缩短网格生成时间和流场计算时间。因此，生成复杂外形网格的
算法设计与分析课程设计报告 学院计算机科学与技术 专业计算机科学与技术 年级2011 姓名XXX 学号 2013年5 月19 日
题目：最小生成树问题的算法实现及复杂度分析 摘要：该程序操作简单，具有一定的应用性。数据结构是计算机科学的算法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计算机学科的核心课程。而最小生成树算法是算法设计与分析中的重要算法，最小生成树也是最短路径算法。最短路径的问题在现实生活中应用非常广泛，如邮递员送信、公路造价等问题。本设计以Visual Studio 2010作为开发平台，C/C++语言作为编程语言，以邻接矩阵作为存储结构，编程实现了最小生成树算法。构造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了PRIM 经典算法的算法思想，最后用这种经典算法实现了最小生成树的生成。 引言：假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n（n-1）/2条线路，那么如何在这些可能的线路中选择n-1 条使总的代价最小呢？可以用连通网来表示n 个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树，也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。一棵生成树的代价就是树上各边的代价之和。而实现这个运算的经典算法就是普利姆算法。
基于映射法的六面体网格生成算法 王东风,翟建军,陈文亮 (南京航空航天大学机电学院,江苏南京 210016) 摘要:六面体网格划分技术是三维有限元仿真软件处理的关键环节之一,等参映射法既可适应特殊的区域边界形状,又可控制所生成单元的形状和密度。对基于等参映射法的六面体网格划分原理进行了深入研究,并在此研究基础上对等参映射法的计算过程进行了细致的分析,利用VC++开发了该算法的相应程序,最后给出了2个等参映射法具体的应用实例,计算结果表明该程序的计算精度已经达到了工程要求。 关键词:等参映射法;六面体网格;有限元 中图分类号:TP391 文献标识码:A 文章编号:1672-1616(2009)05-0025-03 在有限元仿真过程中,单元类型的选择对整个有限元仿真的计算效率、自动化程度、计算精度都将产生重要影响。六面体单元由于变形特性好、计算精度高等优点在三维有限元仿真领域中得到了广泛应用[1]。 映射法是三维网格划分中最早使用的方法,和扫略法、基于栅格法等其他方法相比,该方法生成网格速度快、生成的网格单元质量好、网格密度可控制[2～4]。映射法对复杂实体生成三维有限元网格有两大难点,一是子区域划分问题,二是子区域之间网格相容性问题。Price与Armstrong等提出中面法,将三维复杂区域分解成可映射子区域[5～7],但是该算法存在一些问题,特别是几何适应能力问题。李华和程耿东提出了三维组合式模板,一定条件下解决了子区域之间的网格相容性问题[2]。还有学者提出了Embedded Voronoi Graph[8]和BLOBs[9],对复杂实体利用映射法划分六面体网格。映射法在众多有限元分析软件中占有重要地位,美国Altair公司Hyper-Mesh软件中的Solid Mesh Panel就是利用映射法生成六面体网格。 本文对基于等参映射法的六面体网格划分技术进行了详细研究。通过形函数映射技术将物理域映射到参数空间域,对规则参数域进行网格剖分,将参数域的网格反向映射回物理空间,从而得到物理空间六面体网格。利用VC++实现了映射过程,在输入边界信息和划分信息后,即得到了六面体网格的节点信息和单元信息。 1 映射法生成四边形网格和六面体网格 本文主要讨论的是怎样在一个子区域中划分 六面体网格。这里的子区域指的是具有6个面12条边,每条边的特征点已知的区域。 求子区域六面体网格节点的步骤:(1)利用积累弦长参数化法对每条边进行参数化。(2)利用拉格朗日插值公式求边界函数。(3)利用边界函数,由双线性混合孔斯曲面片公式求曲面节点坐标。 (4)由孔斯线性混合插值公式求子区域节点坐标。 在计算的过程中要用到2种坐标系,即笛卡尔坐标系和自然坐标系。笛卡尔坐标系用x,y,z表示,自然坐标系用一组不超过1的无量纲参数r,s, t表示,边界点分别对应自然坐标等于1或0的点。如图1所示。 图1 自然坐标和笛卡尔坐标之间的变换 收稿日期:2008-08-08 作者简介:王东风(1979-),男,河南商丘人,南京航空航天大学硕士研究生,主要研究方向为CAD/CAM/CAE。
最小生成树算法分析 一、生成树的概念 若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次bfs或dfs后便可以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs或bfs亦可系统地访问所有顶点。在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图称为原图的生成树。 对于不连通的无向图和不是强连通的有向图，若有根或者从根外的任意顶点出发，调用一次bfs或dfs后一般不能系统地访问所有顶点，而只能得到以出发点为根的连通分支（或强连通分支）的生成树。要访问其它顶点需要从没有访问过的顶点中找一个顶点作为起始点，再次调用bfs 或dfs，这样得到的是生成森林。 由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。 可以证明：具有n个顶点的带权连通图，其对应的生成树有n-1条边。 二、求图的最小生成树算法 严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成一个子图G’，即G’=（V， E’），且边集E’能将图中所有顶点连通又不形成回路，则称子图G’是图G的一棵生成树。 对于加权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的最小生成树。 求图的最小生成树具有很高的实际应用价值，比如下面的这个例题。
例1、城市公交网 [问题描述] 有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。 [输入] n（城市数，1<=n<=100） e（边数） 以下e行，每行3个数i,j,w ij，表示在城市i,j之间修建高速公路的造价。 [输出] n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。 [举例] 下面的图（A）表示一个5个城市的地图，图（B）、（C）是对图（A）分别进行深度优先遍历和广度优先遍历得到的一棵生成树，其权和分别为20和33，前者比后者好一些，但并不是最小生成树，最小生成树的权和为19。 [问题分析] 出发点：具有n个顶点的带权连通图，其对应的生成树有n-1条边。那么选哪n-1条边呢？设图G的度为n，G=（V，E），我们介绍两种基于贪心的算法，Prim算法和Kruskal算法。 1、用Prim算法求最小生成树的思想如下： ①设置一个顶点的集合S和一个边的集合TE，S和TE的初始状态均为空集； ②选定图中的一个顶点K，从K开始生成最小生成树，将K加入到集合S； ③重复下列操作，直到选取了n-1条边： 选取一条权值最小的边（X，Y），其中X∈S，not (Y∈S)； 将顶点Y加入集合S，边（X，Y）加入集合TE； ④得到最小生成树T =（S，TE）
自动网格生成法 二维网格生成—Advancing Front方法 从概念上来讲，Advancing front方法是最简洁的方法之一。单位元素生成算法始于一个特殊边界条件所定义的“front”,此算法逐级地生成各个元素，同时“front”元素离散地前进，直至整个区域都被元素所覆盖。 网格生成过程包括三个主要步骤： 1、在边界上生成节点，形成一个离散的区域边界。 2、在离散区域边界内生成元素（亦或节点）。 3、强化节点形状以提高网格图形清晰度。 在介绍这个方法之前我们先介绍以下有关于二维空间地几何表示。 一、二维网格的几何特征 我们利用网格参数（一般是空间的函数）来表征网格的一些性质，诸如节点尺寸，节点形状和节点方向等等。网格参数包括两个相互正交的单位矢量a1和a2表示的方向参数，和由两个相互正交代表节点形状的矢量的模值h1和h2。前者表征网格节点伸展的方向，注意的是，只有在生成的是非各向同性的网格内，方向参数才有定义，否则方向矢量是常单位矢量，而尺寸参数有h1=h2，这样就定义了各向同性的平凡网格。 二、区域的几何表示 边界曲线的表示： 我们一般用组合参数样条线表示曲线边界单位，利用参数t，我们利用二维矢量函数表达出曲线边界： r t=x t,y t,0≤t≤1 一般来讲，一条组合样条曲线至少是C1连续的，以保证边界曲线平滑和算法要求的数学连续性。我们下面将要用厄米三阶样条线，当然还有许多就不一一举例了。 样条线的参数表达式如下： X t=H0t,H1t,G0t,G1t?x0,x1,x,t0,x,t1T,0≤t≤1 转置的前两项是曲线的两个端点，而后两项是它们对t求导现在端点处的值。另外G和H分别是四个三阶厄米多项式： H0t=1?3t2+2t3 ; H1t=3t2?2t3 G0t=t?2t2+t3 ; G1t=?t2+t3 此时，参数表达式可以通过一个系数矩阵来描述： X t=1,t,t2,t3M x0,x1,x,t0,x,t1T,0≤t≤1 其中M矩阵读者很容易写出，是一个4*4的方阵，而每一列是这些厄米多项式的系数排列而成。我们把这个表示称之为样本表示。每个边界都包含n个这样的数据点： x i,i=1,2,3,……,n 利用内插法可以构造出如下形式的关系式： X u=H0t x u i?1+H1t x u i+Δi G0t x,t u i?1+Δi G1t x,t u i 其中Δi是单位区间的长度。同时参数t也变为离散的取值是单位区间从原点到任意点所有的个数。如果参数的离散取值正好是i，那么u的表达式将简化为：
#include
{ printf("请输入有边的2个顶点\n"); scanf("%d %d",&n,&m); while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum) { printf("输入的数字不符合要求请重新输入:\n"); scanf("%d%d",&n,&m); } G->arc[n][m].adj = G->arc[m][n].adj = 1; getchar(); printf("请输入%d与%d之间的权值:\n", n, m); scanf("%d",&G->arc[n][m].weight); } printf("邻接矩阵为:\n"); for ( i = 1; i <= G->vexnum; i++) { for ( j = 1; j <= G->vexnum; j++) { printf("%d ",G->arc[i][j].adj); } printf("\n"); } } void sort(edge edges[],MGraph *G)//对权值进行排序{ int i, j; for ( i = 1; i < G->arcnum; i++) { for ( j = i + 1; j <= G->arcnum; j++) { if (edges[i].weight > edges[j].weight) { Swapn(edges, i, j); } } } printf("权排序之后的为:\n"); for (i = 1; i < G->arcnum; i++) {
课程设计报告 课程名称：数据结构课程设计 设计题目：克鲁斯卡尔算法求最小生成树 系别：计算机系 专业：软件技术 学生姓名：陈浩学号:2011304040133 日期: 2013年1月5日-2013年1月11日
目录 1. 需求分析 (2) 1.1 设计题目 (2) 1.2 设计任务及要求 (2) 1.3课程设计思想 (2) 1.4 程序运行流程: (2) 1.5软硬件运行环境及开发工具 (2) 2.概要设计 (2) 2.1流程图 (2) 2.2抽象数据类型MFSet的定义 (3) 2.3主程序 (3) 2.4抽象数据类型图的定义 (4) 2.5抽象数据类型树的定义 (6) 3. 详细设计 (8) 3.1程序 (8) 4.调试与操作说明 (11) 4.1测试结果 (11) 4.2调试分析 (12)
5.课程设计总结与体会 (12) 5.1总结 (12) 5.2体会 (12) 6. 致谢 (13) 7. 参考文献 (13) 1.需求分析 1.1 设计题目：最小生成树 1.2 设计任务及要求：任意创建一个图，利用克鲁斯卡尔算法，求出该图的最小生成树。 1.3 课程设计思想：Kruskal算法采用了最短边策略(设G=(V,E)是一个无向连通网，令T=(U，TE)是G的最小生成树。最短边策略从TE={}开始，每一次贪心选择都是在边集E中选择最短边(u,v)，如果边(u,v)加入集合TE中不产生回路，则将边(u,v)加入边集TE中，并将它在集合E中删去。)，它使生成树以一种任意的方式生长，先让森林中的树木随意生长，每生长一次就将两棵树合并，最后合并成一棵树。 1.4程序运行流程: 1)提示输入顶点数目； 2)接受输入，按照项目要求产生边权值的随机矩阵；然后求解最小生成树； 3)输出最小生成树并且退出； 1.5 软硬件运行环境及开发工具：VC 2.概要设计
关键字：柴油机有限元网格 在计算机交互辅助设计中常常要进行多方案的结构有限元对比分析计算，三维有限元实体网格的划分及修改是一项极为繁琐的工作.目前的有限元软件对复杂柴油机的零部件，如活塞、机体、缸盖等结构的前处理功能有一定局限［1］，本研究以几种典型的柴油机的零部件为例讨论三维有限元网格生成算法，通过采用这些方法可进行三维有限元网格辅助生成修改工作. 1轴对称结构模型的有限元网格自动生成 轴对称结构也是工程设计中常用的零件结构，在柴油机中活塞可视为轴对称结构.图 1 为轴对称结构体有限元三维网格沿着z轴旋转，即可形成轴对称结构体的三维有限元网格。这一三维有限元网格自动生成算法简单、实用，可用于完成大多数轴对称结构有限元网格的自动生成.图 2 为6108 型柴油机活塞的三维网格模型（四分之一模型）.低散热气缸盖的气道口及气门座镶圈等部分也可用这一算法自动生成. 图1轴对称结构体（缸套）三维网格.模型的自动生成
图2活塞的三维网格模型 2特殊形状零件的有限元网格自动生成 由于柴油机零件的形状千差万别，不同形状零件要求采用不同的算法对其生成网格，下面以气缸盖排气道为例，叙述特殊形状零件的网格生成算法.排气道是气缸盖中最复杂的部分之一，低散热气缸盖又增加了陶瓷隔热层和耐热钢衬套，陶瓷的厚度仅0.7～1.5mm,结构更为复杂，无论是手工划分还是计算机生成都较为困难.为了采用计算机辅助生成陶瓷隔热层三维网格，首先需对气道表面进行表面网格划分，形成类似于边界元分析的表面网格，作为三维网格生成的基础，然后再进一步生成三维网格. 2.1计算机辅助三维网格生成算法 由表面网格生成三维网格，要向表面a内侧法向量n方向、距离为L （气道壁厚）处增加一个新表面从而形成三维网格［2，3］.已知平面法矢量n(i,j,k) 和平面上任一点r(x0, y0, z0)，原平面方程为 (x-x0)i+(y-y0)j+(z-z0)k=0, 即n(r-r0)=0.平面沿n方向平移L，平面上一点r(x0, y0 ,z0) 的新坐标为，则新平面方程为： (x-x1)i+(y-y1)j+(z-z1)k=0. 由于新的表面各节点位置已经改变（即新表面位置已知，但四个节点位置未知），问题的关键即转化为求新的节点.为找出新的节点，可将与单元相邻的各单元新表面找出，若相交则可得交线，交线相交得交点，即为所求新表面的节点，见图 3.其中节点的坐标(x,y,z) 可由
一、树及生成树的基本概念 树是无向图的特殊情况，即对于一个N个节点的无向图，其中只有N-1条边，且图中任意两点间有且仅有一条路径，即图中不存在环，这样的图称为树，一般记为T。树定义有以下几种表述： (1)、T连通、无圈、有n个结点，连通有n－1条边；(2)、T无回路，但不相邻的两个结点间联以一边，恰得一个圈；(3)、T连通，但去掉任意一边，T就不连通了（即在点集合相同的图中，树是含边数最少的连通图）；(4)、T的任意两个结点之间恰有一条初等链。 例如：已知有六个城市，它们之间要架设电话线，要求任 意两个城市均可以互相通话，并且电话线的总长度最短。若用 六个点v1…v6代表这六个城市，在任意两个城市之间架设电话 线，即在相应的两个点之间连一条边。这样，六个城市的一个 电话网就作成一个图。任意两个城市之间均可以通话，这个图 必须是连通图，且这个图必须是无圈的。否则，从圈上任意去 掉一条边，剩下的图仍然是六个城市的一个电话网。图5-6是 一个不含圈的连通图，代表了一个电话线网。 生成树（支撑树） 定义：如果图G’是一棵包含G的所有顶点的树，则称G’是G的一个支撑树或生成树。例如,图5-7b是图5-7a的一个支撑树。 定理：一个图G有生成树的条件是G是连通图。 证明:必要性显然； 充分性:设图G是连通的，若G不含圈，则按照定义，G是一个树，从而G是自身的一个生成树。若G含圈，则任取G的一个圈，从该圈中任意去掉一条边，得到图G的一生成子图G1。若G1不含圈，则G1是G的一个生成树。若G1仍然含圈，则任取G1的一个圈，再从圈中任意去掉一条边，得到图G的一生成子图G2。依此类推，可以得到图G的一个生成子 图G K，且不含圈，从而G K是一个生成树。 寻找连通图生成树的方法： 破圈法：从图中任取一个圈，去掉一条边。再对剩下的图 重复以上步骤，直到不含圈时为止，这样就得到一个生成树。 取一个圈(v1,v2,v3,v1)，在一个圈中去掉边e3。在剩下的图 中，再取一个圈（v1,v2,v4,v3,v1），去掉边e4。再从圈（v3,v4,v5,v3） 中去掉边e6。再从圈(v1,v2,v5,v4,v3,v1）中去掉边e7， 这样，剩下的图不含圈，于是得到一个支撑树，如图所示。 避圈法：也称为生长法，从图中某一点开始生长边，逐步扩展成长为一棵树，每步选取与已入树的边不构成圈的那些边。
第一章介绍 ICEM CFD 工程 Tutorials目录中每个工程是一个次级子目录。每个工程的目录下有下列子目录：import, parts, domains, mesh, 和transfer。他们分别代表： ? import/: 要导入到ICEMCFD中的集合模型交换文件，比如igs，STL等； ? parts/: CAD模型 ? domains/: 非结构六面体网格文件(hex.unstruct), 结构六面体网格分区文件(domain.n), 非结构四面体网格文件(cut_domain.1) ? mesh/: 边界条件文件(family_boco, boco)，结构网格的拓扑定义文件(family_topo, topo_mulcad_out), 和Tetin几何文件(tetin1). ? transfer/: 求解器输入文件(star.elem), 用于Mom3d.的分析数据 mesh目录中Tetin文件代表将要划分网格的几何体。包含B-spline曲面定义和曲线信息，以及分组定义 Replay 文件是六面体网格划分的分块的脚本 鼠标和键盘操作
第二章ICEM CFD Mesh Editor界面 The Mesh Editor, 创建修改网格的集成环境，包含三个窗口 ? The ICEM CFD 主窗口 ? 显示窗口 ? The ICEM CFD 消息窗口 主窗口 主窗口中除了图形显示区域，外，还有6个radio按钮：File, Geometry, Meshing, Edit Mesh and Output. The File Menu The File menu 包含 ? Open, Save, Save as, Close, Quit, Project dir, Tetin file, Domain file, B.C file, Import geo, Export geo, Options, Utilities, Scripting, Annotations, Import mesh, DDN part.
实验5 最小生成树算法的设计与实现 一、实验目的 1、根据算法设计需要, 掌握连通图的灵活表示方法； 2、掌握最小生成树算法，如Prim、Kruskal算法； 3、基本掌握贪心算法的一般设计方法； 4、进一步掌握集合的表示与操作算法的应用。 二、实验内容 1、认真阅读算法设计教材和数据结构教材内容, 熟习连通图的不同表示方法和最小生成树算法； 2、设计Kruskal算法实验程序。 有n个城市可以用（n-1）条路将它们连通，求最小总路程的和。 设计测试问题,修改并调试程序, 输出最小生成树的各条边, 直至正确为止。 三、Kruskal算法的原理方法 边权排序: 1 3 1 4 6 2 3 6 4 1 4 5 2 3 5 3 4 5 2 5 6 1 2 6 3 5 6 5 6 6 1. 初始化时：属于最小生成树的顶点U={}
不属于最小生成树的顶点V={1，2，3，4，5，6} 2. 根据边权排序，选出还没有连接并且权最小的边（1 3 1），属于最小生成树 的顶点U={1，3}，不属于最小生成树的顶点V={2,4,5,6}
3. 根据边权排序，选出还没有连接并且权最小的边（4 6 2），属于最小生成树的顶点U={{1，3}，{4，6}}（还没有合在一起，有两颗子树），不属于最小生成树的顶点V={2,5} 4. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，3，4，6}（合在一起），不属于最小生成树的顶点V={2,5}
5. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，2，3，4，6},，不属于最小生成树的顶点V={5} 6. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，2，3，4，5，6}此时，最小生成树已完成
开题报告 信息与计算科学 最小生成树算法及其应用 一、综述本课题国内外研究动态, 说明选题的依据和意义 最小生成树(minimum spanning tree,MST)是计算机学科中一重要内容, 其算法也是重要的计算方法, 是现代科学中比较热门的研究方向. 一个有个结点的连通图的生成树是原图的极小连通子图, 且包含原图中的所有个n n 结点, 并且有保持图联通的最少的边. 许多应用问题都是一个求五项连通图的最小生成树问题. 例如: 要在个城市之间铺设n 光缆, 主要目标是要使这个城市的任意两个之间都可以通信, 但铺设光缆的费用很高, n 且各个城市之间铺设光缆的费用不同; 另一个目标是要使铺设光缆的总费用最低. 这就需要找到带权的最小生成树. MST 性质: 最小生成树性质: 设是一个连通网络, 是顶点集的一个真(,)G V E =U V 子集. 若是中一条“一个端点在中(例如: ), 另一个端点不在中”的边(,)n u v G U u U ∈U (例如:), 且具有最小权值, 则一定存在的一棵最小生成树包括此边v V U ∈-(,)u v G . (,)u v 求MST 的一般算法可描述为: 针对图, 从空树开始, 往集合中逐条选择并G T T 加入条安全边, 最终生成一棵含条边的MST. 1n -(,)u v 1n -当一条边加入时, 必须保证仍是MST 的子集, 我们将这样的边称(,)u v T {}(,)T u v 为的安全边. 其中主要有两种算法: Prim 算法和Kruskal 算法. T Prim 算法: 该算法由Prim 提出, 但事实上Jarnik 于1930年更早提出. 用于求无向图的最小生成树. 设图 . (),G V E =步骤1: 取一个顶点, 则, . 1v {}1V v ={}E =
创作编号： GB8878185555334563BT9125XW 创作者：凤呜大王* kruskal算法及代码 ---含伪代码、c代码、matlab、pascal等代码 K r u s k a l算法每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。K r u s k a l算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。 目录 Kruskal算法 Kruskal算法的代码实现 Kruskal算法 Kruskal算法的代码实现 算法定义 克鲁斯卡尔算法 假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。
举例描述 克鲁斯卡尔算法(Kruskal's algorithm)是两个经典的最小生成树算法的较为简单理解的一个。这里面充分体现了贪心算法的精髓。大致的流程可以用一个图来表示。这里的图的选择借用了Wikipedia上的那个。非常清晰且直观。 首先第一步，我们有一张图，有若干点和边 如下图所示： 第一步我们要做的事情就是将所有的边的长度排序，用排序的结果作为我们选择边的依据。这里再次体现了贪心算法的思想。资源排序，对局部最优的资源进行选择。 排序完成后，我们率先选择了边AD。这样我们的图就变成了 第二步，在剩下的变中寻找。我们找到了CE。这里边的权重也是5
有限元网格自动生成的并行区域划分算法 作者：呙嘉妮胡久乡卢正鼎 摘要：提出了一种基于网格生成递归法的并行区域划分算法，该算法依据网格生成代价的估算分析，采用迭代分解法对区域进行并行划分。在曙光1000A 系统上的运行结果表明，该网格算法的效率和加速比均优于串行递归算法。 关键词：有限元网格；并行区域划分算法；网格生成代价；迭代分解法 基于网络生成递归法［1～3］，本文提出了一种并行区域划分算法，该算法满足以下四个基本原则：a. 任务平衡性原则。能生成平衡的子区域集，即在各子区域中生成网格的时间大致相等。b. 边界最简原则。子区域的边界结构简单，边界处理所需时间短，处理器间消息传递的费用低。c. 网格均匀原则。并行生成的最终网格形状均匀，无奇异单元。d. 区域划分代价最小原则。区域划分算法本身的代价尽可能小。 1、基本思想及相关算法 在网格生成递归法中，如果每个子区域都包含相同的单元数，就比较容易实现任务平衡。因此，首先按照单元数估算待处理区域的网格生成代价，然后根据当前参与并行处理的处理器数N对区域进行分解，并对分解所得子区域进行边界处理，最终获得相互之间既平衡又独立的N个并行子任务。 1.1网格生成代价的估算算法 网格生成代价与分布于待处理区域中的单元数目紧密相关，而单元数目是由该区域的总面积S和区域内单元分布密度决定的。估算公式如下： G=S/Stri，（1） Stri=［L2/(2M2)］sin60°，（2） M=Σ2li/(di1+di2) (i=1，2，…，n)，（3） 式中，G表示三维平面区域(含有n条边) 的网格生成代价；S表示该区域的面积；Stri 是
数据结构与算法 课程设计报告 课程名称：数据结构与算法课程设计 题目：改进的最小生成树算法 专业：计算机科学与技术 班级：（一）班 学号：1362810118，1362810107，1362810108 学生姓名：王洪，汪妍，罗林芳
一、目录 一、问题描述 (1) 二、需求分析 (1) 1. 性能需求 (1) 2. 功能需求 (2) 3. 问题假设 (2) 三、准备知识 (2) 1. 欧拉图定义： (2) 2. 欧拉图相关定理：......................................................................... 错误！未定义书签。 3. 欧拉图应用：................................................................................. 错误！未定义书签。 四、算法和数据结构设计 (5) 1. 算法分析 (5) 2. 建立模型 (5) 1) 前期准备................................................................................. 错误！未定义书签。 2) 确定模型................................................................................. 错误！未定义书签。 3. 具体算法实现................................................................................. 错误！未定义书签。 4. 时间复杂度分 (6) 5.题目拓展 (8) 五、程序测试......................................................................................... 错误！未定义书签。 1. 测试1（测试没有度数为奇数的顶点） (9) 2. 测试2（测试度数为奇数的定点有4个） (9) 六、总结 (11) 1. 已完成部分 (11) 2. 后期设想 (11) 3. 课程设计思考与体会............................................................. 错误！未定义书签。 七、参考文献 (11)