三维数据结构及其分类.docxVIP

三维数据结构及其分类姓名：班级：学号：日期：三维数据结构及其分类一、引言随着GIS理论的日趋成熟及其应用的不断拓展，其许多商业化的GIS软件的功能也逐渐完善。但是绝大多数的商品化GIS软件包还只是在二维平面基础上对现实世界的实体及实体之间的关系的模拟和处理，而我们生活在三维的世界里，所涉及到的有关气象、水文、采矿、灾害、污染等方面的自然现象都是三维的，显然当我们仅仅用二维的方法和思路解释和处理三维问题时，就不能够精确地或正确地反映、存储、分析、处理和显示地理空间信息。因此，为更逼真精确地描述现实三维世界，探讨和研究三维数据结构显得尤为重要。二、三维数据结构数据结构是即数据的逻辑结构形式，我们所熟悉的是二维数据结构，从类别上分，二维数据结构包括矢量数据结构、栅格数据结构、矢量-栅格一体化数据结构等，这主要是依据其数据模型进行分类的，即栅格数据模型、矢量数据模型、面向对象数据模型等，这与我们通常先建立数据模型，再依据数据模型选用合适的数据结构对数据进行组织的思路是一致的。通常我们所说的三维景观可视化和已经具有的2.5维表面建模都还不是真正意义上的三维，比如利用DEM数据建立的三维景观模型可视化，或者利用多属性的实体的某一属性作为第三维对平面图形进行三维显示等。如利用v = f(x,y)表达一个二维系统，(x,y)是二维平面坐标，v是对应点的属性值，当v表示高程时，就可以表示数字高程模型。但这里v受x,y变化的影响；而真正意义上的三维数据模型中，三维变量之间应是相互独立的。也就是说，对于一个真正的三维数据模型，可以用V = f(x,y,z)来描述，其中z是自变量，不受x，y变化的影响，即(x,y,z)是在三维空间连续变化的。总的来说，即是与二维相比，三维多出了一维，但仍然可以将二维的观点引入对三维的研究之中。三维空间数据模型是人们对客观世界的理解和抽象，是建立三维空间数据库的理论基础。三维空间数据结构是三维空间数据模型的具体实现，是客观对象在计算机中的底层表达，是对客观对象进行可视表现的基础。引入二维空间数据模型的部分理念后，且在三维空间里进一步作适当合理的扩展，地理实体可以分为点、线、面和体四种基本元素，由这四种元素构成复杂的三位目标。这样，将地理实体的三维空间分成细小的单元，称之为体元素或体元，并将其作为三维空间研究的原子项，并用二值化的思想判断体元与实体之间的关系，即体元包含在实体内，则赋值为1，否则赋值为0.体元可以是正立方体、正方体、四面体或其它非规则形状等。在对三维数据模型作了较为成熟的认识之后，三维数据结构的建立便于有了一定的依据。为了实现将三维的空间实体模型在计算机之中存储、处理、检索、查询、分析和显示，必须利用适于计算机表达、存储和管理的三维数据结构对现实建立的三维数据模型进行表达。同样，考虑二维数据结构，并将其在三维空间进行拓展，可以得到对应的三维数据结构，即八叉树三维数据结构。利用八叉树来表示三维形体，既可以看成是四叉树方法在三维空间的推广，也可以是用三维体素列阵表示形体方法的一种改进。其逻辑结构可以定义如下。假设要表示的形体T可以放在一个充分大的实体C内,C的边长为2n，形体TC，它的八叉树可以用以下递归的方法来定义：八叉树的每个节点与C的一个子立方体对应，树根与C本身相对应，如果T=C，那么T的八叉树仅有树根，如果T不等于 C，则C等分为八个子立方体，每个子立方体与树根的一个子节点相对应。只要某个子立方体不是完全空白或完全为T所占据，就要被八等分，从而对应的节点也就有了八个子节点。这样递归判断、分割一直要进行到节点所对应的立方体或是完全空白，或者是完全为T占据，或是其大小已是预先定义的体素大小，并且对它与T之交作一定的“舍入”，使体素或认为是空白的，或认为是T占据的。如此所生成的八叉树上的节点可以分为三类：一是灰节点，对应的立方体部分地为T所占据；二是白节点，对应的立方体中无T的内容；三是黑节点，对应的立方体全为T所占据。后两类又称为叶节点。与四叉树结构相类似的八叉树结构可以沿用四叉树的有关方法。根据存储方式的不同，八叉树可以分为常规的、线形的、一对八的八叉树等等。1）规则的八叉树八叉树的存储结构是用一个有九个字段的记录来表示树中的每个结点，其中一个字段用来秒苏该结点的特性，其余的八段用来作为存放指向其八个子结点的指针。但是规则八叉树的缺陷较多，最大的问题就是指针占用了很大的空间。因此虽然其易于理解掌握，但存储代价太大。2）线形八叉树线形八叉树注重考虑的是如何提高空间利用率，用某一预先确定的次序遍历八叉树，将八叉树转换成一贯线形表，表的每个元素与一个结点相对应。线形八叉树不仅节省存储空间，对某些运算也比较方便，但是不够灵活。3）一对八式的八叉树在一对八式的八叉树中，一个非叶结点有八个子结点，如果一个记录与一