搜索
四叉树结构的基本思想是将一幅栅格地图或图像等分为四部分，逐块检查其格网属性值(或灰度)，如果某个子区的所有格网值都具有相同的值，则这个子区就不再继续分割，否则还要把这个子区再分割成四个子区。这样依次地分割，直到每个子块都只含有相同的属性值或灰度为止。从下而上的合并算法：如果每相邻四个网格值相同则进行合并，逐次往上递归合并，直到符合四叉树的原则为止。这种方法重复计算较少，运算速度较快。从上而下的分割算法：需要大量的运算，因为大量数据需要重复检查才能确定划分。当矩阵比较大，且区域内容要素又比较复杂时，建立这种四叉树的速度比较慢。②阵列各部分的分辨率是可变的，边界复杂部分四叉树较高即分级多，分辨率也高，而不需表示许多细节的部分则分级少，分辨率低，因而既可精确表示图形结构又可减少存贮量；②结点之间借助指针联系，每个结点需要用六个量表达：四个叶结点指针，一个父结点指针和一个结点的属性或灰度值。②线性四叉树叶结点的编号需要遵循一定的规则，这种编号称为地址码，它隐含了叶结点的位置和深度信息。最常用的地址码是四进制或十进制的Morton码。①常规四叉树除了记录叶结点之外，还要记录中间结点。③这些指针不仅增加了数据贮存量，而且增加了操作的复杂性。常规四叉树主要在数据索引和图幅索引等方面应用。③栅格到四叉树及四叉树到简单栅格结构的转换比其它压缩方法容易；①容易而有效地计算多边形的数量特征；为了保证四叉树能不断的分解下去，要求图像必须为2n*2n的栅格阵列，n为极限分割次数，n+1是四叉树的最大高度或最大层数。①线性四叉树则只存贮最后叶结点的信息。包括叶结点的位置、深度和本结点的属性或灰度值。（1）常规四叉树（2）线性四叉树④多边形中嵌套异类小多边形的表示较方便。四叉树的生成算法：四叉树结构分类：四叉树编码的特点：基于十进制的Morton码及四叉树的建立：2.2.4四叉树编码(quad-treecode)[四叉树分割演示]页码，1/2(W)w2010/12/2mhtml:file://F:\地理信息系统概论\漫画学GIS\四叉树\WebForm56.mhtPDF文件使用pdfFactory试用版本创建、JJ中的二进制数字交叉结合的结果，即设十进制表示的行、列号在计算机内部的二进制数字分别为：[上一根节][下一根节][回节目录][根节目录]在生成的线性四叉树表中，仍存在前后叶结点的值相同的情况，因而可以采取进一步的压缩表达，即将格网值相同的前后结点合并成一个值，形成二维行程编码（TwoDimensionalRunEncoding，简称2DRE）表。在这种二维行程编码中，前后两个地址码之差表达了该行程段的格网数，它可以表示该子块的大小。[回章目录]二维行程编码：基于按位操作的运算计算Morton码：线性四叉树存储结构：(b)基于十进制的线性四叉树Morton码(b)二维行程编码存储结构（a）线性四叉树存储结构（a）四叉树分割示意图页码，2/2(W)w2010/12/2mhtml:file://F:\地理信息系统概论\漫画学GIS\四叉树\WebForm56.mhtPDF文件使用pdfFactory试用版本创建