线性八叉树邻域寻找新算法.docVIP

线性八叉树邻域寻找新算法 　　摘要:提出了一种直接利用三维栅格的编码求其邻域的新算法。这种算法在求相同尺寸邻域时,仅需扫描编码的后几位,而在求不同尺寸邻域时,则直接在已求出的相同尺寸邻域的基础上,利用编码的层次性和大小性寻找此邻域的各级祖先结点和各级子孙结点,且仅需扫描此邻域编码的前几位。 　　关键词:三维栅格 线性八叉树 邻域 　　 　　引言 　　 八叉树只记录叶结点的编码,而不记录中间结点的编码及层次关系,由于它比普通八叉树大大节省了存储空间,且蕴含有层次特性,因此它在实际工作中得到了广泛的应用。邻域实质上是一种拓扑关系,邻域的寻找在一定程度上说,也就是在三维栅格结构中确定物体间的拓扑关系。因此,寻找某一三维栅格的邻域也就成了克服栅格结构中拓扑关系不清晰及栅格矢量数据结构相互转换难点的一种新思路。因此,邻域寻找成为许多学者研究的重点之一。 　　 　　2 几个概念 　　2.1线性八叉树的邻域 　　 它的邻域则分为三种:面相邻的面邻域、边相邻的边邻域、角相邻的角邻域。线性八叉树任一栅格的面邻域有6个,边邻域有12个,角邻域有8个,共26个邻域。 　　2.2边界三维栅格与非边界三维栅格 　　 边界三维栅格是指处于边界上的三维栅格,它们的共同特点是在其各个邻域中总有一个或一个以上的邻域不存在,即这些邻域或是在研究区以外,或是在背景叶结点集中。除了边界三维栅格以外,剩下的都是非边界三维栅格,非边界三维栅格的各个邻域都存在。 　　2.3相同尺寸和不同尺寸邻域 　　 相同尺寸邻域是指待求邻域的尺寸与原三维栅格的尺寸相同。不同尺寸邻域则指待求邻域的尺寸与原三维栅格的尺寸不同,或大或小。 　　2.4对于八叉树编码基准体系的划分 　　 线性八叉树的编码基准体系划分为:北部N8={0,1,4,5}, 南部N8={2,3,6,7},西部W8={0,2,4,6}, 东部E8={1,3,5,7},上部U8={0,1,2,3} 下部D8={4,5,6,7},八叉树的面邻域分为东面、西面、南面、北面、上面、下面邻域;其边邻域可分为东上、东下、西上、西下、南上、南下、北上、北下、东北、西北、东南、西南边邻域;其角邻域分为8个,它们是西北上、西北下、东北上、东北下、东南上、东南下、西南上和西南下角邻域。 　　2.5线性八叉树层次编码特性剖析 　　 线性八叉树的编码有如下特性:(1)方向性。按照八叉树的编码基准,编码大小是按由西向东,由北向南、由上向下的顺序递增。(2)层次性。第n层像元的四进制编码应为:q1q2…qn, qi∈{0,1,2,3,4,5,6,7}, i=1,2,3,…,n在这些编码中,处在第1位的是第1层,第2位是第2层,第n位是第n层(第n次分割), 编码是321像元,因为第一位q1=3按照编码的基准,表示该像元在第1层中的位置为3,同样第2层的位置为2,第3层的位置为1。(3)可压缩性。由编码可知,每一个像元q1,q2,…,qn都需要n个字节来存贮,这显然有点浪费存贮空间,为此可采用位运算法将其转为十进制码以进一步压缩,如对四进制编码为321的像元有(321)4=3×82+2×8+1=209。(4)大小性。显然,编码的位数越多,深度越大,层次越低,像元尺寸越小,编码为2的像元的尺寸分别是编码为30、321像元尺寸的2倍和4倍。 　　 　　3 线性八叉树邻域的确定 　　3.1边界栅格识别 　　 对于任一像元A=O1O2…On,Oi为八进制整数,我们首先判断其是否为边界栅格,若 Oi∈E8或 Oi∈S8或 Oi∈W8或 Oi∈N8或 Oi∈U8或 Oi∈D8, 表示全部,则在面邻域中,其对应的E邻域或S邻域或W邻域或N邻域或U邻域或D邻域将分别不存在。对于边邻域、角邻域存在与否的情况,读者可自行推之。识别出边界栅格后,就知道了哪些邻域不存在,是不用求的。而对于存在的邻域,按下面的方法来求。 　　3.2 相同尺寸面邻域的确定 　　 对于线性八叉树的东、南、西、北面邻域的确定,由于只是在上部或下部内单独运算,上部和下部之间并不发生任何关系,所以可以直接用与线性四叉树相同的求解方法来确定它们。其中,末位qn为0或4、1或5、2或6、3或7的计算方法分别与线性四叉树末位qn为0、1、2、3的计算方法完全相同,只是要注意,若用计算公式计算,则要把上述四叉树公式中的4换成8,因为在八叉树中使用的是八进制编码。但是对于上部和下部发生关系的上下邻域的求解,则要按如下规则来求: 　　 若qn属于上部集合,根据八叉树编码标准体系,可以直接得其下面邻域为A+4,而其上面邻域编码的求解则要经过如下判断: 　　 从编码的末位qn按从右到左的顺序扫描,直到找到第一个不属于上部集合的编码qi(1≤i≤n-1,i为从左到右的