三维数据结构

1、四、三维四、三维GISGIS数据模型和数据结构数据模型和数据结构在计算机三维实体造型系统中，常用的形体表示技术与方法有: (一)单元分解法：即三维GIS的栅格结构。它以固定形状(如立方体)的单元体规则地分布于空间网格位置上。一个形体就是这些具有邻接关系的大量固定单元的集合，单元大小决定了单元分解形式的精度。 它具有易于存取给定点的优点，能保证空间的唯一性。缺点是各部分关系不够明确，需要耗费大量的存储空间。在实际应用中一般采用八叉树(单元正则形体)或BSP树(单元大小可变形体)的组织形式。 1.八叉树:（octree）是一种用于描述三位空间的树状数据结构。八叉树的每个节点表示一个正方体的体积元素

2、，每个节点有八个子节点，将八个子节点所表示的体积元素加在一起就等于父节点的体积。八叉树的逻辑结构八叉树的逻辑结构如下：假设要表示的形体V可以放在一个充分大的正方体C内，C的边长为2n，形体VC，它的八叉树可以用以下的递归方法递归方法来定义： 八叉树的每个节点与C的一个子立方体对应，树根与C本身相对应，如果VC，那么V的八叉树仅有树根，如果VC，则将C等分为八个子立方体，每个子立方体与树根的一个子节点相对应。只要某个子立方体不是完全空白或完全为V所占据，就要被八等分，从而对应的节点也就有了八个子节点。这样的递归判断、分割一直要进行到节点所对应的立方体或是完全空白，或是完全为V占据，或是其大小已是

3、预先定义的体素大小，并且对它与V之交作一定的“舍入”，使体素或认为是空白的，或认为是V占据的。节点:灰节点:它对应的立方体部分地为V所占据；白节点:它所对应的立方体中无V的内容；黑节点:它所对应的立方体全为V所占据。白节点和黑节点又称为叶结点。形体V关于C的八叉树的逻辑结构是一颗树，其上的节点要么是叶节点，要么就是有八个子节点的灰节点。根节点与C相对应，其它节点与C的某个子立方体相对应。八叉树的存贮结构 常规八叉树 线性八叉树 一对八的八叉树1)1)规则八叉树规则八叉树 规则八叉树的存贮结构用一个有九个字段九个字段的记录来表示树中的每个结点。其中一个字段用来描述该结点的特性(在目前假定下，只要

4、描述它是灰、白、黑三类结点中哪一类即可)，其余的八个字段用来作为存放指向其八个子结点的指针。这是最普遍使用的表示树形数据的存贮结构方式。 规则八叉树缺陷较多，最大的问题是指针占用了大量的空间。假定每个指针要用两个字节表示，而结点的描述用一个字节，那么存放指针要占总的存贮量的94。因此，这种方法虽然十分自然，容易掌握，但在存贮空间的使用率方面不很理想。2)2)线性八叉树线性八叉树 线性八叉树注重考虑如何提高空间利用率。用某一预先确定的次序遍历八叉树(例如以深度第一的方式)，将八叉树转换成一个线性表，表的每个元素与一个结点相对应。对于结点的描述可以丰富一点，例如用适当的方式来说明它是否为叶结点，如

5、果不是叶结点时还可用其八个子结点值的平均值作为非叶结点的值等等。这样，可以在内存中以紧凑的方式来表示线性表，可以不用指针或者仅用一个指针表示即可。线性八叉树特点：不仅节省存贮空间节省存贮空间，对某些运算也较为方便较为方便。但是为此付出的代价是丧失了一定的灵活性丧失了一定的灵活性。例如为了存取属于原图形右下角的子图形对应的结点，那么必须先遍历了其余七个子图形对应的所有结点后才能进行；不能方便地以其它遍历方式对树的结点进行存取，导致了许多与此相关的运算效率变低。因此尽管不少文章讨论了这种八叉树的应用，但是仍很难令人满意很难令人满意。 3)3)一对八式的八叉树一对八式的八叉树 一个非叶结点有八个子结

