当前位置：文档之家 › GIS原理课件4.8四叉树编码

GIS原理课件4.8四叉树编码

  • 格式：pdf
  • 大小：1.01 MB
  • 文档页数：27

36
2
37
2
38
0
39
0
栅格数据
00
0
00 00
0
00 22 00 00 00
11
1
11 22
2
22 22 00 00 00
44
4
44 44
4
44 44 44 44 44
44
4
44 44
4
44 44 44 44 44
将按照二M进D码制顺的序行，列检号查相两邻两四交个叉单元的属性值， 再相同将则其合转并换，为存储十最进小制M数D码及属性值，不同则存储所有单元。
MD码 0 4 8 12 16 20 24 28 32 33 34 35 36 37 38
……
属性值
0 1 0 2 4 4 4 4 2 2 0 0 2 2 0 ……
栅格数据
00
0
00 00
0
00 22 00 00
0
00
11
1
11 22
2
22 22 00 00
0
00
44
4
44 44
4
44 44
4
44 44
MD码 0 4 8 12 16 32 33 34 35 36 37
…… 48 52 56 60
属性值
0 1 0 2 4 2 2 0 0 2 2 …… 4 4 4 4
栅格数据
00
0
00 00
0
00 22 00 00
0
00
11
1
11 22
2
22 22 00 00
0
00
4444
44
4444
4
4444
44
4444 4444
1.四叉树的概念Concept
➢四叉树分割的基本思想：首先把一幅图象 或一幅栅格地图等分成四部分，如果检查到 某个子区的所有格网都含有相同的值（灰度 或属性值），那么，这个子区域就不再往下 分割；否则，把这个区域再分割成四个子区 域，这样递归地分割，直至每个子块都只含 有相同的灰度或属性值为止。
1.四叉树的概念Concept
01
2
00
00004444
22002200
2.常规四叉树Ordinary Quadtree
• 采用自上而下的分割方法，从顶层开始，先检测全区域， 如果其值不一致则四等分，直到数值一致为止。
◼ 如何存储常规四叉树？ ◼ 属性值 ◼ 父节点指针（1个） ◼ 叶节点指针（4个）
根节点
结点
叶
4
4
பைடு நூலகம்
节 点
0
01
MD码 0 4 8 12 16 32 33 34 35 36 37 38 39 40 44 48
属性值
0 1 0 2 4 2 2 0 0 2 2 0 0 0 0 4
栅格数据
00
0
00 00
0
00 22 00 00
0
00
11
1
11 22
2
22 22 00 00
0
00
4444
44
4444
4
4444
44
4444 4444
• 采用自上而下的分割方法，从顶层开始，先检测全区域， 如果其值不一致则四等分，直到数值一致为止。
00114444
根节点
WN EN 0 0 1 1 4 4 4 4
0 0 2 2 4 4 4 4 生成四叉树
结点
00224444
4
叶
4
节 点
22224444
0
WS ES 0 0 0 0 4 4 4 4
00004444
方法：将二进制的行列号两两交叉，再将其转换为十进制数。
3.线性四叉树Linear Quadtree
• 3.3 基于MD码的线性四叉树
➢3.3.1 MD码求解
• 求第二行第三列的MD码
行号
列号
2
3
二进制
10
11
➢3.3.2 MD码反求行列号
• 已知MD码为13，求行列号
Morton码 13
二进制
1 10 1
44
4444 4444
44
4444
按照MD码顺序，检查相邻四个单元的属性值， 相同则合并，存储最小MD码及属性值，不同则存储所有单元。
检测上层相邻四个单元属性值，直到遍历所有单元。
3.线性四叉树Linear Quadtree
• 3.3 基于MD码的线性四叉树 ➢3.3.3 MD码应用
MD码
0 1 4 5 16 17 20 21 2 3 6 7 18 19 22 23 8 9 12 13 24 25 28 29 10 11 14 15 26 27 30 31 32 33 36 37 48 49 52 53 34 35 38 39 50 51 54 55 40 41 44 45 56 57 60 61 42 43 46 47 58 59 62 63
44 44
4
44
44
4
44 44
4
44 44
4
44 44
4
44
按照MD码顺序，检查相邻四个单元的属性值， 相同则合并，存储最小MD码及属性值，不同则存储所有单元。
3.线性四叉树Linear Quadtree
• 3.3 基于MD码的线性四叉树 ➢3.3.3 MD码应用
MD码
0 1 4 5 16 17 20 21 2 3 6 7 18 19 22 23 8 9 12 13 24 25 28 29 10 11 14 15 26 27 30 31 32 33 36 37 48 49 52 53 34 35 38 39 50 51 54 55 40 41 44 45 56 57 60 61 42 43 46 47 58 59 62 63
• 通过逐次四等分的方法，将栅格数据分解为一系列单值的 方形区域。
00114444 00114444 00224444 00224444 22224444 00004444 00004444 00004444
主要内容
四叉树的概念 常规四叉树
线性四叉树
2.常规四叉树Ordinary Quadtree
主要内容
四叉树的概念 常规四叉树
★ 线性四叉树
3.线性四叉树Linear Quadtree
• 为了克服常规四叉树占用存储空间大的缺点，人们提 出了线性四叉树的算法。线性四叉树只存储最后叶结 点的信息，即结点的位置、大小和灰度。叶结点位置 采用基于四进制或十进制的Morton码表示（加拿大学 者Morton于1966年提出）；叶结点的大小用结点的深 度或层次表示。Morton码又称为M码。
2
00
22002200
优点：便于前后寻址 缺点：增加了数据存储量及操作的复杂性 应用：数据索引、图幅索引
2.常规四叉树Ordinary Quadtree
常规四叉树的特点如下：
(1)运算量较大。因为，大量数 据需要重复检查才能确定划分； （如7、8、9、10等格网需要检 查4次）
(2)占用的存储空间较大。每个 结点需要六个变量才能加以表 达：一个变量表示父结点指针， 四个变量代表四个子结点指针， 一个变量代表本结点的灰度或 属性值。
3.线性四叉树Linear Quadtree
• 3.3 基于MD码的线性四叉树 ➢3.3.3 MD码应用
MD码
0 1 4 5 16 17 20 21 2 3 6 7 18 19 22 23 8 9 12 13 24 25 28 29 10 11 14 15 26 27 30 31 32 33 36 37 48 49 52 53 34 35 38 39 50 51 54 55 40 41 44 45 56 57 60 61 42 43 46 47 58 59 62 63
32 33 34 35 36 37 38 ……
2 2 0 0 2 2 0 ……
栅格数据
00
0
00 00
0
00 22 00 00
0
00
11
1
11 22
2
22 22 00 00
0
00
44
4
44 44
4
44 44
4
44 44
4
44
44
4
44 44
4
44 44
4
44 44
4
44
按照MD码顺序，检查相邻四个单元的属性值， 相同则合并，存储最小MD码及属性值，不同则存储所有单元。
码 Ib , Jb 分别为栅格单元行列号的二进制数。
3.线性四叉树Linear Quadtree
• 3.3 基于MD码的线性四叉树
➢3.3.1 MD码求解
行号I= In-1 In-2 …. I1 I0 列号 J= Jn-1 Jnn--22 ….
J1 J0
二进制码
….
十进制码（ MD ） MD = J0*20 + I0*21 + J1*22 + I1*23 + …. + Jn-2*22n-4 + In-2*22n-3 + Jn-1*22n-2+In-1*22n-1
➢3.3.3 MD码应用
4
1
8
0
MD码
12
2
0 1 4 5 16 17 20 21
16
4
2 3 6 7 18 19 22 23 8 9 12 13 24 25 28 29 10 11 14 15 26 27 30 31 32 33 36 37 48 49 52 53 34 35 38 39 50 51 54 55 40 41 44 45 56 57 60 61 42 43 46 47 58 59 62 63

