没有合适的资源?快使用搜索试试~ 我知道了~
八叉树三维数据结构及示例程序文件.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 18 浏览量
2021-10-12
10:22:23
上传
评论
收藏 134KB DOC 举报
温馨提示
试读
24页
八叉树三维数据结构及示例程序文件.doc
资源推荐
资源详情
资源评论
. . . .
八叉树三维数据结构
〔一〕根本原理
用八叉树来表示三维形体,并研究在这种表示下的各种操作与应用是在进入 80 年代后
才比拟全面地开展起来的。这种方法,既可以看成是四叉树方法在三维空间的推广,也可
以认为是用三维体素阵列表示形体方法的一种改良。
八叉树的逻辑结构如下:
假设要表示的形体 V 可以放在一个充分大的正方体 C,C 的边长为 2 n ,形体 V C ,它
的八叉树可以用以下的递归方法来定义:
八叉树的每个节点与 C 的一个子立方体对应,树根与 C 本身相对应,如果 V=C,那么
V 的八叉树仅有树根,如果 V≠C,那么将 C 等分为八个子立方体,每个子立方体与树根的
一个子节点相对应。只要某个子立方体不是完全空白或完全为 V 所占据,就要被八等分
〔图 2-5-1〕,从而对应的节点也就有了八个子节点。这样的递归判断、分割一直要进展
到节点所对应的立方体或是完全空白,或是完全为 V 占据,或是其大小已是预先定义的体
素大小,并且对它与 V 之交作一定的“舍入〞,使体素或认为是空白的,或认为是 V 占据的。
如此所生成的八叉树上的节点可分为三类:
灰节点,它对应的立方体局部地为 V 所占据;
白节点,它所对应的立方体中无 V 的容;
黑节点,它所对应的立方体全为 V 所占据。
后两类又称为叶结点。形体 V 关于 C 的八叉树的逻辑结构是这样的:它是一颗树,其上
的节点要么是叶节点,要么就是有八个子节点的灰节点。根节点与 C 相对应,其它节点与
C 的某个子立方体相对应。
因为八叉树的结构与四叉树的结构是如此的相似,所以八叉树的存贮结构方式可以完全
沿用四叉树的有关方法。因而,根据不同的存贮方式,八叉树也可以分别称为常规的、线
性的、一对八的八叉树等等。
另外,由于这种方法充分利用了形体在空上的相关性,因此,一般来说,它所占用的存
贮空间要比三维体素阵列的少。但是实际上它还是使用了相当多的存贮,这并不是八叉树
的主要优点。这一方法的主要优点在于可以非常方便地实现有广泛用途的集合运算(例如可
以求两个物体的并、交、差等运算),而这些恰是其它表示方法比拟难以处理或者需要消耗
许多计算资源的地方。不仅如此,由于这种方法的有序性与分层性,因而对显示精度和速
度的平衡、隐线和隐面的消除等,带来了很大的方便,特别有用。
〔二〕八叉树的存贮结构
八叉树有三种不同的存贮结构,分别是规那么方式、线性方式以与一对八方式。相应的
八叉树也分别称为规那么八叉树、线性八叉树以与一对八式八叉树。不同的存贮结构的空
间利用率与运算操作的方便性是不同的。分析说明,一对八式八叉树优点更多一些。
1、规那么八叉树
规那么八叉树的存贮结构用一个有九个字段的记录来表示树中的每个结点。其中一个字
段用来描述该结点的特性(在目前假定下,只要描述它是灰、白、黑三类结点中哪一类即
可),其余的八个字段用来作为存放指向其八个子结点的指针。这是最普遍使用的表示树形
数据的存贮结构方式。
规那么八叉树缺陷较多,最大的问题是指针占用了大量的空间。假定每个指针要用两个
字节表示,而结点的描述用一个字节,那么存放指针要占总的存贮量的 94%。因此,这种
方法虽然十分自然,容易掌握,但在存贮空间的使用率方面不很理想。
1 / 24
. . . .
2、线性八叉树
线性八叉树注重考虑如何提高空间利用率。用某一预先确定的次序遍历八叉树(例如以
深度第一的方式),将八叉树转换成一个线性表〔图 2-5-2〕,表的每个元素与一个结点相
对应。对于结点的描述可以丰富一点,例如用适当的方式来说明它是否为叶结点,如果不
是叶结点时还可用其八个子结点值的平均值作为非叶结点的值等等。这样,可以在存中以
紧凑的方式来表示线性表,可以不用指针或者仅用一个指针表示即可。
线性八叉树不仅节省存贮空间,对某些运算也较为方便。但是为此付出的代价是丧失了
一定的灵活性。例如为了存取属于原图形右下角的子图形对应的结点,那么必须先遍历了
其余七个子图形对应的所有结点后才能进展;不能方便地以其它遍历方式对树的结点进展
存取,导致了许多与此相关的运算效率变低。因此尽管不少文章讨论了这种八叉树的应用,
但是仍很难令人满意。
3、一对八式的八叉树
一个非叶结点有八个子结点,为了确定起见,将它们分别标记为
0,1,2,3,4,5,6,7。从上面的介绍可以看到,如果一个记录与一个结点相对应,
那么在这个记录中描述的是这个结点的八个子结点的特性值。而指针给出的那么是该八个
子结点所对应记录的存放处,而且还隐含地假定了这些子结点记录存放的次序。也就是说,
即使某个记录是不必要的(例如,该结点已是叶结点),那么相应的存贮位置也必须空闲在
那里〔图 2-5-3〕,以保证不会错误地存取到其它同辈结点的记录。这样当然会有一定的
浪费,除非它是完全的八叉树,即所有的叶结点均在同一层次出现,而在该层次之上的所
有层中的结点均为非叶结点。
为了克制这种缺陷,有两条途径可以采纳。一是增加计算量,在记录中增加一定的信息,
使计算工作适当减少或者更方便。
栅格数据压缩存储方式之四叉树、八叉树编码
四叉树编码(quad-tree code)
四又树结构的根本思想是将一幅栅格地图或图像等分为四局部。逐块检查其格网属性
值(或灰度)。如果某个子区的所有格网值都具有一样的值。那么这个子区就不再继续分割,
2 / 24
. . . .
否那么还要把这个子区再分割成四个子区。这样依次地分割,直到每个子块都只含有一样
的属性值或灰度为止。
四叉树编码法有许多有趣的优点:①容易而有效地计算多边形的数量特征;②阵列各
局部的分辨率是可变的,边界复杂局部四叉树较高即分级多,分辨率也高,而不需表示许
多细节的局部那么分级少,分辨率低,因而既可准确表示图形结构又可减少存贮量;②栅
格到四叉树与四叉树到简单栅格结构的转换比其它压缩方法容易;④多边形中嵌套异类小
多边形的表示较方便。
四叉树编码的最大缺点是转换的不定性,用同一形状和大小的多边形可能得出多种不
同的四叉树结构,故不利于形状分析和模式识别。但因它允许多边形中嵌套多边形即所谓
“洞〞这种结构存在,使越来越多的地理信息系统工作者都对四叉树结构很感兴趣。上述这
些压缩数据的方法应视图形的复杂情况合理选用,同时应在系统中备有相应的程序。另外,
用户的分析目的和分析方法也决定着压缩方法的选取。
四叉树结构按其编码的方法不同又分为常规四叉树和线性四叉树。常规四叉树除了记
录叶结点之外,还要记录中间结点。结点之间借助指针联系,每个结点需要用六个量表达:
四个叶结点指针,一个父结点指针和一个结点的属性或灰度值。这些指针不仅增加了数据
贮存量,而且增加了操作的复杂性。常规四叉树主要在数据索引和图幅索引等方面应用。
线性四叉树那么只存贮最后叶结点的信息。包括叶结点的位置、深度和本结点的属性
或灰度值。所谓深度是指处于四叉树的第几层上。由深度可推知子区的大小。
线性四叉树叶结点的编号需要遵循一定的规那么,这种编号称为地址码,它隐含了
叶结点的位置和深度信息。最常用的地址码是四进制或十进制的 Morton 码。
————————————————————————————————————
————————
八叉树结构就是将空间区域不断地分解为八个同样大小的子区域(即将一个六面的立方
体再分解为八个一样大小的小立方体),分解的次数越多,子区域就越小,一直到同—区域
的属性单一为止。按从下而上合并的方式来说,就是将研究区空间先按—定的分辨率将三
维空间划分为三维栅格网,然后按规定的顺序每次比拟 3 个相邻的栅格单元,如果其属性
值一样那么合并,否那么就记盘。依次递归运算,直到每个子区域均为单值为止。
八叉树同样可分为常规八叉树和线性八叉树。常规八叉树的结点要记录十个位,即八
个指向子结点的指针,—个指向父结点的指针和一个属性值(或标识号)。而线性八叉树那
么只需要记录叶结点的地址码和属性值。因此,它的主要优点是,其一节省存储空间,因
为只需对叶结点编码,节省了大量中间结点的存储。每个结点的指针也免除了,而从根到
某一特定结点的方向和路径的信息隐含在定位码之中,定位码数字的个位数显示分辨率的
上下或分解程度;其次,线性八叉树可直接寻址,通过其坐标值那么能计算出任何输入结
点的定位码(称编码),而不必实际建立八叉树,并且定位码本身就是坐标的另—种形式,
3 / 24
. . . .
不必有意去存储坐标值。假设需要的话还能从定位码中获取其坐标值(称解码);其三,在
操作方面,所产生的定位码容易存储和执行,容易实现象集合、相加等组合操作。
八叉树主要用来解决地理信息系统中的三维问题。
#include "stdafx.h"
#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "octree.h"
/* ------------------------------------------------------------------------ */
/* ------------------------------------------------------------------------ */
Vec3 makeVec3( double x, double y, double z)
{
Vec3 v3 = (Vec3) malloc(3 * sizeof(double));
v3[0] = x; v3[1] = y; v3[2] = z;
return v3;
}
Vec3 copyVec3( Vec3 src )
{
Vec3 v3 = (Vec3) malloc(3 * sizeof(double));
v3[0] = src[0]; v3[1] = src[1]; v3[2] = src[2];
return v3;
}
/* ------------------------------------------------------------------------ */
Octree* make_octree( Vec3 min, Vec3 max )
{
//Octree* o = (Octree*) malloc(sizeof(Octree));
Octree* o = new Octree;
o->min = copyVec3(min);
o->max = copyVec3(max);
o->children = 0;
o->at_max_depth = 0;
/*
printf("creating octree %.3lf,%.3lf,%.3lf ... %.3lf,%.3lf,%.3lf\n",
o->min[2], o->min[1], o->min[0],
4 / 24
. . . .
o->max[2], o->max[1], o->max[0] );
*/
return o;
}
void subpoint( Octree* o,int oc,Vec3 min, Vec3 max)
{
pvex_nor *m_p1,*m_p2;
POSITION pos1,pos2;
for(pos1=o->vex.GetHeadPosition(),pos2=o->normal.GetHeadPosition();pos1!=NULL;)
{
//pos1=o->vex.FindIndex(i);//pos2=o->normal.FindIndex(i);
m_p1=(pvex_nor*)o->vex.GetNext(pos1);m_p2=(pvex_nor*)o-
>normal.GetNext(pos2);
if((m_p1->x>min[0]&&m_p1->x<max[0])&&(m_p1->y>min[1]&&m_p1->y<max[1])
&&(m_p1->z>min[2]&&m_p1->z<max[2]))
{
o->children[oc]->vex.AddHead(new pvex_nor(m_p1->x,m_p1->y,m_p1->z));
o->children[oc]->normal.AddHead(new pvex_nor(m_p2->x,m_p2->y,m_p2->z));
}
}
}
void split_octree( Octree* o )
{
double oc_min[3];
double oc_max[3];
Vec3 mid = makeVec3( (o->min[0] + o->max[0]) * 0.5,
(o->min[1] + o->max[1]) * 0.5,
(o->min[2] + o->max[2]) * 0.5 );
int xp, yp, zp;
int oc = 0;
//o->children = (Octree**) malloc( 8 * sizeof(Octree*));
o->children = new Octree*;
for(zp=0; zp < 2; zp++)
{
if(zp == 0)
{
oc_min[2] = o->min[2];
oc_max[2] = mid[2];
}
5 / 24
剩余23页未读,继续阅读
资源评论
yunxidzh
- 粉丝: 59
- 资源: 30万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功