三维数据结构及其分类

1、三维数据结构及其分类姓名:班级:学号:日期:三维数据结构及其分类一、引言随着GIS理论的日趋成熟及其应用的不断拓展，其许多商业化的GIS软件的 功能也逐渐完善。但是绝大多数的商品化GIS软件包还只是在二维平面基础上对 现实世界的实体及实体之间的关系的模拟和处理，而我们生活在三维的世界里， 所涉及到的有关气象、水文、采矿、灾害、污染等方面的自然现象都是三维的， 显然当我们仅仅用二维的方法和思路解释和处理三维问题时，就不能够精确地或 正确地反映、存储、分析、处理和显示地理空间信息。因此，为更逼真精确地描 述现实三维世界，探讨和研究三维数据结构显得尤为重要。二、三维数据结构数据结构是即数据的逻辑结构

2、形式，我们所熟悉的是二维数据结构，从类别上分， 二维数据结构包括矢量数据结构、栅格数据结构、矢量-栅格一体化数据结构等， 这主要是依据其数据模型进行分类的，即栅格数据模型、矢量数据模型、面向对 象数据模型等，这与我们通常先建立数据模型，再依据数据模型选用合适的数据 结构对数据进行组织的思路是一致的。通常我们所说的三维景观可视化和已经具有的2.5维表面建模都还不是真正 意义上的三维，比如利用DEM数据建立的三维景观模型可视化，或者利用多属 性的实体的某一属性作为第三维对平面图形进行三维显示等。如利用v = f(x,y)表 达一个二维系统，(x,y)是二维平面坐标，v是对应点的属性值，当v表示高程

3、时， 就可以表示数字高程模型。但这里v受x,y变化的影响；而真正意义上的三维数 据模型中，三维变量之间应是相互独立的。也就是说，对于一个真正的三维数据 模型，可以用V = f(x,y,z)来描述，其中z是自变量，不受x，y变化的影响，即(x,y,z) 是在三维空间连续变化的。总的来说，即是与二维相比，三维多出了一维，但仍 然可以将二维的观点引入对三维的研究之中。三维空间数据模型是人们对客观世界的理解和抽象，是建立三维空间数据库 的理论基础。三维空间数据结构是三维空间数据模型的具体实现，是客观对象在 计算机中的底层表达，是对客观对象进行可视表现的基础。引入二维空间数据模型的部分理念后，且在三维空

4、间里进一步作适当合理的 扩展，地理实体可以分为点、线、面和体四种基本元素，由这四种元素构成复杂 的三位目标。这样，将地理实体的三维空间分成细小的单元，称之为体元素或体 元，并将其作为三维空间研究的原子项，并用二值化的思想判断体元与实体之间 的关系，即体元包含在实体内，则赋值为1，否则赋值为0.体元可以是正立方体、 正方体、四面体或其它非规则形状等。在对三维数据模型作了较为成熟的认识之后，三维数据结构的建立便于有了 一定的依据。为了实现将三维的空间实体模型在计算机之中存储、处理、检索、 查询、分析和显示，必须利用适于计算机表达、存储和管理的三维数据结构对现 实建立的三维数据模型进行表达。同样，考

5、虑二维数据结构，并将其在三维空间 进行拓展，可以得到对应的三维数据结构，即八叉树三维数据结构。利用八叉树来表示三维形体，既可以看成是四叉树方法在三维空间的推广， 也可以是用三维体素列阵表示形体方法的一种改进。其逻辑结构可以定义如下。假设要表示的形体T可以放在一个充分大的实体C内,C的边长为2n，形体 TC，它的八叉树可以用以下递归的方法来定义：八叉树的每个节点与C的一个子 立方体对应，树根与C本身相对应，如果T=C，那么丁的八叉树仅有树根，如果 T不等于C，则C等分为八个子立方体，每个子立方体与树根的一个子节点相对 应。只要某个子立方体不是完全空白或完全为T所占据，就要被八等分，从而对 应的节