合集下载

GIS6空间数据管理

GIS6空间数据管理


栅格数据的形状、尺寸及相关问题
• 由于栅格结构对地表的离散，在计算面积、长 度、距离、形状等空间指标时，若栅格尺寸较 大，则造成较大的误差 。
• 由于栅格单元中存在多种地物，而数据中常常 只记录一个属性值，这会导致属性误差。比如， 遥感数据中的“混合像元”问题。
第29页/共137页
II 栅格数据结构的特点
第35页/共137页
III 决定栅格单元代码的方 式
4.百分比法 • 处理方法：根据栅格区域内各地理要素所占面积的百分比数确定栅 格单元的代码 • 适用于地物面积具有重要意义的分类体系
例如：可记面积最大的两 类BA，也可以根据B类和 A类所占面积百分比数在 代码中加入数字
第36页/共137页
III 决定栅格单元代码的方 式
第14页/共137页
1.3 数据与文件组织
一、数据的层次单位
物理单位: 位(比特)、字节、字、块(物理记录)、桶和卷
逻辑单位: 数据项、数据项组、记录、文件和数据库
文件
逻辑数据单位之间的关系
记录
数据项 数据项组
第15页/共137页
1.3 数据与文件组织
最基本的不可分割的数据单位,具有
数据项 独立的逻辑意义
在地理信息系统中的压缩编码多采用信 息无损编码，而对原始遥感影像进行压 缩时也可以采取有损压缩编码方法。
第42页/共137页
压缩编码方式
1 链码（Chain Codes） 链式编码又称为弗里曼链码（Freeman，
1961）或边界链码。该编码方法将数据 表示为由某一原点开始并按某些基本方 向确定的单位矢量链。 基本方向可定义为：东＝0，东南＝1， 南＝2，西南＝3，西＝4，西北＝5，北 ＝6，东北＝7 等八个基本方向。
GIS名词解释

