(1)三维和四维数据结构的提出。前面介绍的数据结构都是二维的,然而在有些信息系统中,需要有真三维的空间数据结构。例如矿山开采中的地下资源埋藏和采矿巷道的空间分布,如果用二维的坐标体系就根本无法很好表达。此外,矿山空间目标往往随时间不断变化着,这就提出了空间和时间信息系统的问题。 |
在时间信息系统中不考虑时间,是把时间看作不变的常数,即为当前的时间。而在时间和空间信息系统中,则把时间看作有过去、现在和将来的可变值。这种系统中,空间和时间是不可分割的信息,并起着同样重要的作用。 |
我们首先用三维来定义空间目标,在同一坐标系统下,用四维数据来定义时间和空间数据。根据这种方案,任何目标都可以由其坐标对({s} ,t)惟一确定。这里{s} ={x,y,z}定义空间数据,而t定义时间数据。对每一个三维坐标数据(x,y,z),必定有而且仅有一个时间t值与之相对应,但反之则不然。 |
为了表示三维数据和四维数据,较好的数据结构方式是在四叉树基础上发展起来的大义树和十六叉树结构。 |
(2)八叉树结构及其编码。八叉树结构是从四叉树结构直接发展而来的,其原理就是将空间区域不断地分解为八个同样大小的子区域(即将一个六面的立方体再分解为八个相同大小的小立方体),分解的次数越多,子区域就越小,一直到同一区域的属性单一为止。按从下而上合并的方式来说,就是将研究区空间先按一定的分辨率将三维空间划分为三维栅格网,然后按规定的顺序每次比较8个相邻的栅格单元,如果其属性值相同则合并,否则就记盘。 |
依次递归运算,直到每个子区域均为单值为止。 |
八叉树同样可分为常规八叉树和线性八叉树。常规八叉树的结点要记录十个值,即八个指向子结点的指针,一个指向父结点的指针和一个属性值(或标识号)。而线性八叉树则只需要记录叶结点的地址码和属性值。因此,它的主要优点是,一是节省存储空间,因为只需对叶结点编码,节省了大量中间结点的存储。每个结点的指针也免除了,而从根到某一特定结点的方向和路径的信息隐含在定位码之中,定位码数字的个位数显示分辨率的高低或分解程度;其次,线性八叉树可直接寻址,通过其坐标值则能计算出任何输入结点的定位码(称编码),而不必实际建立八叉树,并且定位码本身就是坐标的另一种形式,不必有意去存储坐标值。若需要的话还能从定位码中获取其坐标值(称解码);第三,在操作方面,所产生的定位码容易存储和执行,容易实现集合、相加等组合操作;此外,如果应用任务很大致使在核心存储器中不能容纳所有定位码时,也可以将定位码安排在B树中,以便划分成许多页面,并存储在外围设备中。 |
|
图2-29表示一种线性八叉树的生成。通过对八叉树及其编码方案的分析研究,可总结出下列一些自动计算定位码的有用规则: |
①给定分辨率n,也即确定了坐标系统的大小。每个坐标轴的取值范围从0到。在图2-29中的分辨率等于3,则三个坐标轴的坐标范围为从0到7。 |
②每个八叉树点的编码采用的形式如图2_30所示。每个位置上的qi是(0,1,2,…,7)八个数之一,qi的个数取决于分辨率n。在本例中定位码以三个八进制数表示。 |
③对整个编码按Z字形的方式进行,其方向取决于如何选择第一、二、三和第四维坐标。 |
|
基于第一个规则,坐标(X,Y,Z)已知的八叉树点的编码可用下式表示: |
|
式中:系数ci、di和ei(i=0, …,n-2,n-l)的取值为0或1,可通过比较方程式两边的值来确定。 |
根据第二、三规则的观点,qi值可由下式确定:
(2-1)
取n=3,(X,Y,Z)=(6,3,1)为例,则八叉树编码的表达式为
因此
qi的值为
因此,按给定的八义树节点所产生的定位码为136。 |
线性八叉树的地址码有八进制和十进制数两种。十进制地址码亦称Morton码。由于Morton码是自然数码,所以可以将二维数组转化成以Morton码为下标的一维数组。线性八叉树的自然数编码的表达式为
(2-3)
式中:c0,d1,cn-1,d0,dn-1和e0,e1,en-1分别是行号和列号二进制化后由低位到高位的权。 |
当图形、图像恢复时,可由N码经逆变换为下列十进制的行、列号: |
|
其中
当k<n-l时;
当k=n-l时,。 |
|
其中
当k<n-l时,;
当k=n-l时,。 |
|
其中
当k<n-l时,;
当k=n-l时,。 |
(3)线性叉树的自然数编码及其收敛性分析。基于线性四叉树和线性八叉树的数据结构,可以推想,对于一个四维的时空目标也可以用线性十六叉树来表示。因此推求线性2m叉树的自然数编码的通式,不仅有理论意义,还便于指导实际应用。 |
根据以上的推导,可以得到线性叉树自然数编码的一般公式为 |
|
其中
式中:m为研究目标的维数;
Iik是m维欧氏空间中第i个坐标轴的十进制坐标。 |
我们知道图像分辨率n决定了栅格坐标大小,在式(2_7)中给出了二进制化的最大取余迭代次数就是图像分辨率大小。而在同一图像分辨率下,m维欧氏空间中不同的坐标取余迭代收敛次数为 |
|
表明取余迭代速度是由坐标Ii0决定的,因此线性叉树自然数编码的实用公式为
其中
m维图像恢复时,进行逆变换:
其中
当k<n-1 时,;
当k=n-1时,NK=N0。 |
同样,为了提高逆变换式(2-10)取余迭代收敛速度,应选确定k的取余迭代初始值,即满足条件 |
|
|
因此实用时,式(2-10)中k的初值用式(2-12)取代。 |
利用式(2-10)和式(2-12)进行图像恢复的逆变换时,取余迭代是否在k=0处收敛呢?很明显要满足
MOD(Tk,2)≡0 (2-13)
恒成立,于是有mk+i-l≤-l。即 |
|
只有当i=m时,k≤-l。因此在取余迭代式(2-10)中,Ii值一定会在k=0处收敛。作为上述公式应用的一个例子,图2-31为由一维时间和三维空间复合形成的四维时空数据结构的线性十六叉树自然数编码图。 |
按上述公式可将四维时空坐标系中每个超体素的时空位置转换为线性24叉树自然数编码,如位于(1,3,0,1)处的超体素的编码N=43。这样十进制的自然数编码N自然地对应一维数组下标,四维图像超体素合并运算时,依次将数组中24个相邻元素进行合并操作。四维图像恢复时,利用上述逆变换为4个坐标值。 |
线性十六叉树构成的数学模型可扩展如下: |
(1) 任何十六叉树的坐标可用下式表示: |
|
|
(2) 定位码的十六位数字qi为
|
举例来说,空间和时间坐标为(X,Y,Z,T)=(3,1,2,1),则利用上面的公式得到地址码为5B,即如图2-31中后面那个立方体中灰色立方单元。而前面那个灰色单元的坐标为(2,1,0,0),它的地址码为12。 |
相关推荐
3d场景八叉树优化算法,可以解决卡顿
八叉树模型是计算机科学中常用的一种非线性数据结构。它在 工程中有广泛的应用。笔者选用柱形坐标空间作为八叉树模型的根结点,提出了 一个由三维实体的CSG 模型按递归方式生成实体八叉树模型的算法,找出了八叉 树...
本文在对目前线性四叉树、八叉树邻域寻找算法进行分析的基础上,通过分析这两种数据结构编码的特性(方向性、层次性、可压缩性及大小性),提出了一种直接利用象元和3D栅格的编码求其邻域的新算法。这种算法在求相同...
#资源达人分享计划#
八叉树的三维行程编码 paper 八叉树结构是 3D GIS中一种研究和应用最为广泛的栅格数据结构。在对线性八叉树编码方法进行 分析的基础上 ,将行程编码技术引入八叉树的数据压缩 ,形成三维行程编码方法。 并对三维行程...
算法使用八叉树结构生成三维模型的高度场表示,将传统的z向高度场扩展到x,y,z三个方向的高度场。首先,提出了三角面片预处理方法,保证模型精度和数据的完整性;其次,提出了基于投影变换的高度场表示判断及栅格化...
RegionTrees.jl:四叉树,八叉树及其N维表兄弟 这个Julia包是用于定义N维区域树的轻量级框架。 在2D中,这些称为区域四叉树,而在3D中,它们通常称为octree 。 区域树是一种简单的数据结构,用于描述具有不同分辨率...
稀疏八度 一种基于指针的稀疏八叉树数据结构。 有关线性实现,请参见 。 ··安装该库需要对等依赖关系 。 npm install math-ds sparse-octree用法点数import { Vector3 } from "math-ds" ;import { PointOctree } ...
3D 中的八叉树点分解OcTree 用于创建包含 3D 的 bin 的树数据结构点。 每个 bin 可以递归地分解为 8 个子 bin。http://en.wikipedia.org/wiki/Octree OT = OcTree(PTS) 从一个 N×3 的点矩阵创建一个八叉树坐标。 ...
网格的多分辨率层次结构存储为不重叠的固定大小网格的复合结构,这些结构作为叶子存储在四叉树或八叉树的森林中。 基于高度可扩展的网格划分库p4est() 提供了针对双曲线PDE的求解器,包括Clawpack 4.x,Clawpack ...
分析了线性四叉树、线性八叉树两种数据结构的特点,介绍了一种基于十进制的线性八叉树编码技术。针对矿山GIS中空间三维目标与二维目标叠置分析存在的问题,提出了一种基于四叉树的线性八叉树的数据结构。试验表明,这种...
八叉树是一种特别适合3D点云分区的数据结构。 八叉树于1980年在Donald Meagher中引入,是许多图形引擎和渲染系统的基础。 它在图像处理,碰撞检测,颜色量化,视锥体平视和其他许多空间计算中很有用。 类似于2D四叉...
空间剖分是构造快速空间查找数据结构的有效方法,四叉树、八叉树、Kd-树是典型的基于空间剖分思想的树形空间查找结构。选择合适的参数来构造实际点集数据的树形查找结构,对提高相关算法的效率具有重要意义。在分析...
四叉树是一种树数据结构,其中每个内部节点恰好具有四个子节点。 四叉树是八叉树的二维模拟,最常用于通过将二维空间递归细分为四个象限或区域来划分二维空间。 演示版 在GitHub页面上查看演示: :
为了提高三角网格模型简化的速度,满足实时显示的要求,并且有效地...采用八叉树结构自适应地分割网格模型空间,同时在各个区域中采用近似曲率的边折叠算法并行地进行边折叠操作。实验证明,该算法取得了不错的效果。
基于中心有限体积方法和双时间推进算法,对民机起飞和着陆构型的绕流流场进行了Euler方程数值模拟,分析了应角八叉树和全叉树数据结构时的区别,计算结果与实验数据的对比,说明所述方法的正确性。
它在分区空间的维度上是通用的,因此支持二叉树,四叉树,八叉树等。预期目标是在不牺牲抽象性的前提下,以最快的速度实现这些功能并覆盖尽可能多的用例。 该项目的当前状态还处于试验阶段。 它可以正常工作并且...
DS 数据结构 在此存储库中,我将添加所有数据结构实现。它们大多数是用C编程语言实现的。 如果您知道北印度语,请访问我的YouTube频道,获取有关以下主题的教程: ...八叉树 四叉树 树 线性数据结构: 非线性数据结构:
3D Tiles规范的好处在于,它允许一种通用渲染实现来支持使用许多不同数据结构(例如,二叉树,四叉树或八叉树)进行平铺的数据集。 它还支持稀疏数据表示,因此它可以很好地适应具有可变详细密度的数据集。实施细节...