2025年八叉树和十六叉树结构

科技前沿 • 2025-03-05 11:55 • 阅读 56

大家好，我是讯享网，很高兴认识大家。

(1)三维和四维数据结构的提出。前面介绍的数据结构都是二维的，然而在有些信息系统中，需要有真三维的空间数据结构。例如矿山开采中的地下资源埋藏和采矿巷道的空间分布，如果用二维的坐标体系就根本无法很好表达。此外，矿山空间目标往往随时间不断变化着，这就提出了空间和时间信息系统的问题。

在时间信息系统中不考虑时间，是把时间看作不变的常数，即为当前的时间。而在时间和空间信息系统中，则把时间看作有过去、现在和将来的可变值。这种系统中，空间和时间是不可分割的信息，并起着同样重要的作用。

我们首先用三维来定义空间目标，在同一坐标系统下，用四维数据来定义时间和空间数据。根据这种方案，任何目标都可以由其坐标对（{s} ,t）惟一确定。这里{s} ={x,y,z}定义空间数据，而t定义时间数据。对每一个三维坐标数据(x，y，z),必定有而且仅有一个时间t值与之相对应，但反之则不然。

为了表示三维数据和四维数据，较好的数据结构方式是在四叉树基础上发展起来的大义树和十六叉树结构。

(2)八叉树结构及其编码。八叉树结构是从四叉树结构直接发展而来的，其原理就是将空间区域不断地分解为八个同样大小的子区域(即将一个六面的立方体再分解为八个相同大小的小立方体)，分解的次数越多，子区域就越小，一直到同一区域的属性单一为止。按从下而上合并的方式来说，就是将研究区空间先按一定的分辨率将三维空间划分为三维栅格网，然后按规定的顺序每次比较8个相邻的栅格单元，如果其属性值相同则合并，否则就记盘。

依次递归运算，直到每个子区域均为单值为止。

八叉树同样可分为常规八叉树和线性八叉树。常规八叉树的结点要记录十个值，即八个指向子结点的指针，一个指向父结点的指针和一个属性值(或标识号)。而线性八叉树则只需要记录叶结点的地址码和属性值。因此，它的主要优点是，一是节省存储空间，因为只需对叶结点编码，节省了大量中间结点的存储。每个结点的指针也免除了，而从根到某一特定结点的方向和路径的信息隐含在定位码之中，定位码数字的个位数显示分辨率的高低或分解程度;其次，线性八叉树可直接寻址，通过其坐标值则能计算出任何输入结点的定位码(称编码)，而不必实际建立八叉树，并且定位码本身就是坐标的另一种形式，不必有意去存储坐标值。若需要的话还能从定位码中获取其坐标值(称解码);第三，在操作方面，所产生的定位码容易存储和执行，容易实现集合、相加等组合操作;此外，如果应用任务很大致使在核心存储器中不能容纳所有定位码时，也可以将定位码安排在B树中，以便划分成许多页面，并存储在外围设备中。

讯享网

2025年八叉树和十六叉树结构

相关推荐