栅格数据的四叉树

5，5 2，A 3，B 1，A 3，C 1，A 1，D 2，C 2，A
…
…
☞块码(游程编码向二维扩展)
☞块式编码是将游程扩大到两维情况，把 多边形范围划提成若干具有同一属性旳正 方形，然后对各个正方形进行编码。 ☞块式编码旳数据构造由初始位置（行列 号）、半径和属性代码构成。
块码示意图
M M R M M MMM MMRRMRMM
MR RR RR RM MR R RRR RM MR RR RR RM MR RR RR RM MMRR R RRM M M M R R M MM
四叉树：叶子节点和树杈节点
12 34 5 6 78
在四叉树中，不能再分旳结点称为叶子结 点，可再分旳结点称为树杈结点
123 45678
M M R M M MMM MMRRMRMM
四叉树编码实例
区域分割措施
M M R M M MMM MMRRMRMM MR RR RR RM MR R RRR RM MR RR RR RM MR RR RR RM MMRR R RRM M M M R R M MM
12 34 5 6 78
123 45678
M M R M M MMM MMRRMRMM
旳单位矢量链来表达线状地物或多边形旳边界。
☞四叉树编码(Quadtree Encoding)
☞四叉树又称四元树或四分树，是最有效旳栅格数据压 缩编码措施之一。
☞四分树将整个图像区域逐渐分解为一系列方形区域， 且每一种方形区域具有单一旳属性。最小区域为一种象 元。
☞区域分割原则：将欲分解区域等分为四个象限，再根 据各个象限旳象元值是否单一决定要不要再分。假如单 一则不再分割，不然同法再分，直到全部象限旳象元属 性值相同为止。

567
4
0
04477777 4 4 4 4 47 7 7 4 4 4 48 87 7 00488877 00888878 00088888 00008888 00000888
3
1
2
属性值为“4”的多边形:
（ 4,1，2）0，1，0，3，3， 5，4，6，7
17
特点: 可以有效地压缩栅格数据,而且对于估算面积、长度、转折方
层2
…
层n
栅格数据文件 层1 多边形1 属性值
像元1坐标 …
像元n坐标 多边形N
层2
…
10
层n
六、栅格数据存储编码
1、直接栅格编码 当每个像元都有唯一一个属性值时,一层内的编码就需要
m行×n列×3(x,y和属性编码值)个存储单元。
栅格数据是二维表面上地理数据的离散量化值,每一层的象元值组成
像元阵列（即二维数组），其中行、列号表示它的位置。
例如影像:
AAAA
ABBB
ABBB
AAAB 在计算机内是一个4*4阶的矩阵。但在外部设备上，以左上角开始逐行 逐列存贮。如上例存贮顺序为：A A A A A B B B A A B B A A A B
11
2、压缩编码方法 目的:用尽可能小的数据量来记录尽可能多的信息。 方法:游程长度编码、链码、块码、四叉树编码。
❖ 以层为基础。每一层又以像元为序记录它的坐标和属性值。
❖ 以层为基础。但每一层内以多边形为序记录多边形的属性值和充 满多边形的各像元的坐标。
栅格数据文件
像元1 像元2
X坐标 Y坐标 层1属性值 层2属性值
… 层n属性值
… 像元n
栅格数据文件
层1 像元1 X,Y,属性值

线性四叉树的编码与解码
• 位图的读入 • 程序的简介 • 程序的流程 • 程序的结果
• 位图的结构
位图的读入
BITMAPFILEHEADER 位图文件头
BITMAPIFOHEADER 位图信息头
颜色表
24bit的位图没有颜色表
位图数据
位图的读入
• 位图读入的基本流程
读方式打开文件
跳过文件头结构
读入信息头结构
存放结点信息
struct LinkStack{ PNode top;};
链栈结构
• 数据说明
程序的简介
QuadTree类 QuadTree
class QuadTree{ public: PLinkStack createEmptyStack_link(); //生成空栈 void push (PLinkStack plstack,MortonAndPixel x); //元素入栈 void pop(PLinkStack plstack); //元素出栈 MortonAndPixel CatchTop(PLinkStack plstack); //获取栈顶元素 int GetT(long Num);//获取结点循环次数 int GetHang(long morton);//morton码反算得到行 int GetLie(long morton);//morton码反算得到列 }
移动栈顶指针 元素Next指针=NULL 是 结束
程序的流程
• 解码示意
解码入新栈 取栈顶元素
栈顶指针
16 4 12 2 8 0 4 1 0 0 Morton码 属性值
16 12
取下一个元素
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Morton码 4 2 2 2 2 0 0 0 0 1 1 1 1 0 0 0 0 属性值

栅格数据详解目录一简介二栅格结构的数据组织方法三栅格数据的获取途径与原则四栅格结构的编码方法一简介1基本知识栅格数据是按网格单元的行与列排列、具有不同灰度或颜色的阵列数据。

栅格结构是大小相等分布均匀、紧密相连的像元(网格单元)阵列来表示空间地物或现象分布的数据组织。

是最简单、最直观的空间数据结构，它将地球表面划分为大小、均匀、紧密相邻的网格阵列。

每一个单元(象素)的位置由它的行列号定义，所表示的实体位置隐含在栅格行列位置中，数据组织中的每个数据表示地物或现象的非几何属性或指向其属性的指针。

对于栅格结构:点实体由一个栅格像元来表示;线实体由一定方向上连接成串的相邻栅格像元表示;面实体(区域)由具有相同属性的相邻栅格像元的块集合来表示。

2栅格结构的特点数据直接记录属性的指针或属性本身，而其所在位置则根据行列号转换成相应的坐标给出。

也就是说，定位是根据数据在数据集合中的位置得到的。

如图1(a)所示，数据1表示属性或编号位的一个点，其位置由所在的第3行、第5列得到。

因为栅格结构是按一定的规则排列的，因此所表示的实体位置很容易隐含在网格文件的存储结构中。

在网格文件中每个代码本身明确地代表了实体的属性或属性编码，如果为属性编码，则该编码可作为指向实体属性表的指针。

图1(a)中表示了代码分别为1，3，6的实体，图1(b)表示了一条代码为8的线实体，图1(c)表示了3个代码分别为4，7，9的面实体。

(a)点(b)线(c)区域000000000080000044447777000000000008000044444777000010000000800044449977000000000000080000499977000300000000080000099977000000000000080000099999000006000008800000009999000000000000000000000999图1二栅格结构的数据组织方法栅格地图数据栅格结构是用有限的网格逼近某个图形，因此用栅格数据表示的地表是不连续的，是近似离散的数据。