基于四叉树的复杂边界四边形网格自适应生成方法研究

地理信息系统考试复习题1、地理信息的概念及特点：定义：指与研究对象的空间地理分布有关的信息。

它表⽰地理系统诸要素的数量、质量、分布特征，相互联系和变化规律的图、⽂、声、像等的总称。

A、地域性：（是地理信息区别于其它类型信息的最显著标志）。

地理信息属于空间信息，位置的识别与数据相联系，它的这种定位特征是通过公共的地理基础来体现的B、多维结构：指在同⼀位置上可有多种专题的信息结构。

如某⼀位置上的地理信息包括C、时序特征：时空的动态变化引起地理信息的属性数据或空间数据的变化2、地理信息系统的概念及组成概念：GIS是由计算机硬件、软件和不同的⽅法组成的系统，该系统设计⽤来⽀持空间数据的采集、管理、处理、分析、建模和显⽰，以便解决复杂的规划和管理问题。

组成：⽤户（GIS服务的对象，分为⼀般⽤户和从事建⽴、维护、管理和更新的⾼级⽤户软件（⽀持数据采集、存储、加⼯、回答⽤户问题的计算机程序系统）硬件（各种设备-物质基础）数据（系统分析与处理的对象、构成系统的应⽤基础）4、GIS的输⼊和输出设备有哪些输⼊：数字化、解析测图仪、扫描仪遥感处理设备等输出：打印机绘图仪显⽰终端5、GIS的功能和应⽤（论述题）GIS的功能：、数据采集与输⼊、数据编辑与更新数据、存储与管理、数据显⽰与输出应⽤：GIS最初就是起源于资源调查，是GIS的最基本的职能，⽬前趋于成熟的主要应⽤领域。

资源调查包括⼟地资源，森林资源和矿产资源的调查、管理、⼟地利⽤规划，野⽣动物的保护等。

GIS的主要任务是将各种来源的数据和信息有机地汇集在⼀起，并通过统计，叠量分析等功能，按多种边界和属性条件，提供区域多种条件组合形式的资源统计和资源现状分析，从⽽为资源的合理开发、利⽤提供依据。

在进⾏区域和城镇规划的过程中，要处理许多不同性质和不同特点的问题，涉及多⽅⾯要素，如资源、环境、⼈⼝、交通、经济、教育、⽂化和⾦融等，GIS将这些数据信息归算到城市的统⼀系统之中，最后进⾏城市和区域多⽬标的开发和规划，包括城镇总体规划，城市建设⽤地适宜性评价，城市环境选质量评价，道路交通规划，公共设施配置及城市环境动态监测等，这些功能的实现是以GIS的⼀些数据处理和分析算法加以保证的，如GIS的空间搜索⽅法，多信息叠加处理和⼀系列的分析软件，回归分析，投⼊产出计算，模糊加权评价等。

地理信息系统概论课后习题部分答案第一章1、什么是地理信息系统（GIS)?它与一般计算机应用系统有哪些异同点？答：地理信息系统：是由计算机硬件、软件和不同的方法组成的系统，该系统设计支持空间数据的采集、管理、处理、分析、建模和显示，以便解决复杂的规划和管理问题. GIS 脱胎于地图学，是计算机科学、地理学、测绘遥感学、环境科学、城市科学、空间科学、信息科学和管理科学等众多学科交叉融合而成的新兴学科。

但是，地理信息系统与这学科和系统之间既有联系又有区别: （1）GIS 与机助制图系统机助制图是地理信息系统得主要技术基础,它涉及GIS 中的空间数据采集、表示、处理、可视化甚至空间数据的管理。

地理信息系统和数字制图系统的主要区别在于空间分析方面。

一个功能完善的地理信息系统可以包含数字制图系统的所有功能，此外它还应具有丰富的空间分析功能。