6、点也就有了八个子节点。这样递归判断、分割一直要进行到节点所对应的 立方体或是完全空白，或者是完全为T占据，或是其大小已是预先定义的体素大 小，并且对它与T之交作一定的“舍入”，使体素或认为是空白的，或认为是T 占据的。如此所生成的八叉树上的节点可以分为三类：一是灰节点，对应的立方 体部分地为T所占据；二是白节点，对应的立方体中无T的内容；三是黑节点， 对应的立方体全为T所占据。后两类又称为叶节点。与四叉树结构相类似的八叉树结构可以沿用四叉树的有关方法。根据存储方 式的不同，八叉树可以分为常规的、线形的、一对八的八叉树等等。1）规则的八叉树八叉树的存储结构是用一个有九个字段的记录来表示树中的每个

7、结点，其中 一个字段用来秒苏该结点的特性，其余的八段用来作为存放指向其八个子结点的 指针。但是规则八叉树的缺陷较多，最大的问题就是指针占用了很大的空间。因 此虽然其易于理解掌握，但存储代价太大。2）线形八叉树线形八叉树注重考虑的是如何提高空间利用率，用某一预先确定的次序遍历 八叉树，将八叉树转换成一贯线形表，表的每个元素与一个结点相对应。线形八 叉树不仅节省存储空间，对某些运算也比较方便，但是不够灵活。3）一对八式的八叉树在一对八式的八叉树中，一个非叶结点有八个子结点，如果一个记录与一个 结点对应，那么在这个记录中描述的是这个结点的八个子结点的特征值，而指针 给出的则是该八个子结点所对应记录的

8、存放处，而且还隐含地假设了这些子结点 记录存放的次序。也就是说，即使某个记录是不必要的，那么相应的存储位置也 必须空闲在那里，以保证不会错误地存取到其它同层结点的记录。很显然，当它 不是完全八叉树的时候，存储空间会有一定的浪费。为了克服这种缺陷，一是增 加计算量，即在存取相应结点记录之前，首先检查它的父结点记录，看一下之前 有几个叶结点，从而可以知道应该如何存取所需结点记录。这种方法可以减小存 储需求，但会增加计算量；另一个是在记录中增加一定的信息，使计算工作适当 减少或者更方便。例如在原记录中增加三个字节，一分为八，每个字节点对应三 位，代表它的子结点在指针指向区域中的偏移。因此，要找到它的

9、子结点记录位置，只要固定地把指针指向的位置加上这个偏移量乘上记录所占的字节数，就是 所要的位置，因而一个结点可以描述为：偏移指针SWESWTNWBNWTSETSEBNETNEB用这种方式所得到的八叉树和以前相同，只是每个记录前多了三个字节。三、分类与二维数据结构类比，可将三维数据结构分为三维矢量数据结构、三维栅格 数据结构、矢量栅格一体化三维数据结构、面向对象三维数据结构、镶嵌数据结 构等。基于镶嵌数据模型的三维数据结构可以利用有四面体格网法、单纯形剖分 法、空间枚举法、单元分解法等表达；基于矢量的数据模型的三维数据结构可以 利用线框表示法、实体模型法、表面剖分法等表达；基于分析型的数据模型的

10、三 维数据结构可以利用非均匀有理B样条函数等进行表达;此外还有混合型数据结 构，其可用构造几何体法、面向对象思想以及与树结构相结合进行表达。其中三 维数据结构的最重要的一个分类依据就是实际应用，通过对现实世界表达的需要 分析以寻求利用一种合适的三维数据结构来表达三维空间实体及实体之间的关 系。但其从二维空间数据结构进行拓展来定义三维数据结构以及结合三维的特点 在适当三维模型构建的基础之上进行三维数据结构的定义对利用三维数据结构 来研究现实世界的三维空间实体以及其关系提供了科学的方法。四、结论三维数据模型的构建和三维数据结构的组织对于三维空间数据的收集、存储、 管理、分析、表达和显示是不可或缺的。三维数据模型具有较为