三维数据结构及其分类

三维数据结构及其分类

姓名:

班级:

学号:

日期:

三维数据结构及其分类

一、引言

随着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的边长为21形体

TC,它的八叉树可以用以下递归的方法来定义：八叉树的每个节点与C的一个子

立方体对应，树根与C本身相对应，假如T=C,那么T的八叉树仅有树根，假如

T不等于C,则C等分为八个子立方体，每个子立方体与树根的一个子节点相对

应。只要某个子立方体不是完全空白或完全为T所占据，就要被八等分，从而对

应的节点也就有了八个子节点。这样递归推断、分割始终要进行到节点所对应的

立方体或是完全空白，或者是完全为T占据，或是其大小已是预先定义的体素大

小，并且对它与T之交作肯定的“舍入”，使体素或认为是空白的，或认为是T

占据的。如此所生成的八叉树上的节点可以分为三类：一是灰节点，对应的立方

体部分地为T所占据；二是白节点，对应的立方体中无T的内容；三是黑节点，

对应的立方体全为T所占据。后两类又称为叶节点。

与四叉树结构相类似的八叉树结构可以沿用四叉树的有关方法。依据存储方

式的不同，八叉树可以分为常规的、线形的、一对八的八叉树等等。

1）规章的八叉树

八叉树的存储结构是用一个有九个字段的纪录来表示树中的每个结点，其中

一个字段用来秒苏该结点的特性，其余的八段用来作为存放指向其八个子结点的

指针。但是规章八叉树的缺陷较多，最大的问题就是指针占用了很大的空间。因

此虽然其易于理解把握，但存储代价太大。

2）线形八叉树

线形八叉树注意考虑的是如何提高空间采用率，用某一预先确定的次序遍历

八叉树，将八叉树转换成一贯线形表，表的每个元素与一个结点相对应。线形八

叉树不仅节约存储空间，对某些运算也比较便利，但是不够敏捷。

3）一对八式的八叉树

在一对八式的八叉树中，一个非叶结点有八个子结点，假如一个纪录与一个

结点对应，那么在这个纪录中描述的是这个结点的八个子结点的特征值，而指针

给出的则是该八个子结点所对应纪录的存放处，而且还隐含地假设了这些子结点

纪录存放的次序。也就是说，即使某个纪录是不必要的，那么相应的存储位置也

必需空闲在那里，以保证不会错误地存取到其它同层结点的纪录。很明显，当它

不是完全八叉树的时候，存储空间会有肯定的铺张。为了克服这种缺陷，一是增

加计算量，即在存取相应结点纪录之前，首先检查它的父结点纪录，看一下之前

有几个叶结点，从而可以知道应当如何存取所需结点纪录。这种方法可以减小存

储需求，但会增加计算量；另一个是在纪录中增加肯定的信息，使计算工作适当

削减或者更便利。例如在原纪录中增加三个字节，一分为八，每个字节点对应三

位，代表它的子结点在指针指向区域中的偏移。因此，要找到它的子结点纪录位

置，只要固定地把指针指向的位置加上这个偏移量乘上纪录所占的字节数，就是

所要的位置，因而一个结点可以描述为：

偏移指针SWESWTNWBNWTSETSEBNETNEB

用这种方式所得到的八叉树和以前相同，只是每个纪录前多了三个字节。

三、分类

与二维数据结构类比，可将三维数据结构分为三维矢量数据结构、三维栅格

数据结构、矢量栅格一体化三维数据结构、面对对象三维数据结构、镶嵌数据结

构等。基于镶嵌数据模型的三维数据结构可以采用有四周体格网法、单纯形剖分

法、空间枚举法、单元分解法等表达；基于矢量的数据模型的三维数据结构可以

采用线框表示法、实体模型法、表面剖分法等表达；基于分析型的数据模型的三

维数据结构可以采用非匀称有理B样条函数等进行表达;此外还有混合型数据结

构，其可用构造几何体法、面对对象思想以及与树结构相结合进行表达。其中三

维数据结构的最重要的一个分类依据就是实际应用，通过对现实世界表达的需要

分析以寻求采用一种合适的三维数据结构来表达三维空间实体及实体之间的关

系。但其从二维空间数据结构进行拓展来定义三维数据结构以及结合三维的特点

在适当三维模型构建的基础之上进行三维数据结构的定义对采用三维数据结构

来讨论现实世界的三维空间实体以及其关系供应了科学的方法。

四、结论

三维数据模型的构建和三维数据结构的组织对于三维空间数据的收集、存