线性八叉树的一种最优构造算法--《计算机学报》1993年04期
线性八叉树的一种最优构造算法
【摘要】：本文提出线性八叉树的一种最优构造算法,本文对文献[3]中最优四叉树构造算法的某些思路作了推广及改进:采用了最大活动结点插入原则,免除了合并操作;算法只需进行与黑结点数成比例的插入操作。借助于一种新的图像数据结构——数字搜索树作为中间存储结构,有效地压缩了数据并加快了插入速度,因而本算法有较高的效率.
【作者单位】：
【关键词】：
【正文快照】：
1。砚!性叁.一J.‘二J八叉树是表达三维图像的一种重要方法,它在计算机图形学、计算机视觉、图像处理计算机学报1993年及景物分析等领域有着广泛的用途.为了压缩存储空间,[1]中提出了目前广泛应用的线性八叉树编码,使用这种图像表示方法的前提,是建立由初始三维数组转换为线
欢迎：、、)
支持CAJ、PDF文件格式，仅支持PDF格式
【引证文献】
中国期刊全文数据库
吴晓军,刘伟军,王天然;[J];工程图学学报;2005年04期
谈国新;[J];武汉城市建设学院学报;1994年02期
郑永果，潘久辉;[J];中南工业大学学报(自然科学版);1996年04期
中国硕士学位论文全文数据库
吴海明;[D];河北工业大学;2000年
【同被引文献】
中国期刊全文数据库
滕弘飞,孙守林,葛文海,杨永辉,娄汉文;[J];大连理工大学学报;1993年03期
覃中平,张焕国;[J];计算机学报;1992年03期
李庆华;[J];计算机学报;1992年08期
滕弘飞,刘义军,葛文海,孙大新,钟万勰;[J];计算机学报;1993年07期
黄文奇,李庆华,余向东;[J];应用数学学报;1986年04期
杜志江,孙立宁,富历新;[J];高技术通讯;2003年06期
陈传波,欧阳星明;[J];华中科技大学学报(自然科学版);1993年06期
【二级引证文献】
中国期刊全文数据库
吕广宪;潘懋;王占刚;兰向荣;;[J];地理与地理信息科学;2007年01期
毕林;王李管;荆永滨;;[J];湖南科技大学学报(自然科学版);2007年03期
陈慧,何兴恒,胡娟;[J];中国科技信息;2005年22期
中国博士学位论文全文数据库
柳伟;[D];上海交通大学;2008年
吕天阳;[D];吉林大学;2007年
李蔚清;[D];南京理工大学;2007年
权胜赫;[D];吉林大学;2007年
毛先成;[D];中南大学;2006年
中国硕士学位论文全文数据库
荆永滨;[D];中南大学;2007年
张淑焕;[D];西北工业大学;2006年
温春明;[D];西北工业大学;2006年
马强;[D];吉林大学;2007年
高涛;[D];哈尔滨工程大学;2003年
王忠;[D];浙江大学;2005年
【相似文献】
中国期刊全文数据库
许志明;[J];计算机工程;1987年03期
卢声凯,唐泽圣;[J];计算机辅助设计与图形学学报;1989年01期
张建民,卢振荣;[J];工程图学学报;1989年01期
丁文毅;[J];计算机工程;1990年02期
周洞汝,杨荣;[J];计算机辅助设计与图形学学报;1992年01期
周洞汝,姜海涛;[J];计算机辅助设计与图形学学报;1992年03期
周洞汝;[J];科学通报;1992年17期
周洞汝,杨荣;[J];计算机学报;1993年04期
周洞汝;[J];计算机学报;1994年04期
朱建飞，沈锦林，颜晖;[J];计算机工程与科学;1994年01期
中国硕士学位论文全文数据库
车敏;[D];西安理工大学;2006年
&快捷付款方式
&订购知网充值卡
400-819-9993
《中国学术期刊（光盘版）》电子杂志社有限公司
同方知网数字出版技术股份有限公司
地址：北京清华大学 84-48信箱 知识超市公司
出版物经营许可证 新出发京批字第直0595号
订购热线：400-819-82499
服务热线：010--
在线咨询：
传真：010-
京公网安备75号基于三维点云数据的线性八叉树编码压缩算法(权毓舒, 何明一,2005)_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
基于三维点云数据的线性八叉树编码压缩算法(权毓舒, 何明一,2005)
上传于||文档简介
&&介​绍​三​维​G​I​S​应​用​中​,​八​叉​树​原​理​、​创​建​、​优​化​的​相​关​文​章
阅读已结束，如果下载本文需要使用0下载券
想免费下载更多文档？
定制HR最喜欢的简历
你可能喜欢一种基于自然数线性八叉树的优化构造算法--《武汉城市建设学院学报》1994年02期
一种基于自然数线性八叉树的优化构造算法
【摘要】：本文提出了一种基于自然数线性八叉树的优化构造算法。该算法以活动结点表为中间辅助结构，在图像输入过程中直接生成基于Ｎ码的八叉树叶结点．与常规构造算法相比，新提出的优化构造算法省去了Ｎ码的计算及合并过程，从而具有较高的时空效率．
【关键词】：
【分类号】：TP311.12【正文快照】：
一种基于自然数线性八叉树的优化构造算法谈国新（城市建设与管理系）摘要本文提出了一种基于自然数线性八叉树的优化构造算法。该算法以活动结点表为中间辅助结构，在图像输入过程中直接生成基于Ｎ码的八叉树叶结点．与常规构造算法相比，新提出的优化构造算法省去了Ｎ码的
欢迎：、、)
支持CAJ、PDF文件格式，仅支持PDF格式
【引证文献】
中国博士学位论文全文数据库
毛先成;[D];中南大学;2006年
中国硕士学位论文全文数据库
高涛;[D];哈尔滨工程大学;2003年
周胜;[D];中南大学;2009年
【参考文献】
中国期刊全文数据库
龚健雅;[J];测绘学报;1992年02期
周洞汝,杨荣;[J];计算机学报;1993年04期
【共引文献】
中国期刊全文数据库
唐宏,盛业华;[J];北京测绘;1999年03期
刘刚;周炳俊;安铭刚;杨国辉;;[J];北京测绘;2007年04期
彭仪普,刘文熙;[J];测绘工程;2002年03期
侯妙乐;朱光;王前卫;杜明义;;[J];测绘科学;2009年06期
王春;陶旸;贾敦新;朱雪坚;;[J];地理信息世界;2008年01期
葛咏,潘正风;[J];测绘通报;2000年05期
王小军;[J];测绘通报;2000年05期
眭海刚,朱庆;[J];测绘通报;2001年04期
秦其明,袁胜元;[J];测绘通报;2001年S1期
李鲁群,赫建忠,林宗坚;[J];测绘通报;2002年06期
中国重要会议论文全文数据库
陶旸;;[A];中国地理信息系统协会第四次会员代表大会暨第十一届年会论文集[C];2007年
郭加树;刘展;;[A];中国地球物理学会第二十三届年会论文集[C];2007年
中国博士学位论文全文数据库
张山山;[D];西南交通大学;2001年
罗德安;[D];西南交通大学;2001年
王宇翔;[D];中国科学院研究生院（遥感应用研究所）;2002年
张锦;[D];中国科学院研究生院（测量与地球物理研究所）;2002年
王盼成;[D];中国科学院研究生院（遥感应用研究所）;2004年
崔巍;[D];武汉大学;2004年
赵杰;[D];武汉大学;2004年
赵村民;[D];中国地质大学（北京）;2005年
程朋根;[D];武汉大学;2005年
何勇;[D];武汉大学;2004年
中国硕士学位论文全文数据库
吴海明;[D];河北工业大学;2000年
张轶;[D];解放军信息工程大学;2001年
陈镇虎;[D];北京工业大学;2002年
夏启兵;[D];中国人民解放军信息工程大学;2002年
赵金萍;[D];解放军信息工程大学;2004年
杨金侠;[D];西北大学;2005年
廖云;[D];中国人民解放军信息工程大学;2005年
杨成月;[D];武汉大学;2004年
汪诗峰;[D];中国科学院研究生院（遥感应用研究所）;2006年
覃永宁;[D];浙江大学;2006年
【同被引文献】
中国期刊全文数据库
,范继璋;[J];长春地质学院学报;1989年03期
李景朝,王世称,杨毅恒;[J];吉林大学学报(地球科学版);2002年04期
赵震宇,王世称,孟令顺,杨毅恒,高怀雄,王敬凯,董王仓,侯满堂;[J];吉林大学学报(地球科学版);2004年02期
郑坤;刘修国;吴信才;杨慧;;[J];吉林大学学报(地球科学版);2006年03期
申维;[J];长春地质学院学报;1997年01期
余生晨，王世称，刘洪;[J];长春地质学院学报;1997年02期
阳正熙;[J];成都理工学院学报;2000年S1期
张寿庭,赵鹏大,陈建平,徐旃章;[J];成都理工大学学报(自然科学版);2003年05期
夏庆霖,张寿庭,赵鹏大,金友渔;[J];成都理工大学学报(自然科学版);2003年05期
赵鹏大,张寿庭,陈建平;[J];成都理工大学学报(自然科学版);2004年02期
中国博士学位论文全文数据库
王润怀;[D];西南交通大学;2007年
中国硕士学位论文全文数据库
邓浩;[D];中南大学;2008年
【二级引证文献】
中国期刊全文数据库
毛先成;华萍;陈振;;[J];地质找矿论丛;2008年04期
施龙青;翟培合;魏久传;朱鲁;韩进;尹会永;于小鸽;;[J];地球物理学进展;2009年02期
邓金灿;甘文志;;[J];矿产与地质;2009年03期
刘文玉;吴湘滨;张宝一;黄亚;刘珊;侯东壮;;[J];科技导报;2011年11期
施龙青;翟培合;魏久传;朱鲁;韩进;尹会永;;[J];山东科技大学学报(自然科学版);2008年06期
梁锦;;[J];中山大学研究生学刊(自然科学.医学版);2011年02期
赵百轶;张利军;贾鹤鸣;;[J];应用科技;2011年10期
中国重要会议论文全文数据库
李国山;;[A];2010'中国矿业科技大会论文集[C];2010年
中国博士学位论文全文数据库
张建东;[D];中南大学;2007年
韩进;[D];上海大学;2008年
徐翠玲;[D];长安大学;2007年
张东风;[D];中南大学;2010年
谭正华;[D];中南大学;2010年
中国硕士学位论文全文数据库
王兴博;[D];华北电力大学（北京）;2006年
鲁燕;[D];哈尔滨工程大学;2006年
毛宇峰;[D];哈尔滨工程大学;2006年
管乐乐;[D];哈尔滨工程大学;2007年
王磊;[D];哈尔滨工程大学;2007年
陈永军;[D];哈尔滨工程大学;2007年
刘梅华;[D];中南大学;2007年
黄艳丽;[D];昆明理工大学;2008年
王萍;[D];中南大学;2008年
陈振;[D];中南大学;2008年
【相似文献】
中国期刊全文数据库
周洞汝,杨荣;[J];计算机学报;1993年04期
朱建飞，沈锦林，颜晖;[J];计算机工程与科学;1994年01期
谈国新，林宗坚;[J];测绘学报;1995年03期
马文华;[J];西南民族学院学报(自然科学版);1996年03期
许志明;[J];计算机工程;1987年03期
马文华;[J];宁夏工学院学报;1996年02期
丁文毅;[J];计算机工程;1990年02期
周洞汝,杨荣;[J];计算机辅助设计与图形学学报;1992年01期
马智民,陈浩,王金玲;[J];西安工程学院学报;1999年S1期
余慧,张曙光,刘英,李国亚;[J];计算机工程;2004年06期
中国重要报纸全文数据库
杨明;[N];西藏日报;2003年
陈赜宇;[N];电子报;2001年
湖水;[N];中国电子报;2002年
郝煜 赵磊（实习生）;[N];中国计算机报;2002年
龙期超;[N];电子报;2000年
寒武;[N];电脑报;2003年
中南大学 中石化巴陵分公司 董纯坚 邹琳翔;[N];计算机世界;2004年
侍晓宁 潘海浪;[N];中国国门时报;2003年
;[N];通信产业报;2004年
凯力;[N];中国计算机报;2002年
中国硕士学位论文全文数据库
邓浩;[D];中南大学;2008年
车敏;[D];西安理工大学;2006年
唐婧;[D];中南大学;2010年
许秀明;[D];南京邮电大学;2012年
&快捷付款方式
&订购知网充值卡
400-819-9993
《中国学术期刊（光盘版）》电子杂志社有限公司
同方知网数字出版技术股份有限公司
地址：北京清华大学 84-48信箱 知识超市公司
出版物经营许可证 新出发京批字第直0595号
订购热线：400-819-82499
服务热线：010--
在线咨询：
传真：010-
京公网安备75号散乱点云线性八叉树结构在GPU中的实现--《机械设计与制造工程》2013年04期
散乱点云线性八叉树结构在GPU中的实现
【摘要】：为快速建立散乱点云的空间邻接关系,研究了更快速构建线性八叉树。采用Morton码描述八叉树的节点,并按照层次顺序对叶节点进行遍历,通过建立两个查询表,实现对节点相邻信息的快速查询。算法利用了GPU架构的并行度,实验表明,该算法有较高的效率。
【作者单位】：
【关键词】：
【分类号】：TP391.41【正文快照】：
八叉树数据结构以其结构简单、易于遍历、算法实现方便成为建立散乱点云的空间邻近关系,是近年来科研人员研究的热点。其实现方式主要有指针八叉树、线性八叉树。指针八叉树采用一组指针来记录节点父子之间的关系,由于指针高效的随机访问特性,用这种方式查询效率高,但需要大
欢迎：、、)
支持CAJ、PDF文件格式，仅支持PDF格式
【相似文献】
中国期刊全文数据库
龚健雅;[J];测绘学报;1992年02期
罗亚波,陈定方,肖田元;[J];武汉大学学报(信息科学版);2003年02期
孙文焕,方秋;[J];微机发展;1992年03期
潘志宏;张王俊;;[J];计算机世界;1994年09期
胡小红;周旺;吴杰;;[J];科技广场;2008年08期
林永良;胡建平;;[J];科协论坛(下半月);2009年10期
陈慧群;黎景炎;陈忠宁;陈志平;张斌;;[J];深圳信息职业技术学院学报;2009年04期
胡雪莲,孙永军,程承旗,马蔼乃;[J];地理与地理信息科学;2003年02期
周巧临,蒋华;[J];计算机与现代化;2004年12期
朱聃;张丽艳;;[J];中国制造业信息化;2007年01期
中国重要会议论文全文数据库
赵俊兰;赵洪岩;;[A];《测绘通报》测绘科学前沿技术论坛摘要集[C];2008年
中国博士学位论文全文数据库
吴慧欣;[D];西北工业大学;2007年
朱经纬;[D];华中科技大学;2007年
宋卫卫;[D];大连理工大学;2008年
徐江斌;[D];国防科学技术大学;2010年
肖永飞;[D];哈尔滨工业大学;2010年
张会霞;[D];中国矿业大学（北京）;2010年
张建国;[D];上海交通大学;2009年
中国硕士学位论文全文数据库
白鑫;[D];吉林大学;2013年
季振方;[D];山东大学;2011年
李天兰;[D];昆明理工大学;2011年
汤杨华;[D];长安大学;2009年
赵永民;[D];沈阳工业大学;2007年
肖何;[D];电子科技大学;2008年
李忠远;[D];浙江大学;2010年
侯庆;[D];贵州大学;2006年
王妍;[D];北京工业大学;2009年
谢路生;[D];厦门大学;2009年
&快捷付款方式
&订购知网充值卡
400-819-9993
《中国学术期刊（光盘版）》电子杂志社有限公司
同方知网数字出版技术股份有限公司
地址：北京清华大学 84-48信箱 知识超市公司
出版物经营许可证 新出发京批字第直0595号
订购热线：400-819-82499
服务热线：010--
在线咨询：
传真：010-
京公网安备75号八叉树-Octree（19）
八叉树维基释义：八叉树（Octree）是一种用于描述三维空间的状。八叉树的每个节点表示一个正方体的体积元素，每个节点有八个子节点，这八个子节点所表示的体积元素加在一起就等于父节点的体积。一般中心点作为节点的分叉中心。百度百科释义：八叉树（Octree）的定义是：若不为空树的话，树中任一节点的子节点恰好只会有八个，或零个，也就是子节点不会有0与8以外的数目。那么，这要用来做什么？想象一个立方体，我们最少可以切成多少个相同等分的小立方体？答案就是8个。再想象我们有一个房间，房间里某个角落藏着一枚金币，我们想很快的把金币找出来，聪明的你会怎么做？我们可以把房间当成一个立方体，先切成八个小立方体，然后排除掉没有放任何东西的小立方体，再把有可能藏金币的小立方体继续切八等份….如此下去，平均在Log8(房间内的所有物品数)的时间内就可找到金币。因此，八叉树就是用在3D空间中的场景管理，可以很快地知道物体在3D场景中的位置，或侦测与其它物体是否有碰撞以及是否在可视范围内。　　八叉树是一种用于描述三维空间的树状数据结构。八叉树的每个节点表示一个正方体的体积元素，每个节点有八个子节点，将八个子节点所表示的体积元素加在一起就等于父节点的体积。实现八叉树的原理&　　(1). 设定最大递归深度。　　(2). 找出场景的最大尺寸，并以此尺寸建立第一个立方体。　　(3). 依序将单位元元素丢入能被包含且没有子节点的立方体。　　(4). 若没达到最大递归深度，就进行细分八等份，再将该立方体所装的单位元元素全部分担给八个子立方体。　　(5). 若发现子立方体所分配到的单位元元素数量不为零且跟父立方体是一样的，则该子立方体停止细分，因为跟据空间分割理论，细分的空间所得到的分配必定较少，若是一样数目，则再怎么切数目还是一样，会造成无穷切割的情形。　　(6). 重复3，直到达到最大递归深度。& & & & & & & & & & & & & & & & & & & & & & & & & & & & &&八叉树三维数据结构&（一）&& 基本原理&&&&& 用八叉树来表示三维形体，并研究在这种表示下的各种操作及应用是在进入80年代后才比较全面地开展起来的。这种方法，既可以看成是四叉树方法在三维空间的推广，也可以认为是用三维体素阵列表示形体方法的一种改进。&&&& 八叉树的逻辑结构如下： 假设要表示的形体V可以放在一个充分大的正方体C内，C的边长为2n，形体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％。因此，这种方法虽然十分自然，容易掌握，但在存贮空间的使用率方面不很理想。2、线性八叉树&&&&& 线性八叉树注重考虑如何提高空间利用率。用某一预先确定的次序遍历八叉树(例如以深度第一的方式)，将八叉树转换成一个线性表（图2-5-2），表的每个元素与一个结点相对应。对于结点的描述可以丰富一点，例如用适当的方式来说明它是否为叶结点，如果不是叶结点时还可用其八个子结点值的平均值作为非叶结点的值等等。这样，可以在内存中以紧凑的方式来表示线性表，可以不用指针或者仅用一个指针表示即可。3、一对八式的八叉树&&&&& 一个非叶结点有八个子结点，为了确定起见，将它们分别标记为0，1，2，3，4，5，6，7。从上面的介绍可以看到，如果一个记录与一个结点相对应，那么在这个记录中描述的是这个结点的八个子结点的特性值。而指针给出的则是该八个子结点所对应记录的存放处，而且还隐含地假定了这些子结点记录存放的次序。也就是说，即使某个记录是不必要的(例如，该结点已是叶结点)，那么相应的存贮位置也必须空闲在那里（图2-5-3），以保证不会错误地存取到其它同辈结点的记录。这样当然会有一定的浪费，除非它是完全的八叉树，即所有的叶结点均在同一层次出现，而在该层次之上的所有层中的结点均为非叶结点。 为了克服这种缺陷，有两条途径可以采纳。一是增加计算量，在记录中增加一定的信息，使计算工作适当减少或者更方便。此上转载处：实现八叉树的原理 八叉树要用来做什么？ 想象一个立方体，我们最少可以切成多少个相同等分的小立方体？答案就是8个。再想象我们有一个房间，房间里某个角落藏着一枚金币，我们想很快的把金币找出来，聪明的你会怎么做？我们可以把房间当成一个立方体，先切成八个小立方体，然后排除掉没有放任何东西的小立方体，再把有可能藏金币的小立方体继续切八等份….如此下去，平均在Log8(房间内的所有物品数)的时间内就可找到金币。因此，八叉树就是用在3D空间中的场景管理，可以很快地知道物体在3D场景中的位置，或侦测与其它物体是否有碰撞以及是否在可视范围内。(1).&设定最大递归深度(2).&找出场景的最大尺寸，并以此尺寸建立第一个立方体(3).&依序将单位元元素丢入能被包含且没有子节点的立方体(4).&若没有达到最大递归深度，就进行细分八等份，再将该立方体所装的单位元元素全部分担给八个子立方体(5).&若发现子立方体所分配到的单位元元素数量不为零且跟父立方体是一样的，则该子立方体停止细分，因为跟据空间分割理论，细分的空间所得到的分配必定较少，若是一样数目，则再怎么切数目还是一样，会造成无穷切割的情形。(6).&重复3，直到达到最大递归深度。具体代码：#include &iostream&
//定义八叉树节点类
template&class T&
struct OctreeNode
T //节点数据
T xmin, //节点坐标，即六面体个顶点的坐标
OctreeNode &T&*top_left_front,*top_left_ //该节点的个子结点
OctreeNode &T&*top_right_front,*top_right_
OctreeNode &T&*bottom_left_front,*bottom_left_
OctreeNode &T&*bottom_right_front,*bottom_right_
OctreeNode //节点类
(T nodeValue = T(),
T xminValue = T(),T xmaxValue = T(),
T yminValue = T(),T ymaxValue = T(),
T zminValue = T(),T zmaxValue = T(),
OctreeNode&T&*top_left_front_Node = NULL,
OctreeNode&T&*top_left_back_Node = NULL,
OctreeNode&T&*top_right_front_Node = NULL,
OctreeNode&T&*top_right_back_Node = NULL,
OctreeNode&T&*bottom_left_front_Node = NULL,
OctreeNode&T&*bottom_left_back_Node = NULL,
OctreeNode&T&*bottom_right_front_Node = NULL,
OctreeNode&T&*bottom_right_back_Node = NULL )
:data(nodeValue),
xmin(xminValue),xmax(xmaxValue),
ymin(yminValue),ymax(ymaxValue),
zmin(zminValue),zmax(zmaxValue),
top_left_front(top_left_front_Node),
top_left_back(top_left_back_Node),
top_right_front(top_right_front_Node),
top_right_back(top_right_back_Node),
bottom_left_front(bottom_left_front_Node),
bottom_left_back(bottom_left_back_Node),
bottom_right_front(bottom_right_front_Node),
bottom_right_back(bottom_right_back_Node){}
//创建八叉树
template &class T&
void createOctree(OctreeNode&T& * &root,int maxdepth,double xmin,double xmax,double ymin,double ymax,double zmin,double zmax)
//cout&&&处理中，请稍候……&&&
maxdepth=maxdepth-1; //每递归一次就将最大递归深度-1
if(maxdepth&=0)
root=new OctreeNode&T&();
cout&&&请输入节点值:&;
//root-&data =9;//为节点赋值，可以存储节点信息，如物体可见性。由于是简单实现八叉树功能，简单赋值为9。
cin&&root-&
//为节点赋值
root-&xmin= //为节点坐标赋值
root-&xmax=
root-&ymin=
root-&ymax=
root-&zmin=
root-&zmax=
double xm=(xmax-xmin)/2;//计算节点个维度上的半边长
double ym=(ymax-ymin)/2;
double zm=(ymax-ymin)/2;
//递归创建子树，根据每一个节点所处（是几号节点）的位置决定其子结点的坐标。
createOctree(root-&top_left_front,maxdepth,xmin,xmax-xm,ymax-ym,ymax,zmax-zm,zmax);
createOctree(root-&top_left_back,maxdepth,xmin,xmax-xm,ymin,ymax-ym,zmax-zm,zmax);
createOctree(root-&top_right_front,maxdepth,xmax-xm,xmax,ymax-ym,ymax,zmax-zm,zmax);
createOctree(root-&top_right_back,maxdepth,xmax-xm,xmax,ymin,ymax-ym,zmax-zm,zmax);
createOctree(root-&bottom_left_front,maxdepth,xmin,xmax-xm,ymax-ym,ymax,zmin,zmax-zm);
createOctree(root-&bottom_left_back,maxdepth,xmin,xmax-xm,ymin,ymax-ym,zmin,zmax-zm);
createOctree(root-&bottom_right_front,maxdepth,xmax-xm,xmax,ymax-ym,ymax,zmin,zmax-zm);
createOctree(root-&bottom_right_back,maxdepth,xmax-xm,xmax,ymin,ymax-ym,zmin,zmax-zm);
//先序遍历八叉树
template &class T&
void preOrder( OctreeNode&T& * & p)
cout&&i&&&.当前节点的值为：&&&p-&data&&&\n坐标为：&;
cout&&&xmin: &&&p-&xmin&&& xmax: &&&p-&
cout&&&ymin: &&&p-&ymin&&& ymax: &&&p-&
cout&&&zmin: &&&p-&zmin&&& zmax: &&&p-&
preOrder(p-&top_left_front);
preOrder(p-&top_left_back);
preOrder(p-&top_right_front);
preOrder(p-&top_right_back);
preOrder(p-&bottom_left_front);
preOrder(p-&bottom_left_back);
preOrder(p-&bottom_right_front);
preOrder(p-&bottom_right_back);
//求八叉树的深度
template&class T&
int depth(OctreeNode&T& *& p)
if(p == NULL)
return -1;
int h =depth(p-&top_left_front);
return h+1;
//计算单位长度，为查找点做准备
int cal(int num)
int result=1;
if(1==num)
for(int i=1;i&i++)
int maxdepth=0;
int times=0;
static double xmin=0,xmax=0,ymin=0,ymax=0,zmin=0,zmax=0;
int tmaxdepth=0;
double txm=1,tym=1,tzm=1;
template&class T&
void find(OctreeNode&T& *& p,double x,double y,double z)
double xm=(p-&xmax-p-&xmin)/2;
double ym=(p-&ymax-p-&ymin)/2;
double zm=(p-&ymax-p-&ymin)/2;
if(x&xmax || x&xmin|| y&ymax || y&ymin || z&zmax || z&zmin)
cout&&&该点不在场景中！&&&
if(x&=p-&xmin+txm&& x&=p-&xmax-txm && y&=p-&ymin+tym &&y&=p-&ymax-tym && z&=p-&zmin+tzm &&z&=p-&zmax-tzm )
cout&&endl&&&找到该点！&&&&该点位于&&&
cout&&&xmin: &&&p-&xmin&&& xmax: &&&p-&
cout&&&ymin: &&&p-&ymin&&& ymax: &&&p-&
cout&&&zmin: &&&p-&zmin&&& zmax: &&&p-&
cout&&&节点内！&&&
cout&&&共经过&&&times&&&次递归！&&&
else if(x&(p-&xmax-xm) && y&(p-&ymax-ym) &&z&(p-&zmax-zm))
cout&&&当前经过节点坐标：&&&
cout&&&xmin: &&&p-&xmin&&& xmax: &&&p-&
cout&&&ymin: &&&p-&ymin&&& ymax: &&&p-&
cout&&&zmin: &&&p-&zmin&&& zmax: &&&p-&
find(p-&bottom_left_back,x,y,z);
else if(x&(p-&xmax-xm) && y&(p-&ymax-ym) &&z&(p-&zmax-zm))
cout&&&当前经过节点坐标：&&&
cout&&&xmin: &&&p-&xmin&&& xmax: &&&p-&
cout&&&ymin: &&&p-&ymin&&& ymax: &&&p-&
cout&&&zmin: &&&p-&zmin&&& zmax: &&&p-&
find(p-&top_left_back,x,y,z);
else if(x&(p-&xmax-xm) && y&(p-&ymax-ym) &&z&(p-&zmax-zm))
cout&&&当前经过节点坐标：&&&
cout&&&xmin: &&&p-&xmin&&& xmax: &&&p-&
cout&&&ymin: &&&p-&ymin&&& ymax: &&&p-&
cout&&&zmin: &&&p-&zmin&&& zmax: &&&p-&
find(p-&bottom_right_back,x,y,z);
else if(x&(p-&xmax-xm) && y&(p-&ymax-ym) &&z&(p-&zmax-zm))
cout&&&当前经过节点坐标：&&&
cout&&&xmin: &&&p-&xmin&&& xmax: &&&p-&
cout&&&ymin: &&&p-&ymin&&& ymax: &&&p-&
cout&&&zmin: &&&p-&zmin&&& zmax: &&&p-&
find(p-&top_right_back,x,y,z);
else if(x&(p-&xmax-xm) && y&(p-&ymax-ym) &&z&(p-&zmax-zm))
cout&&&当前经过节点坐标：&&&
cout&&&xmin: &&&p-&xmin&&& xmax: &&&p-&
cout&&&ymin: &&&p-&ymin&&& ymax: &&&p-&
cout&&&zmin: &&&p-&zmin&&& zmax: &&&p-&
find(p-&bottom_left_front,x,y,z);
else if(x&(p-&xmax-xm) && y&(p-&ymax-ym) &&z&(p-&zmax-zm))
cout&&&当前经过节点坐标：&&&
cout&&&xmin: &&&p-&xmin&&& xmax: &&&p-&
cout&&&ymin: &&&p-&ymin&&& ymax: &&&p-&
cout&&&zmin: &&&p-&zmin&&& zmax: &&&p-&
find(p-&top_left_front,x,y,z);
else if(x&(p-&xmax-xm) && y&(p-&ymax-ym) &&z&(p-&zmax-zm))
cout&&&当前经过节点坐标：&&&
cout&&&xmin: &&&p-&xmin&&& xmax: &&&p-&
cout&&&ymin: &&&p-&ymin&&& ymax: &&&p-&
cout&&&zmin: &&&p-&zmin&&& zmax: &&&p-&
find(p-&bottom_right_front,x,y,z);
else if(x&(p-&xmax-xm) && y&(p-&ymax-ym) &&z&(p-&zmax-zm))
cout&&&当前经过节点坐标：&&&
cout&&&xmin: &&&p-&xmin&&& xmax: &&&p-&
cout&&&ymin: &&&p-&ymin&&& ymax: &&&p-&
cout&&&zmin: &&&p-&zmin&&& zmax: &&&p-&
find(p-&top_right_front,x,y,z);
//main函数
int main ()
OctreeNode&double& *rootNode = NULL;
int choiced = 0;
while(true)
system(&cls&);
cout&&&请选择操作：\n&;
cout&&&1.创建八叉树 2.先序遍历八叉树\n&;
cout&&&3.查看树深度 4.查找节点
cout&&&0.退出\n\n&;
if(choiced == 0)
else if(choiced == 1)
system(&cls&);
cout&&&请输入最大递归深度：&&&
cout&&&请输入外包盒坐标，顺序如下：xmin,xmax,ymin,ymax,zmin,zmax&&&
cin&&xmin&&xmax&&ymin&&ymax&&zmin&&
if(maxdepth&=0|| xmax&xmin || ymax&ymin || zmax&zmin || xmin&0 || ymin&0||zmin&0)
tmaxdepth=cal(maxdepth);
txm=(xmax-xmin)/
tym=(ymax-ymin)/
tzm=(zmax-zmin)/
createOctree(rootNode,maxdepth,xmin,xmax,ymin,ymax,zmin,zmax);
cout&&&输入错误！&;
else if(choiced == 2)
system(&cls&);
cout&&&先序遍历八叉树结果：/n&;
preOrder(rootNode);
system(&pause&);
else if(choiced == 3)
system(&cls&);
int dep =depth(rootNode);
cout&&&此八叉树的深度为&&&dep+1&&
system(&pause&);
else if(choiced == 4)
system(&cls&);
cout&&&请输入您希望查找的点的坐标，顺序如下：x,y,z\n&;
double x,y,z;
cin&&x&&y&&z;
cout&&endl&&&开始搜寻该点……&&&
find(rootNode,x,y,z);
system(&pause&);
system(&cls&);
cout&&&\n\n错误选择！\n&;
system(&pause&);
}此上转载出处：我将上述代码调试了一下，改动了一些（原楼主是自动给每个节点数据都输入9，测试起来比较方便，我改成了自己输入，输入数较多的时候比较麻烦），调试过程中出现错误（我用的是VC6.0），把头文件#include&stdafx.h&注释掉之后就可以正常运行了。原楼主有点粗心，把\n打成了/n，我斗胆改了过来~这段代码用的递归函数比较多。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：6985859次
积分：83527
积分：83527
排名：第9名
原创：1127篇
转载：2950篇
评论：1297条
(3)(13)(13)(4)(9)(62)(16)(8)(23)(9)(37)(73)(34)(31)(120)(128)(183)(23)(69)(75)(1)(171)(33)(148)(168)(145)(27)(144)(139)(208)(61)(59)(10)(10)(32)(2)(7)(34)(24)(9)(39)(25)(32)(46)(20)(44)(8)(21)(43)(49)(100)(113)(136)(35)(55)(15)(29)(41)(15)(50)(17)(20)(182)(206)(43)(27)(19)(17)(13)(1)(40)(5)(3)(4)(21)(71)(73)(19)(2)(2)(1)(1)(1)(6)(3)