6、点，为了确定起见，将它们分别标记为0，1，2，3，4，5，6，7。从上面的介绍可以看到，如果一个记录与一个结点相对应，那么在这个记录中描述的是这个结点的八个子结点的特性值。而指针给出的则是该八个子结点所对应记录的存放处，而且还隐含地隐含地假定了这些子结点记录存放的次序记录存放的次序。也就是说，即使某个记录是不必要的(例如，该结点已是叶结点)，那么相应的存贮位置也必须空必须空闲在那里闲在那里，以保证不会错误地存取到其它同辈结点的记录。这样当然会有一定的浪费，除非它是完全的八叉树，即所有的叶结点均在同一层次出现，而在该层次之上的所有层中的结点均为非叶结点。2.BSP树(Binary Space P

7、artioning-Tree):BSP树是一种二叉树，它将空间逐级进行一分为二的划分。二叉树是一种十分重要的树型结构。它的特点是，树中的每个结点最多只有两棵子树，即树中任何结点的度数不得大于。二叉树的子树有左右之分，而且，子树的左右次序是重要的，即使在只有一棵子树的情况下，也应分清是左子树还是右子树。定义：二叉树是结点的有限集合，这个集合或是空的，或是由一个根结点和两棵互不相交的称之为左子树和右子树的二叉树组成。BSP树能很好地与空间数据库中空间对象的分布情况相适应，但对一般情况而言，BSP树深度较大，对各种操作均有不利影响。 二叉树的五种基本形态二叉树可以是空集；根可以有空的左子树或右子树；

8、或者左、右子树皆为空。 二叉树的五种基本形态如下图所示。 满二叉树、完全二叉树和不完全二叉树满二叉树(FullBinaryTree) 一棵深度为k且有2k-1个结点的二又树称为满二叉树。 特点：（1）每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。（2）满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。完全二叉树(Complete BinaryTree) 若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。 特点：（1）满二叉树是完全二叉树，完全二

9、叉树不一定是满二叉树。（2）在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。（3）在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。 非完全二叉树(Non-Complete BinaryTree)二叉树存储结构：顺序存储结构和链式存储结构。1)二叉树的顺序存储结构二叉树的顺序存储结构由一个一维数组构成，二叉树上的结点按某种次序分别存入该数组的各个单元。关键在于结点的存储次序，这种次序应能反映结点之间的逻辑关系（父子关系），否则二叉树的基本运算就难以实现。 该方法是把二叉树的所有结点按照一定的线性次序存储到一片连续的存储单元中。

10、结点在这个序列中的相互位置还能反映出结点之间的逻辑关系。完全二叉树结点编号完全二叉树结点编号（1） 编号办法 在一棵n个结点的完全二叉树中，从树根起，自上层到下层，每层从左至右，给所有结点编号，能得到一个反映整个二叉树结构的线性序列。 （2） 编号特点 完全二叉树中除最下面一层外，各层都充满了结点。每一层的结点个数恰好是上一层结点个数的2倍。从一个结点的编号就可推得其双亲，左、右孩子，兄弟等结点的编号。假设编号为i的结点是ki(1in)，则有：若i1，则ki的双亲编号为 ；若i=1，则Ki是根结点，无双亲。若2in，则Ki的左孩子的编号是2i；否则，Ki无左孩子，即Ki必定是叶子。因此完全二叉

11、树中编号 的结点必定是叶结点。若2i+1n，则Ki的右孩子的编号是2i+1；否则，Ki无右孩子。若i为奇数且不为1，则Ki的左兄弟的编号是i-1；否则，Ki无左兄弟。若i为偶数且小于n，则Ki的右兄弟的编号是i+1；否则，Ki无右兄弟。完全二叉树的顺序存储 将完全二叉树中所有结点按编号顺序依次存储在一个向量bt0.n中。 其中：bt1n用来存储结点 bt0不用或用来存储结点数目。【例】下表是前述图形所示的完全二叉树的顺序存储结构，bt0为结点数目，b7的双亲、左右孩子分别是bt3、btl4和bt15。 完全二叉树的存储结构一般二叉树的顺序存储 将一般二叉树添上一些 虚结点，成为完全二叉树 为了

