四叉树网格划分研究四叉树网划分研究格划分研究.doc

 硕士学位论文开题报告及论文工作计划书 课题名称 四叉树网格划分研究 学 号 1070105 姓 名 张 专 业 机械工程 学 院 机械工程与自动化学院 导 师 马 副导师 陈 选题时间 年 月 日 东北大学研究生院 年 月 日填表说明 1、本表一、二、三、四、五项在导师指导下如实填写。 2、学生在通过开题后一周内将该材料交到所在学院、研究所。 3、学生入学后第三学期应完成论文开题报告，按有关规定，没有完成开题报告的学生不能申请论文答辩。 一、立论依据 课题来源、选题依据和背景情况、课题研究目的、理论意义和实际应用价值 课题来源 有限元分析(FEA, Finite Element Analysis)，即有限元方法（冯康首次发现时称为基于变分原理的差分方法），是一种用于求解微分方程组或积分方程组数值解的数值技术. 这一解法基于完全消除微分方程, 即将微分方程转化为代数方程组(稳定情形); 或将偏微分方程(组)改写为常微分方程(组)的逼近, 这样可以用标准的数值技术(例如欧拉法,龙格-库塔方法等)求解。FEA的基本思路是用较简单的问题代替复杂问题后再求解。它将求解域看成是由许多称为有限元的小的互连子域组成，对每一单元假定一个合适的(较简单的）近似解，然后推导求解这个域总的满足条件(如结构的平衡条件），从而得到问题的解。这个解不是准确解，而是近似解，因为实际问题被较简单的问题所代替。由于大多数实际问题难以得到准确解，而有限元不仅计算精度高，而且能适应各种复杂形状，因而成为行之有效的工程分析手段。 网格划分是有限元分析中不可缺少的前处理阶段，被处理对象只有在被网格化之后才能运用有限元方法进行求解分析。网格生成的方法多种多样，整体上可以分为两大类：结构化网格生成方法和非结构化网格生成方法。按照求解问题的复杂程度又可划分为结构化网格生成方法、非结构化网格生成方法和笛卡尔网格生成方法。其中笛卡尔法是特殊的非结构网格生成方法。[1]结构化方法数据结构简单，运算速度快，适用于相对简单的边界情况；非结构化方法适用于复杂的边界形状，数据结构比结构化方法稍复杂；笛卡尔方法是三者中数据结构最为复杂的，但其计算精度高、易于实现、便于网格自动划分，故适用于更为复杂的边界情况。 按照网格类型网格划分方法可分为三角形网格划分、四边形网格划分和混合网格划分。其中混合网格划分是指生成的网格中既有三角形网格又有四边形网格。三角形网格生成容易，有良好的理论基础，但移点时网格需要局部重划分；四边形网格需要处理好边界切割情况，可以灵活地调整点的位置而不必重新划分网格。混合网格结合了三角形网格和四边形网格的优点，有很好的适应性。 四边形网格的划分方法也有多种，常见的有三角形合并法（也称间接法）、铺砌法(Paving)、推进波前法(Advancing Front Method)、基于栅格法等。本课题将要研究的四叉树网格划分就属于基于栅格法。 选题依据和背景情况 四叉树是一种具有继承性的数据结构，但它对应的是一种空间分解方法.Samet[2]详述了四叉树的起源、应用及相关算法.四叉树最初是用来进行二进制的计算机图像处理，存储图像信息。Hunter第一次给出了“四叉树”这个命名。 将四叉树空间分解方法应用于网格生成的引路人是Yerry和Shephard. 其基本思想如下:首先将目标区域用一尽可能小的正方形圈定，然后将此正方形分解成四个相同大小的子区域，对每一个子域，测试其是否完全在目标域外面或是满足密度控制的要求，若满足所给定的条件则停止对此子域的细分，否则将之细分，该过程迭代执行下去直至达到预定的离散要求.这样目标区域被一些相互不重叠的各种大小的方形子域拼成的图形所逼近，这些子域是由最初的正方形分解而成，但目标区域本身自始至终并不被分解. 从1983年四叉树网格划分的提出到现在，四叉树网格划分方法的发展大致经历了以 下几个阶段：早期的四叉树、早期的修改四叉树以及改进的修改四叉树。然而四叉树网格划分方法在理论方面仍没有三角形网格划分那样成熟。 课题研究目的 1）解决四叉树网格划分的边界切割处理问题，增强网格的自适应性； 2）改进网格的悬点处理方法，使悬点处理更加合理； 3）在不增添新的悬点的前提下，四边形化边界切割处理后的图形，增强网格边界的自适应性； 4）解决四叉树网格划分的多边界网格划分的问题，增强四叉树网格划分的应用范围； 5）解