GIS名词解释

GIS，由计算机硬件，软件和不同的方法组成的系统，该系统支持空间数据的采集，管理。

处理，分析，建模和显示，以便解决复杂的规划和管理问题℡救赎ヽ(1838247150) 17:31:15地理信息。

是指表示地理环境诸多要素的数量，质量，分布特征以及相互联系和变化规律的数字，文字，图像和图形等的总称℡救赎ヽ(1838247150) 17:34:34信息系统是具有采集管理，处理，分析和表达能力的系统。

信息系统是为实现某些特定功能，由人，机器，数据或方法按一定的相关关系联系起来进行工作的集合体，内部要素之间的相互联系通过信息流来实现。

由硬件，软件，数据和用户四个主要部分组成。

2017-10-25℡救赎ヽ(1838247150) 12:20:39地理数据，以地球表面空间位置为参考，描述自然和社会经济要素的数据，可以是图形，图像，文字，数字和表格等。

℡救赎ヽ(1838247150) 12:22:04地理信息科学，是研究地理信息采集，分析。

存储，显示，管理，传播和应用，以及地理信息流的产生，传输和转化规律的一门科学℡救赎ヽ(1838247150) 12:24:28数据模型，是对现实世界进行认知，简化和抽象表达，并将抽象结果组织成能反映现实世界真实状况数据集的桥梁，是GIS的基础。

2017-10-26℡救赎ヽ(1838247150) 10:51:38矢量数据结构，以几何空间坐标为基础，记录取样点坐标，能够精确的表示点，线及多边形实体，可以得到精美的地图，还可以对复杂数据以最小冗余进行存储，数据精度高，占存储空间少，是一种高效的图形数据结构。

℡救赎ヽ(1838247150) 10:55:40栅格数据结构，基于栅格模型的数据结构简称为栅格数据结构，指将空间分割成有规则的网格，在各个网格上给出相应的属性值来表示地理实体的一种数据组织形式。