12、用结点在向量中的相对位置来表示结点之间的逻辑关系，按完全二叉树形式给结点编号 将结点按编号存入向量对应分量，其中虚结点用表示优点和缺点 对完全二叉树而言，顺序存储结构既简单又节省存储空间。 一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。 最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点的存储空间。在对顺序存储的二叉树做插入和删除结点操作时，要大量移动结点。结点的结构 二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时，每个结点除了存储结点本身的数据外，还应设置两个指针域lchild和rchild，分别指向该结点的左孩子和右孩子。 2）二叉树的链式存储

13、结构二叉链表（二叉树的常用链式存储结构） 在一棵二叉树中，所有类型为BinTNode的结点，再加上一个指向开始结点(即根结点)的BinTree型头指针(即根指针)root，就构成了二叉树的链式存储结构，并将其称为二叉链表 【例】下面左图所示二叉树的二叉链表如下面中图所示。注意：注意： 一个二叉链表由根指针一个二叉链表由根指针root惟一确定。若二叉树为空，则惟一确定。若二叉树为空，则root=NULL；若结点的某个孩子不存在，则相应的指针为空。；若结点的某个孩子不存在，则相应的指针为空。 具有具有n个结点的二叉链表中，共有个结点的二叉链表中，共有2n个指针域。其中只有个指针域。其中只有n-1个

14、用来指个用来指示结点的左、右孩子，其余的示结点的左、右孩子，其余的n+1个指针域为空。个指针域为空。带双亲指针的二叉链表 经常要在二叉树中寻找某结点的双亲时，可在每个结点上再加一个指向其双亲的指针parent，形成一个带双亲指针的二叉链表。 【例】下面右图是左图所示的二叉树的带双亲指针的二叉链表。 注意：二叉树存储方法的选择，主要依赖于所要实施的各种运算的频度注意：二叉树存储方法的选择，主要依赖于所要实施的各种运算的频度 （二）构造性表示法(Constructive Solid Geometry)它是通过体素(如正方体、球体、三角体等)定义运算而得到新的形体的一种表示方法。最著名的构造性表示法

15、是构造实体几何(CSG)法。CSG的体素本身是实体，其运算为刚体运动或正则化的集合运算并、交、差。该法比较适用于机械、建筑等领域。 BAAABB(a)A,B形体的并(b)A,B形体的差(c)A,B形体的交图4-26 构造几何实体法生成三维实体刚体运动：三维空间中，把一个几何物体作旋转，平移，及镜像对称的运动，称之为刚体变换。刚体运动也可以理解为保持长度，角度，面积等不变的仿射变换，即保持内积和度量不变。正则化把非适定问题转化为适定问题的过程。（一个问题的解是存在的，惟一的和稳定的）（三）边界表示法：即三维G1S的矢量结构，一个形体用其拓扑边界表示。它记录形体的几何元素的几何信息(顶点、边、面、

16、体)以及相互连接关系(拓扑信息)，以便直接存取形体的各个体与面、面的边界线，以及各个顶点。这样有利于几实现以体、面、线、点为基础的各种几何运算和操作，以及查询形体的拓扑信息，例如实体中有哪几个相连通的部分等等。三维三维GISGIS矢量数据结构的拓扑关系矢量数据结构的拓扑关系:拓扑关系的建立使得各种空间的操作与信息查询易于实现。然而三维GIS中的三维拓扑关系建立是一个棘手的问题，因为所研究目标的结构极其复杂和不规则。从侧重于矿山实际应用的三维GIS研究出发，认为，复杂地物可用充满空间的各种体域、组成体域的曲面、构成曲面的边界环、组成环的弧、弧上的结点来描述。一般来说，体域是目标实体的基本构成；认