（2）GIS 与DBMS(数据库管理系统）GIS 除需要功能强大的空间数据的管理功能之外，还需要具有图形数据的采集、空间数据的可视化和空间分析等功能。

因此，GIS 在硬件和软件方面均比一般事务数据库更加复杂, 在功能上也比后者要多地多。

(3)GIS 与CAD 系统二者虽然都有参考系统，都能描述图形，但CAD 系统只处理规则的几何图形、属性库功能弱,更缺乏分析和判断能力。

(4）GIS 与遥感图像处理的系统遥感图像处理的系统是专门用于对遥感图像数据处理进行分析处理的软件。

它主要强调对遥感栅格数据的几何处理、灰度处理和专题信息提取。

这种系统一般缺少实体的空间关系描述，难以进行某一实体的属性查询和空间关系查询以及网络分析等功能。

2、地理信息系统有哪几个主要部分组成?它的基本功能有哪些？试举目前广泛应用的两个基础地理信息系统软件为例,列出它们的功能分类表,并比较异同点?（1)系统硬件:包括各种硬件设备,是系统功能实现的物质基础；（2)系统软件：支持数据采集、存储、加工、回答用户问题的计算机程序系统；(3)空间数据:系统分析与处理的对象，构成系统的应用基础；(4）应用人员：GIS 服务的对象，分为一般用户和从事建立、维护、管理和更新的高级用户；（5）应用模型：解决某一专门应用的应用模型，是GIS 技术产生社会经济效益的关键所在.3、试说明地理信息系统的基本分析功能与应用模型之间的区别和联系是什么？答: 地理信息系统分析功能是基于现有数据按照一定规律或者参数进行计算得出的结构，这些规律和参数就可以构成一个应用模型, 比如降雨量计算模型和风力强度计算模型等. 但应用模型很多是专业领域的模型，其表现可以是参数表格也可以是图标或计算公式, 不利于地理信息这种要与地理坐标想联系, 并且需要特殊的可视化效果的信息分析与表达。

Bandelet变换原理及应用研究杨思燕【摘要】In recent years,multi-scale geometric analysis (MGA) has been widely used for research and applications in statistical analysis,pattern recognition,signal processing and digital image processing,etc.As an adaptive MGA method,Bandelet transform can track geometrical regularity of image structure adaptively and represent sharp image transition.Being able to provide the sparsest representation,Bandelet could use less nonzero coefficients to reach the same identification effect as other basic functions,especially more superior in image with significant geometric features.Introduced the development and principles of Bandelet transform in detail,and further researched the application in imagesmoothing,compression,segmentation and fusion.Finally trend in development were also pointed out.%近年来,多尺度几何分析在统计分析、模式识别、信号处理、数字图像处理等领域中应用广泛.作为自适应多尺度几何分析的一种新方法,Bandelet变换侧重于图像边缘的表示和处理,对于图像中的几何正则方向具有较强的自适应跟踪能力,由于Bandelet变换能提供对图像的最稀疏表示,能够用比别的基函数更少的非零系数来达到同样的逼近效果,特别是对几何特征明显的图像更具优势.文中详细介绍了Bandelet变换的提出、基本原理和方法等技术实现细节,探讨和和分析了Bandelet变换在数字图像的压缩、融合、去噪和分割等诸多方面的应用,并探讨了Bandelet变换技术的应用发展趋势.【期刊名称】《计算机技术与发展》【年(卷),期】2013(023)007【总页数】6页(P233-237,241)【关键词】多尺度几何分析;小波变换;Bandelet变换;去噪;压缩【作者】杨思燕【作者单位】陕西广播电视大学计算机与信息管理系,陕西西安710119【正文语种】中文【中图分类】TP390 引言多尺度集合分析(Multiscale Geometric Analysis，MGA)近年来在信号处理、数学分析、计算机视觉和模式识别等学科和领域应用广泛，发展迅速。

收稿日期:2000211229;修改稿收到日期:20012082101作者简介:张　(19752),男,硕士,助理工程师1第19卷第3期2002年8月　计算力学学报　Ch i nese Journa l of Co m puta tiona l M echan icsV o l .19,N o .3A ugu st 2002文章编号:100724708(2002)0320359206简单高效的面向对象四叉树有限元网格生成技术研究张 1,　汤广发,　邓启红,　张峻岭2(11湖南大学土木工程学院,长沙410082;21核工业第五研究设计院,郑州450052)摘　要:用面向对象的思想和方法与四叉树有限元网格生成结合,创建或改进了网格生成各个阶段的算法和实现方式,并在面向对象语言V C ++610中得以实现。

能快速、高效地生成适用于任何复杂边界的四叉树有限元网格,易于自适应,易于局部加密和稀疏化。

关键词:面向对象;四叉树;有限元网格;自适应;局部加密中图分类号:T P 39117 文献标识码:A1　前　言有限元网格生成技术发展至今,许多方法相继出现,且日渐成熟。

为了提高复杂边界网格的质量,结合不同网格生成方法的优势,出现了混合生成方法。

但随之而来的问题是网格生成耗时偏多,有的甚至超过有限元计算。

四叉树有限元网格生成技术作为网格生成技术的典型代表,其优点在于网格生成和通量计算的简单易行以及数据结构的简化;可继承的网格把网格信息存储在四叉树的数据结构中,提供了非结构网格的灵活性;在流动区域它可达到二阶精度且与物面无关,从而消除了网格生成中所有难点[1]。

四叉树网格生成的耗时主要集中在大量数据的存储及对边界网格的处理上,但长期以来,研究者将大量的精力放在处理边界网格上,因此编程更加繁琐,致使网格生成的效率不高,在加上四叉树网格生成的实现方式本已相当复杂,故国内研究的单位不多。

本文将四叉树网格生成技术与面向对象的方法相结合,减少了编程代码;在网格生成过程中,提出边界相对密度的概念,用于边界离散,并结合“网格既定最大划分层”控制网格划分的程度;提出“方向数字化”的网格邻居查寻算法改进了已有算法,提高了查寻效率;针对具有非结构网格特征的四叉树网格,提出“以列为序”的数据提取算法,提高了网格生成的效率,并通过大量的实例验证了它的正确可行性;对于区域边界,直接用正方形网格逼近,直至达到既定要求。

基于四叉树法和波前法的混合网格划分算法的研究和实现
随着计算机技术和信息技术的广泛应用和飞速发展,网格生成技术已成功应用于计算力学、流体力学、有限元分析等工程领域,成为解决数值解析与模拟等复杂问题的强有力手段。

本文对网格生成的相关技术进行了研究与探讨,内容主要包括:对现有曲面网格划分技术进行了研究比较,主要分析探讨了映射法、Delaunay三角剖分法、铺砌法、四叉树法、波前法和三角合成法等常用算法。

将四叉树法、波前法和三角合成法相结合,在映射法的基础上设计并实现了一种新的网格划分方法。

该方法首先将裁剪曲面边界离散成多边形,然后使用四叉树法对待划分裁剪参数曲面按细分要求进行递归分解,最终生成规则的栅格点,再利用波前法的原理生成三角形网格,通过三角合成法生成三角形与四边形混合网格。

针对网格划分算法的具体实现细节,采用了一些可以增强算法稳定性和可靠性,提高算法效率的措施。

在上述技术研究的基础上,将该曲面自动网格划分算法成功应用于板料成形模拟的CAE软件中,该算法具有自适应能力强,网格生成速度快,稳定可靠等优点。

全自动自适应四边形网格生成程序AUTOMESH-2D有限元法是随着计算机技术迅速发展起来的一种现代计算方法，广泛应用于各类复杂工程问题的求解、结构分析、成形过程分析等。

采用有限元分析时，首先需要对分析对象进行网格划分，对于大变形成形问题，随着计算网格的畸变还需要进行多次网格重划。

有限元网格划分是一个费时且容易出错的过程。

网格划分的质量对有限元分析结果有着很大的影响。

一个高效、可靠、全自动、高质量的网格生成或再生成程序是有限元软件不可缺少的部分。

AUTOMESH-2D是由山东大学模具工程技术研究中心赵国群教授、马新武博士在自主研究开发的可靠的网格生成算法基础上，自主开发的一套四边形网格生成程序。

该程序特别适用于成形过程有限元分析的网格生成与再生成，也适用于其它工程问题有限元分析的网格生成。

AUTOMESH本身具有几何输入功能，可显示网格划分结果，并可对网格节点编号进行优化。

AUTOMESH既可以以独立的软件系统提供给用户，也可以以动态连接库的形式提供给有限元软件开发商，作为其软件的一个模块。

AUTOMESH-2D程序的主要特点:(1)采用多种网格密度生成方法，可根据边界曲率、厚度方向单元数目、旧网格场量如温度、应变、应变速率场的梯度以及指定的窗口密度由系统自动生成合理的网格密度分布，也可由用户采用手工的方法，在边界和内部指定网格密度；(2)生成的单元质量高，单元的内角在30度和150度之间，尤其是边界单元，其质量更高；(3)单元数目易于控制，要求划分单元数目与实际划分单元数目的误差不超过10%；(4)划分速度快，划分1000个网格单元所需时间<1s，划分10,000个网格单元所需要时间<10s，划分100,000个网格单元所需要时间<2min；(5)简便易用，输入参数少，一般情况下只需要输入几何形状、要划分单元数据以及密度控制参数即可；(6)既适用于初始网格的生成，也适用于网格畸变后的网格再生成。

空间索引-四叉树前⾔作为程序员，应该都对⼆叉树都不陌⽣，我们都知道⼆叉树的变体⼆叉查找树，⾮常适合⽤来进⾏对⼀维数列的存储和查找，可以达到 O(logn) 的效率；我们在⽤⼆叉查找树进⾏插⼊数据时，根据⼀个数据的值和树结点值的对⽐，选择⼆叉树的两个叉之⼀向下，直到叶⼦结点，查找时使⽤⼆分法也可以迅速找到需要的数据。

但⼆叉树只⽀持⼀维数据，如⼀个标量数值，对地图上的位置点这种有xy两个⽅向上的信息却⽆能为⼒，那么是否有⼀种树能够⽀持⼆维数据的快速查询呢？四叉树介绍四元树⼜称四叉树是⼀种树状数据结构，在每⼀个节点上会有四个⼦区块。

四元树常应⽤于⼆维空间数据的分析与分类。

它将数据区分成为四个象限。

今天要介绍的四叉树可以认为是⼆叉查找树的⾼维变体，它适合对有⼆维属性的数据进⾏存储和查询，当然四叉树存储的也不⼀定是⼆维数据，⽽是有着⼆维属性的数据，如有着 x,y 信息的点，⽤它还可以⽤来存储线和⾯数据。

它有四个叉，在数据插⼊时，我们通过其⼆维属性（⼀般是 x,y）选择四个叉之⼀继续向下，直⾄叶⼦结点，同样使⽤“四分法”来迅速查找数据。

四叉树的⼀般图形结构如下：聪明的⼩伙伴⼀定想到了适合存储和查询三维数据的⼋叉树，它们原理是⼀致的，不过我们暂不讨论。

分类四叉树常见的应⽤有图像处理、空间数据索引、2D中的快速碰撞检测、稀疏数据等，今天我们很纯粹地只介绍它在空间索引⽅⾯的应⽤。

根据其存储内容，四叉树可以分为点四叉树、边四叉树和块四叉树，今天我们实现的是点四叉树。

根据其结构，四叉树分为满四叉树和⾮满四叉树。

对于满四叉树，每个节点都有四个⼦结点，它有着固定的深度，数据全都存在最底层的⼦结点中，进⾏数据插⼊时不需要分裂。

满四叉树在确定好深度后，进⾏插⼊操作很快，可是如果⽤它来存储下图所⽰数据，我们会发现，四叉树的好多叉都是空的，当然它们会造成内存空间的⼤量浪费。

⾮满四叉树解决了此问题，它为每个结点添加⼀个“容量”的属性，在四叉树初始化时只有⼀个根结点，在插⼊数据时，如果⼀个结点内的数据量⼤于了结点“容量”，再将结点进⾏分裂。

四叉树结构的基本思想是将一幅栅格地图或图像等分为四部分，逐块检查其格网属性值(或灰度)，如果某个子区的所有格网值都具有相同的值，则这个子区就不再继续分割，否则还要把这个子区再分割成四个子区。

这样依次地分割，直到每个子块都只含有相同的属性值或灰度为止。

从下而上的合并算法：如果每相邻四个网格值相同则进行合并，逐次往上递归合并，直到符合四叉树的原则为止。

这种方法重复计算较少，运算速度较快。

从上而下的分割算法：需要大量的运算，因为大量数据需要重复检查才能确定划分。

当矩阵比较大，且区域内容要素又比较复杂时，建立这种四叉树的速度比较慢。

②阵列各部分的分辨率是可变的，边界复杂部分四叉树较高即分级多，分辨率也高，而不需表示许多细节的部分则分级少，分辨率低，因而既可精确表示图形结构又可减少存贮量；②结点之间借助指针联系，每个结点需要用六个量表达：四个叶结点指针，一个父结点指针和一个结点的属性或灰度值。

②线性四叉树叶结点的编号需要遵循一定的规则，这种编号称为地址码，它隐含了叶结点的位置和深度信息。

最常用的地址码是四进制或十进制的Morton 码。

①常规四叉树除了记录叶结点之外，还要记录中间结点。

③这些指针不仅增加了数据贮存量，而且增加了操作的复杂性。

常规四叉树主要在数据索引和图幅索引等方面应用。

③栅格到四叉树及四叉树到简单栅格结构的转换比其它压缩方法容易；①容易而有效地计算多边形的数量特征；为了保证四叉树能不断的分解下去，要求图像必须为2n*2n 的栅格阵列，n 为极限分割次数，n+1是四叉树的最大高度或最大层数。

①线性四叉树则只存贮最后叶结点的信息。

包括叶结点的位置、深度和本结点的属性或灰度值。

（1）常规四叉树（2）线性四叉树④多边形中嵌套异类小多边形的表示较方便。

四叉树的生成算法：四叉树结构分类：四叉树编码的特点：基于十进制的Morton 码及四叉树的建立 ：2.2.4 四叉树编码(quad-tree code)[四叉树分割演示]十进制的Morton 码实际上是II 、JJ 中的二进制数字交叉结合的结果，即设十进制表示的行、列号在计算机内部的二进制数字分别为：[上一根节][下一根节][回节目录][根节目录]在生成的线性四叉树表中，仍存在前后叶结点的值相同的情况，因而可以采取进一步的压缩表达，即将格网值相同的前后结点合并成一个值，形成二维行程编码（Two Dimensional Run Encoding ，简称 2DRE ）表。

四叉树碰撞优化版，速度飞一样原来对四叉树有点恐惧，完全不知道这东西怎么回事，觉得很高级，只好花时间研究了一下，最终效果如下：下面是对四叉树的基本介绍。

懂四叉树的同学可以直接跳过前面看优化部分。

四叉树很简单，就是把一块2d的区域，等分成4份,如下图: 我们把4块区域从右上象限开始编号，逆时针。

[查看图片]接着每份继续等分4份。

[查看图片]一直到我们不需要再继续等分为止。

每次插入对象，对象都在其中一个格子里。

进行碰撞检测的时候，对象只会和他同在一个格子里的以及周围的一些对象进行检测，所以提高了效率。

四叉树的原理大致就是这样，和网格法差不多，简单说就是分格子，检测。

//---------------------------------------------分割线-----------------------------------------------------------//以下部分会对四叉树的实现以及优化进行说明。

下面我们对四叉树进行实现：主要代码复制代码MAX_OBJECTS是每个节点能容纳的最多对象超过则分割4个节点, 我们并不是事先就分好格子，而是在插入对象的时候才进行划分。

MAX_LEVELS是四叉树的最大层数超过则不再划分从根节点开始最多6 层。

level：当前层数objects: 当前节点内的待检测的对象。

bounds 当前节点所表示的2d区域的范围nodes: 4个子节点队列。

构造函数：复制代码分割函数：复制代码如你所见，每次划分节点，都会把父节点的区域对半分。

辅助方法getIndex:复制代码这个方法是返回你所要碰撞检测的矩形在哪块区域(当前节点)。

比如当前区域是Rectange(0, 0, 600, 600) 待检测矩形是Rectangel(0, 0, 30, 30) 那么他就在左上象限index = 1 如果是Rectange(400, 400, 30, 30) 那么他就在右下象限index = 3 请注意，当对象刚好在区域的中心线上的时候，也会返回-1。

四边形网格间接生成方法刘晶;聂玉峰;苏少普【摘要】研究了基于背景三角网格的四边形网格间接生成算法,并针对三角形合并过程中容易残留三角形的缺陷提出了确定侧边的详细算法,该算法主要是依据背景三角网格中边的位置和前沿边的情形,通过背景三角网格中已存在的边、边交换或边分割确定侧边,以避免在三角形合并过程中残留三角形单元.最后给出实例验证了算法的有效性.【期刊名称】《计算机工程与应用》【年(卷),期】2010(046)002【总页数】4页(P44-47)【关键词】四边形网格;三角形合并;前沿边【作者】刘晶;聂玉峰;苏少普【作者单位】西北工业大学,应用数学系,西安,710072;西北工业大学,应用数学系,西安,710072;西北工业大学,应用数学系,西安,710072【正文语种】中文【中图分类】O242.211 引言随着有限元方法在工程中的深入广泛应用，人们对有限元计算精度的要求越来越高，而网格的质量对有限元计算精度有重大影响，因而对网格生成方法的研究一直受到人们的重视[1-13]。

二维区域中常用的有三角形网格和四边形网格，三维区域上则常用四面体、三棱柱或六面体网格。

对二维问题，三角形网格的生成算法理论已相对较为成熟，但在具体的求解过程中，使用三角形元的求解精度通常不及使用四边形元的求解精度，故研究基于三角形网格的四边形网格生成算法。

2 基本概念（1）固定节点和可动节点：位于区域边界上的节点为固定节点，区域内部的点则为可动节点。

（2）节点连通度：在网格内与节点相连的单元数目即为节点的连通度。

（3）不规则节点：在四边形网格内部节点连通度不为4的节点即为不规则节点。

（4）结构化网格：是指网格内部各节点的连通度相同的网格。

（5）非结构化网格：与结构化网格相对，非结构化网格是指网格内部各节点的连通度不同的网格。

（6）几何优化：是指调整可动节点的位置而不改变节点的拓扑连接关系以改进网格质量的操作。

（7）拓扑优化：是指改变可动节点的拓扑连接关系以改进网格质量的操作。