℡救赎ヽ(1838247150) 10:57:26栅格矩阵，是最简单的栅格数据存储的方法，又称直接栅格编码。

GIS空间数据处理与分析

GIS空间数据处理与分析

内边界
栅格单元(i,j)四角点坐标的计算:
X(i1,i2)=(j-1)*DX和J*DX Y(i1,i2)=(i-1)*DY和i*DY I,j:栅格单元行列值; DX,DY:栅格单元边长
⑴:识别内边界,并将内边界端点坐标置零. 判别方法: 判断与栅格单元某条边相邻的另一栅 格单元的值,若值小于零,则该边为内边界. 内边界端点坐标置零: 边界起点和终点坐标置零.
分区数据的方法就称为空间数据的内插。
第五节 空间数据的内插方法
1、点的内插：研究具有连续变化特征现象 的数值内插方法。
步骤： 数据取样；数据处内插；数据记录
第五节 空间数据的内插方法
2、区域的内插
研究根据一组分区的已知数据来推求
同一地区另一组分区未知数据的内插方法。
区域内插方法：
2.1 叠合法：认为源和目标区的数据是均匀 分布的，首先确定两者面积的交集，然后 计算出目标区各个分区的内插值。
1、遥感与GIS数据的融合：
遥感技术的优势 融合必要性 GIS技术的优势 遥感图像与图形的融合 融合方法： 遥感数据与DEM的融合 遥感数据与地图扫描图像的融合第三节 多源 Nhomakorabea间数据的融合
2、不同格式数据的融合
不同格式数据的融合方法主要有：
2.1基于转换器的数据融合：
一种软件的数据格式输出为交换格式，然后用于另
P3
P
0
x
判断点是否在多边形内，从该点向左引水平扫描线，计算此 线段与区域边界相交的次数，若为奇数，该点在多边形内；若为 偶数，在多边形外。利用此原理，直接做一系列水平扫描线，求 出扫描线和区域边界的交点，对每个扫描线交点按X值的大小进 行排序，其两相邻坐标点之间的射线在区域内。
第二节
地理信息系统第四章数据采集与处理

地理信息系统第四章数据采集与处理


疏林地 733
未成林林地 734
迹地 735
针叶树疏林地 7331
阔叶树疏林地 7332
标志编号
Ⅰ
Ⅱ
Ⅲ
Ⅳ
Ⅴ
Ⅵ
Ⅶ
Ⅷ
Ⅸ
分类
1
属性数据的编码——编码方法 2
平原河
3
过渡河
山地河
• 多源分类编码法： 1
2 3
常年河
对于一个特定的分类时目令河标，根据诸多不同的
消失河
分类依据分别进行12 编码，各位数字代码之间并没有隶属通不航通关河 航河系。
地理数据库四种方式: 1.全部采用文件管理 2.文件结合关系数据库管理 3.全部采用关系数据库管理 4.重新设计具有空间数据和属 性数据管理和分析功能的数 据库系统（OO－DBMS）
6.地理数据库建立
第三节 地图数字化
一、手扶跟踪数字化 数字化仪组成、数字化方式、操作步骤
二、扫描矢量化 扫描仪原理、处理流程、操作方式
地图投影变换
正解变换 反解变换 数值变换
根据两种投影在变 换区内若干同名的 坐标点，采用插值 法、有限差分法、 待定系数法等，实 现不同投影之间的 转换
空间数据处理的方法-压缩处理
数据压缩的目的
节省存贮空间 节省处理时间
空间数据处理的方法-压缩处理
数据压缩途径
压缩软件:原数据信息基本不丢失而且可以大大 节省存贮空间，缺点是压缩后的文件必须在解 压缩后才能使用
1 2 3 4 5 6
1 2 3 4 5 6 7
1 2 3 4 5
1 2 3 4 5 6 7 8
1 2 3 4 5 6
树状河 平行河 筛状河 辐射河 扇形河 迷宫河
主〔要河〕流∶一级 支 流∶二级