17、为任何复杂的实体都是由体域(自然的或人工的)构成的；体、面、线、点是一个动态的概念，在不同的比例尺或不同的研究重点时可以相互转换。例如对整个矿井来讲，巷道可认为是线域，而对某个工作面来讲，巷道则是体域。按上述思路和观点，考虑保持拓扑信息的完整性、易扩展性，提出用以下6组关系来描述矿山GIS三维矢量结构的空间拓扑关系。(1) 复杂地物体关系：复杂地物与组成它的体域。在该拓扑关系中加入对复杂地物属性的描述或指向属性记录文件的指针。(2) 体复杂地物曲面关系：体域与由其所构成的复杂地物，体域与包围该体域的曲面，以及与该体域相邻的体域。体拓扑结构中可加入对体域属性的描述。(3) 曲面环体域关系：曲面与

18、组成曲面的环以及该曲面所包围的体域(正面邻体)和包围该曲面的外部体域(负面邻体)。一个曲面可能由若干个环构成，其外环取正，内环取负值。在曲面拓扑结构中加上若干值样条弧（如等高弧）或插值函数，就可确定该曲面的空间形态。(4) 环弧曲面关系：环与构成该环的弧以及该环所包围的内部曲面(内邻曲面)和包围该环的外部曲面（外邻曲面）。(5) 弧结点环的关系：弧与该弧的起结点、终点及包含该弧的环。环有正负之分，环方向与弧的方向一致时，取正号；反之取负。在弧拓扑结构中加一系列坐标串，可确定该弧的形态。(6) 结点弧的关系：结点及从该结点出发的离开弧段和以该结点为终点的到达弧段。三维三维GISGIS矢量数据结构

19、拓扑关系的建立矢量数据结构拓扑关系的建立如下图所示为一典型的矿山现象。其物理意义如下：煤层上覆岩层为页岩（V1），中间为煤层（V2），煤层底板为砂岩（V3）。在煤层中赋存着一层很薄的夹矸（用1，2，3，4点连线的V5所示）。在底板砂岩中开拓了一条运输集中巷（V4）。另外，还探测到在煤层某处有一瓦斯集聚点（V6）。表1复杂地物体拓扑如需要详细描述复杂地物的属性，则用属性记录文件的方式加以记录，用指针来穿引。复杂地物组成的体域属性/指向记录文件的指针VV1某运输集中巷及其围岩状况V2V3V4V5V6表2体复杂地物曲面拓扑体域由体域组成的复杂地物构成体域的曲面邻体属性V V1 1V VEFKIEFK

20、I，FGMKFGMK，GHOMGHOM，HEIOHEIO，EHGFEHGF，IKMOIKMOV V2 2页岩页岩V V2 2IKLJIKLJ，KMNLKMNL，MOPNMOPN，OIJPOIJP，-IKMO-IKMO，JLNPJLNPV V1 1，V V3 3煤层煤层V V3 3JLBAJLBA，LNCBLNCB，NPDCNPDC，PJADPJAD，-JLNP-JLNP，ABCDABCD，-QTSR-QTSR，-TUXS-TUXS，-QVUT-QVUT，-QRWV-QRWV，-RSXW-RSXW，-UVWX-UVWXV V2 2，V V4 4砂岩砂岩V V4 4QTSRQTSR，TUXSTUXS，QVXUTQVXUT，QRWVQRWV，RSXWRSXW，UVWUVWV V3 3运输集运输集中巷中巷V V5 512341234V V2 2夹矸夹矸V V6 65 5V V2 2瓦斯聚瓦斯聚集点集点曲面以指向所包围的体域方向为正，远离所包围的体域为负(右手法则)。 表3曲面环体域关系拓扑曲面组成曲面的环正面相邻体负面相邻体值样条弧/插值函数EFKIEFKIEFKIEFKIV V1 1域外域外/ /IKMOIKMOIKMOIKMOV V1 1V V2 2JLBAJLBAJLBAJLBA-QTSR-QTSRV V3 3域外域外/ /QTSRQTSRQTSRQTSRV V4