线性四叉树.pptVIP

线性四叉树 From：GIS Date：2013-11-12 线性四叉树的定义 1 线性四叉树编码方法 2 线性四叉树的作用 3 线性四叉树 一、线性四叉树的定义 线性四叉树只存储最后叶结点信息, 包括叶结点的位置、大小和灰度。 线性四叉树叶结点的编号需要遵循一定的规则，这种编号称为地址码，它隐含了叶结点的位置和深度信息。最常用的地址码是四进制或十进制的Morton码。 一、线性四叉树的定义 基于十进制的Morton码 它的计算方法是, 首先将区域的行、列号转换成二进制数Ib,Jb, 然后由下式得到M码。 M=2*Ib+Jb 一、线性四叉树的定义 线性四叉树的生成方法存在两种方案 一种仍采用自顶向下的分割方法, 即按常规四叉树分割方法进行, 且直接产生码Morton码的。 另一种方案采用从底向上的合并方法, 首先按一种特殊的扫描方式, 即按码的升序排列方式, 依次检查每四个相邻码对应的格网值, 如果相同则合并为一个大块, 否则将这四个格网记盘, 内容包括码、深度和属性值第一轮合并完成以后, 再依次检查四个大块的值此时仅需检查每个大块中的第一个值, 若其中有一个值不同或某子块已记盘, 则不作合并, 而记盘, 循环下去直到没有能够合并的子块为止。 二、线性四叉树的编码方法 线性表法 对栅格数据按行顺序进行扫描, 顺序计算每个格网单元的MD 码, 这需要开辟大小为 字节的线性表, 用于存储格网单元的MD 码及其属性。在提取格网单元的属性值和计算格网单元对应的MD 码后, 存入该表, 并对表按MD码的大小进行升级排序, 然后检查区域内相邻4个栅格单元( 或子区) 的属性值。若相同, 则合并,仅记录最小的MD 码及其属性。 Morton码=0 行列号（i，j） 提取栅格 完全相同 左上角栅格入栈 四个栅格均入栈 压栈 移动栈顶指针 Morton码N*N 结束 是 否 是 否 否 Morton=Morton+4 是 编码流程图 二、线性四叉树的编码方法 2. 伪码法 从表1 可以看出, MD 码正是自下而上合并生成四叉树过程的序编号, 按自然数顺序的线性表扫描即可产生四叉树。事先开辟一个大小为 的一维数组A ( 需要 字节的内存), 按行号顺序对栅格数据进行扫描, 把行、列号转换成伪码, 由伪码计算对应的MD 码, 并将格网属性值直接赋给以MD 码为下标的A 数组单元, 即A ( MD ) = V ( i , j ) 。当对所有的格网单元遍历完后, A 数组各单元均得到相应的值, 且其下标恰为升序的MD 码。这种方法与线性表法相比, 减少了MD 码的排序过程, 在运行速度上有所提高, 但其他缺点依然存在, 仍然需要大量的内存和运行时间。 二、线性四叉树的编码方法 3.线性四叉树快速动态编码 该方法用栈来代替线性表或数组, 在提取格网单元后, 直接检测其属性值、生成MD 码, 并同步地对已检测过的格网单元进行合并, 动态地建立四叉树。 线性四叉树快速动态编码的原理 四叉树动态编码的原理是以动态栈来代替静态的线性表或数组。在顺序提取格网单元属性值的过程中, 利用栈?? 先进后出??的特点, 通过压缩栈中的记录来建立四叉树。当完成对栅格数据的遍历和对栈的压缩后, 栈内记录就是所要求的线性四叉树编码结果。把栈内记录写成文件, 就实现了对栅格数据的线性四叉树编码。动态编码的过程可用图1 来表示。 二、线性四叉树的编码方法 MD 码是由行号和列号的二进制数两两交叉组合的结果 单元的属性值是否相同, 如果完全相同, 则仅把这 4 个格网单元中的左上角格网单元( 即MD 码最小者) 所对应的MD 码及其属性值入栈; 否则, 把4个格网单元按MD 码由小到大将其MD 码和属性值全部入栈。 当栈内记录数大于等于4 时, 需要判断是否对已入栈的记录进行合并压缩。 二、线性四叉树的编码方法 线性四叉树快速动态编码的实现 三、线性四叉树的编码作用 线性四叉树在基于LoD（Level of Detail） 的地表模型绘制中的应用 其主要思想是：在基于LoD技术的地表细节层次模型的绘制方法的基础上，结合线性四叉树在邻域有哪些信誉好的足球投注网站上的特性，就能消除绘制中易出现的“裂痕”现象。 线性四叉树在地表模型绘制中的应用 （1）首先，对每一分块进行线性四叉树编码，并对编码结果进行十进制压缩，连同当前编码的层数，一起作为当前分块的键值加以保存； （2）对所有分块根据其编码键值按照由小到大的顺序排列，这样在后面进行的邻域有哪些信誉好的足球投注网站过程中就可以实施折半查