直接表达区域的四叉树链式编码
- 格式：pdf
- 大小：208.83 KB
- 文档页数：4
下载文档原格式
合集下载
地理名词解释
1.信息：是用文字、数字、符号、语言、图像等介质来表示事件、事物、现象等的内容、数量或特征，从而向人们提供关于现实世界新的事实和知识，是生产、建设、经营、管理、分析和决策的依据2.地理信息：是有关地理实体的性质、特征和运动状态的表征和一切有用的知识，它是对表达地理特征与地理现象之间关系的地理数据的解释3.地理数据：是各种地理特征和现象间关系的符号化表示，包括空间位置、属性位置及时域特征4.地理信息系统：它是在计算机硬、软件系统支持下，对整个或部分地理表层空间中的有关地理分布数据进行采集、储存、管理、运算、分析、显示和描述的技术系统5.大地水准面：可以假设当海水处于完全静止的平衡状态时，从海平面延伸到所有大陆下部，而与地球重力方向处处正交的一个连续、闭合的水准面，这就是大地水准面6.元数据：关于数据的数据7.栅格结构：是指将地球表面划分为大小均匀、紧密相邻的网格阵列，每个网格作为一个像元或像素，由行号、列号定义，并包含一个代码表示该像素的属性类型或量值，或仅仅包含指向其属性记录的指针。
8.矢量结构：即通过记录坐标的方式尽可能精确地表示点、线、面等地理实体，坐标空间设为连续，允许任意位置、长度和面积的精确定义9.失栅一体化数据结构：10.地图11.T IN数据结构：指用来进行镶嵌的小面块具有不规则的形状或边界12.数据库：就是为了一定目的，在计算机系统中以特定的结构组织、存储和应用相关联数据的集合13.地图数字化：指根据现有纸质地图，通过手扶跟踪或扫描矢量化的方法，生产出可在计算机上进行存储、处理和分析的数字化数据14.空间索引：指依据空间对象的位置和形状或空间对象之间的某种空间关系，按一定顺序排列的一种数据结构，其中包括空间对象的概要信息，如对象的标识、外接矩形及指向该空间对象实体的指针15.空间数据质量：是空间数据在表达这三个基本要素时，所能够达到的准确性、一致性、完整性，以及它们三者之间统一性的程度16.误差：反映数据与真实值或者大家公认的真值之间的差异，它是一种常用的数据准确性的表达方式17.模型：是对现实世界中的实体或现象的抽象或简化，是对实体或现象中的最重要的构成及其相互关系的表达，是为了理解和预测现实世界而构建的一种有效的替代物而不是现实世界的复制。
地理信息系统
一、名词解释(10小题，每小题3分，共30分)。
1.地理信息系统（GIS）:是在计算机软、硬件系统支持下，对整个或部分地球表层（包括大气层）的有关地理分布数据进行采集、储存、管理、运算、分析、显示和描述的技术系统。
简言之，地理信息系统是对空间数据进行采集、编辑、存储、分析和输出的计算机信息系统。
2.地理信息：是指表征地理圈或地理环境固有要素或物质的数量、质量、分布特征、联系和规律等的数字、文字、图像和图形等的总称。
3.地理数据：是以地球表面空间位置为参照，描述自然、社会和人文景观的数据。
4.不规则三角网模型（TIN）：简称TIN,它根据区域有限个点集将区域划分为相连的三角面网络，区域中任意点落在三角面的顶点、边上或三角形内。
5.拓扑关系：指网结构元素结点、弧段、面域之间的空间关系。
6.拓扑结构：指在点、线和多边形之间建立关联，以及彻底解决邻域和岛状信息处理问题而必须建立的数据结构。
7.空间数据结构：是指适合于计算机系统存储、管理和处理的地学图形的逻辑结构。
8.矢量数据结构：是利用几何学中的点、线、面及其组合体来表示地理实体空间分布的一种数据组织方式。
9.栅格数据结构：指将空间分割成有规则的网络，在各个网格上给出相应的属性值来表示地理实体的一种数据组织形式。
10.空间数据编码：指将数据分类的结果用一种易于被计算机和人识别的符号系统表示出来的过程。
11. Delaunay三角网：即由狄洛尼三角形组成的三角网，狄洛尼三角形有三个最邻近的点连接而成，这三个相邻点对应的V oronoi多边形有一个公共的顶点，此顶点同时也是狄洛尼三角形外接圆的圆心。
12. V oronoi多边形:由连接两邻点直线的垂直平分线组成的连续多边形组成的图形。
13.坐标变换：采用一定的数学方法将一种坐标系的坐标变换为另一种坐标系的坐标的过程。
14.数据精度：是考察数据质量的一个方面，即对现象描述的详细程度。
15.空间数据库：是地理信息系统在计算机物理存储介质上存储的与应用相关的地理空间数据的总和。
地理信息系统考试重点
1、信息和数据的区别：信息是由文字、数字、符号、语言、图像等介质来表示事件、事物、现象等的内容、数量或特征从你向人们（或系统）提供关于现实世界新的事实和知识，是生产、建设、经营、管理、分析和决策的依据。
而数据是一种未经加工的原始资料，信息是数据的内涵，数据是信息的表达。
2、地理信息系统的概念：是一种特定的十分重要的空间信息系统，它是在计算机硬件、软件系统支持下，对整个或部分地球表层（包括大气层）空间中的有关地理分布数据进行采集、存储、管理、运算、分析、显示和描述的技术系统。
3、GIS的构成：计算机硬件系统（主机、数据输入设备、数据存储设备、数据输出设备）计算机软件系统（计算机系统软件、地理信息系统软件和其他支撑软件、应用分析程序）地理空间数据、网络、系统开发、管理和使用人员。
4、地理信息特征：空间分布性、数据量大、信息载体的多样性。
5、大地水准面：假设当海水处于完全静止状态时，从海平面延伸到所有大陆下部而与地球重力方向处处正交的一个连续。
闭合的水准面，称为大地水准面。
6、地球椭球体：被大地水准面所包裹的球体称为大地椭球体。
7、我国常用大地坐标系统：1954年北京坐标系、1980年西安坐标系、WGS84坐标系8、地图如何描述地理空间实体：在地图学上，把地理空间的实体分为点、线、面三种要素，分别用点状、线状、面状符号来表示。
对那些占面积较小，不能按比例尺表示，又要定位的事物通常用点状要素表示，对于地面上是线状或带状的事物，在地图上均用线状要素表示。
对于不连续分布或连续分布的面状事物的分布范围和质量等特征一般用面状要素表示。
9、空间数据的基本特征：（1）空间特征：表示现象的空间位置或现在所处的地理位置（2）属性特征：表示现象的特征，如变量、分类、数据特征和名称等（3）时间特征：指现象或物体随时间的变化。
10、空间数据拓扑关系：邻接关系：空间图形中同类元素之间的拓扑关系、关联关系：空间图形中不同元素之间的拓扑关系、包含关系：空间图形中同类但不同级元素之间的拓扑关系。
四叉树编码
float fi=curary[0]; int i; //遍历当前数组，是否同构 for(i=0;i<=arysize*arysize-1;i++) {
if(fi!=curary[i]) {
break; }
} if(i==arysize*arysize) {
printf("%d,%f",level,fi); printf("\n"); return; }
二、 实现
本程序实现将一个（2������ ∗ 2������,k>1,不足则补网）数组（一维数组表示），打印 出每个字块的等级和值。
//实现四叉树编码
#include"stdio.h" void Qutree(int arysize,int level,float curary[] )//arysize 表示矩阵长度，level 表示等级，curary[]表示当前矩阵 {
}
level++; Qutree(arysize,level,ary1); Qutree(arysize,level,ary2); Qutree(arysize,level,ary3); Qutree(arysizein() {
//float aa[16]={1,1,2,2,1,1,3,3,4,2,1,2,3,4,3,4}; //Qutree(4,0,aa);
float aa[64]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1};
Qutree(8,0,aa); return 0;
}
参考资料：地理信息系统原理与算法（吴立新，史文中编著）
if(fi!=curary[i]) {
break; }
} if(i==arysize*arysize) {
printf("%d,%f",level,fi); printf("\n"); return; }
二、 实现
本程序实现将一个（2������ ∗ 2������,k>1,不足则补网）数组（一维数组表示），打印 出每个字块的等级和值。
//实现四叉树编码
#include"stdio.h" void Qutree(int arysize,int level,float curary[] )//arysize 表示矩阵长度，level 表示等级，curary[]表示当前矩阵 {
}
level++; Qutree(arysize,level,ary1); Qutree(arysize,level,ary2); Qutree(arysize,level,ary3); Qutree(arysizein() {
//float aa[16]={1,1,2,2,1,1,3,3,4,2,1,2,3,4,3,4}; //Qutree(4,0,aa);
float aa[64]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1};
Qutree(8,0,aa); return 0;
}
参考资料：地理信息系统原理与算法（吴立新，史文中编著）
研究生课程-GIS-地理信息系统考试题目及答案
一、名词解释（30分）1. Geomatics地球空间信息学, 所涵盖的学科范围包括(但不限于)地图学、控制测量、数字测图、大地测量、地理信息系统，水道测量、土地信息管理、土地测量、摄影测量、遥感、重力测量和天文测量。
所采用的方法有星载、机载、舰载和地面数据采集方法，属于现代测绘科学与计算机信息科学的集成，归属于空间信息科学。
2. DTMDTM（Digital Terrain Model）——数字地面模型是利用一个任意坐标系中大量选择的已知x、y、z的坐标点对连续地面的一个简单的统计表示，或者说，DTM就是地形表面形态属性信息的数字表达，是带有空间位置特征和地形属性特征的数字描述。
地形表面形态的属性信息一般包括高程、坡度、坡向等。
3. 数据融合数据融合技术是指利用计算机对按时序获得的若干观测信息，在一定准则下加以自动分析、综合，以完成所需的决策和评估任务而进行的信息处理技术。
数据融合技术，包括对各种信息源给出的有用信息的采集、传输、综合、过滤、相关及合成，以便辅助人们进行态势／环境判定、规划、探测、验证、诊断。
4. 空间数据引擎空间数据引擎，简称SDE，是一种空间数据库管理系统的实现方法，即在常规数据库管理系统之上添加一层空间数据库引擎，以获得常规数据库管理系统功能之外的空间数据存储和管理的能力。
代表性的是ESRI 的SDE。
空间数据引擎在用户和异种空间数据库的数据之间提供了一个开放的接口，它是一种处于应用程序和数据库管理系统之间的中间件技术。
使用不同厂商GIS的客户可以通过空间数据引擎将自身的数据提交给大型关系型DBMS，由DBMS统一管理；同样，客户也可以通过空间数据引擎从关系型DBMS中获取其他类型GIS的数据，并转化成客户可以使用的方式。
5. GIS互操作即空间数据的互操作，指针对异构的数据库和平台，实现数据处理的互操作，是“动态”的数据共享，独立于平台，具有高度的抽象性，是空间数据共享的发展方向。
GIS原理 总复习 总结 试题
（一）四叉树基本思想：
将2n×2n像元组成的图像(不足的用背景补上)按四个象限进行递归分割，并判断属性是否单一，单一：不分；不单一：递归分割。最后得到一颗四分叉的倒向树。
1）从四叉树的特点可知，一幅2n *2n栅格阵列图，具有的最大深度数为n，可能具有的层次为0，1，2，……..n、
2）每一层的栅格宽度，即每层边上包含的最大栅格数，反映了所在叶结点表示的正方形集合的大小，其值为：2（最大深度-当前层次）
百分比法
根据矩形区域内各要素所占面积的百分比数确定栅格单元的代码参与，如可记面积最大的两类BA也可根据B类和A类所占面积百分比数在代码中加入数字。
其它方法
10完全栅格数据结构
特点：最直观、最基本的网格存贮结构，没有进行任何压缩数据处理。
A
A
A
A
A
B
B
B
A
A
B
B
A
A
B
B
1）每行都从左到右记录；
AAAAABBBAABBAABB
在链状双重独立数据结构中，主要有四个文件：多边形文件、弧段文件、弧段坐标文件、结点文件。
链状双重独立式编码特点：
1.拓扑关系明确，也能表达岛信息，而且以弧段为记录单位，满足实际应用需要。
2、当图形数据修改、删除、增加点、线、面要素后，其拓扑关系也发生改变，所以，需重新建拓扑。
5)曲面数据结构
拓扑关系的类型（点线面之间关系）
第三章空间数据结构
1.空间数据结构概念
空间数据结构指对空间数据进行合理组织，以便于进行计算机处理，是地理实体的空间排列方式和相互关系的抽象描述，是数据模型和文件格式之间的中间媒介。
2.从现实世界到计算机世界四个层次（地理空间数据建模）
将2n×2n像元组成的图像(不足的用背景补上)按四个象限进行递归分割，并判断属性是否单一，单一：不分；不单一：递归分割。最后得到一颗四分叉的倒向树。
1）从四叉树的特点可知，一幅2n *2n栅格阵列图，具有的最大深度数为n，可能具有的层次为0，1，2，……..n、
2）每一层的栅格宽度，即每层边上包含的最大栅格数，反映了所在叶结点表示的正方形集合的大小，其值为：2（最大深度-当前层次）
百分比法
根据矩形区域内各要素所占面积的百分比数确定栅格单元的代码参与，如可记面积最大的两类BA也可根据B类和A类所占面积百分比数在代码中加入数字。
其它方法
10完全栅格数据结构
特点：最直观、最基本的网格存贮结构，没有进行任何压缩数据处理。
A
A
A
A
A
B
B
B
A
A
B
B
A
A
B
B
1）每行都从左到右记录；
AAAAABBBAABBAABB
在链状双重独立数据结构中，主要有四个文件：多边形文件、弧段文件、弧段坐标文件、结点文件。
链状双重独立式编码特点：
1.拓扑关系明确，也能表达岛信息，而且以弧段为记录单位，满足实际应用需要。
2、当图形数据修改、删除、增加点、线、面要素后，其拓扑关系也发生改变，所以，需重新建拓扑。
5)曲面数据结构
拓扑关系的类型（点线面之间关系）
第三章空间数据结构
1.空间数据结构概念
空间数据结构指对空间数据进行合理组织，以便于进行计算机处理，是地理实体的空间排列方式和相互关系的抽象描述，是数据模型和文件格式之间的中间媒介。
2.从现实世界到计算机世界四个层次（地理空间数据建模）
线性四叉树
及其属性。
编码流程图
Morton码=0
行列号（i，j）
提取栅格
是
完全相同
Morton=Morton+4 否
左上角栅格入栈
四个栅格均入栈
是
压栈
否
移动栈顶指针 是
Morton码<N*N 否
结束
二、线性四叉树的编码方法
2. 伪码法
• 从表1 可以看出, MD 码正是自下而上合并生成四叉树过程的序编号, 按自
线性四叉树
• From：GIS • Date：2013-11-12
线性四叉树
1
线性四叉树的定义
2
线性四叉树编码方法
3
线性四叉树的作用
一、线性四叉树的定义
• 线性四叉树只存储最后叶结点信息, 包括叶结点的位置、 大小和灰度。
• 线性四叉树叶结点的编号需要遵循一定的规则，这种编号 称为地址码，它隐含了叶结点的位置和深度信息。最常用 的地址码是四进制或十进制的Morton码。
二、线性四叉树的编码方法
1. 线性表法
•
对栅格数据按行顺序进行扫描, 顺序计算每个格网单元的MD 码, 这
需要开辟大小为
ห้องสมุดไป่ตู้
字节的线性表, 用于存储格网单元的MD
码及其属性。在提取格网单元的属性值和计算格网单元对应的MD 码后,
存入该表, 并对表按MD码的大小进行升级排序, 然后检查区域内相邻4
个栅格单元( 或子区) 的属性值。若相同, 则合并,仅记录最小的MD 码
历完后, A 数组各单元均得到相应的值, 且其下标恰为升序的MD 码。这种方
法与线性表法相比, 减少了MD 码的排序过程, 在运行速度上有所提高, 但其
空间数据结构中的四叉树编码性能
任何现象，无论大小，都可以被确定为一个对 象(Object)，且假设它可以从概念上与其邻域现象 相分离。在欧氏（Euclidean）空间中主要有点对象、 线对象、多边形对象和体。
•composed of identifiable entities
•Discrete data.
•Examples
– roads,rivers,
1.7 1.8 2.0 2.2 1.8 1.8 2.3 2.2
2.2 2.2 2.2 2.0
aabb aabc
字母：蔬菜类型、土地分区
空间数据结构中的四叉树编码性能
aacc cccb
2.2.2栅格数据组织方法
栅格数据以层的方 式来组织文件，在栅 格数据结构中，物体 的空间位置就用其在 笛卡尔平面网格中的 行号和列号坐标表示， 物体的属性用象元的 取值表示，每个象元 在一个网格中只能取 值一次，同一象元要 表示多重属性的事物 就要用多个笛卡尔平 面网格，称为层。
(5,5,1,1) (6,0,1,1) (6,8,1,1) (8,3,1,1) (11,8,1,1) (12,8,1,1) (14,3,1,1) (14,4,1,1)
2x2: (3,7,2,2) (4,9,2,2) (5,7,2,2) (7,7,2,2) (8,2,2,2) (9,7,2,2) (12,4,2,2) (13,2,2,2)
… 层n属性值
… 像元n
层1 像元1 X,Y,属性值
像元2 X,Y,属性值
…
…
像元n X,Y,属性值
层2
…
层n
空间数据结构中的四叉树编码性能
层1 多边形1 属性值 像元1坐标 … 像元n坐标
多边形N
层2
…
•composed of identifiable entities
•Discrete data.
•Examples
– roads,rivers,
1.7 1.8 2.0 2.2 1.8 1.8 2.3 2.2
2.2 2.2 2.2 2.0
aabb aabc
字母：蔬菜类型、土地分区
空间数据结构中的四叉树编码性能
aacc cccb
2.2.2栅格数据组织方法
栅格数据以层的方 式来组织文件，在栅 格数据结构中，物体 的空间位置就用其在 笛卡尔平面网格中的 行号和列号坐标表示， 物体的属性用象元的 取值表示，每个象元 在一个网格中只能取 值一次，同一象元要 表示多重属性的事物 就要用多个笛卡尔平 面网格，称为层。
(5,5,1,1) (6,0,1,1) (6,8,1,1) (8,3,1,1) (11,8,1,1) (12,8,1,1) (14,3,1,1) (14,4,1,1)
2x2: (3,7,2,2) (4,9,2,2) (5,7,2,2) (7,7,2,2) (8,2,2,2) (9,7,2,2) (12,4,2,2) (13,2,2,2)
… 层n属性值
… 像元n
层1 像元1 X,Y,属性值
像元2 X,Y,属性值
…
…
像元n X,Y,属性值
层2
…
层n
空间数据结构中的四叉树编码性能
层1 多边形1 属性值 像元1坐标 … 像元n坐标
多边形N
层2
…
栅格数据存储压缩编码方法
栅格数据存储压缩编码方法（3）、块式编码（4）、四叉树编码（1）、链式编码：由某一原点开始并按某些基本方向确定的单位矢量链。
基本方向可定义为：东＝0，南＝3，西＝2，北＝1等，还应确定某一点为原点。
（2）、行程编码：只在各行（或列）数据的代码发生变化时依次记录该代码以及相同代码重复的个数，即按（属性值，重复个数）编码（3）、块式编码：块式编码是将行程编码扩大到二维的情况，把多边形范围划分成由像元组成的正方形，然后对各个正方形进行编码。
（4）、四叉树编码而块状结构则用四叉树来描述，将图像区域按四个大小相同的象限四等分，每个象限又可根据一定规则判断是否继续等分为次一层的四个象限，无论分割到哪一层象限，只要子象限上仅含一种属性代码或符合既定要求的少数几种属性时，则停止继续分割。
否则就一直分割到单个像元为止。
而块状结构则用四叉树来描述。
按照象限递归分割的原则所分图像区域的栅格阵列应为2n2n（n为分割的层数）的形式。
下面就着重介绍四叉树编码。
直接栅格编码是最简单最直观而又非常重要的一种栅格结构编码方法，通常称这种编码为图像文件或栅格文件。
直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行都从左到右逐象元记录，也可奇数行从左到右，而偶数行由右向左记录，为了特定目的还可采用其它特殊的顺序,右图直接编码可表示为矩阵：四叉树编码又称为四分树、四元树编码。
它是一种更有效地压编数据的方法。
它将2n2n像元阵列的区域，逐步分解为包含单一类型的方形区域，最小的方形区域为一个栅格像元。
图像区域划分的原则是将区域分为大小相同的象限，而每一个象限又可根据一定规则判断是否继续等分为次一层的四个象限。
其终止判据是，不管是哪一层上的象限，只要划分到仅代表一种地物或符合既定要求的几种地物时，则不再继续划分否则一直分到单个栅格像元为止。
所谓四叉树结构，即把整个2ｎ2ｎ像元组成的阵列当作树的根结点，n为极限分割次数，n＋1为四分树的最大高度或最大层数。
地理信息系统原理
1、空间参照系统是指确定空间目标平面位置和高程的平面坐标和高程系。
2、地理信息系统：是由计算机硬件、软件和不同的方法组成的系统，该系统设计支持空间数据的采集、管理、处理、分析、建模和显示的计算机综合应用系统，可描述整个或部分地球表面或其实体的空间地理分布，用以解决复杂的规划和管理问题的特定的空间信息系统。
地理信息系统日是（GIS Day）：9月15。
工作原理:1)空间模型：将现实世界抽象为相互连接不同的特征的层面组合，这一实用的概念提供解决纷繁复杂的世界问题的途径。
2）地理参考系：空间数据包括绝对位置信息（经纬度）和相对位置信息（地址、编码、统计调查值等），它们可有效地解决地球表面任意空间定位。
3)矢量和栅格数据结构：以点、线、面方式编码并以（X,Y）坐标存储管理的矢量数据是表现离散空间特征的最佳方式，栅格数据通过一系列网格单元表达连续的地理特征。
功能：基本功能：1）数据采集与编辑；2）数据存储与管理；3）数据处理与变换；4）控件分析与统计；5）产品制作与演示；6）二次开发与编程；应用功能：1）资源管理；2）区域规划；3）国土监测；4）辅助决策；基础理论：地理学、地图学、测量学、数学、计算机科学等。
组成:空间数据、应用模型、系统软件、系统硬件、应用人员。
第一个地理信息系统：加拿大地理信息系统CGIS，Tomlinson。
3、大地水准面与具有微小扁率的旋转椭球面非常接近，可用来代表地球形状，故又名地球椭球面。
地球椭球体的大小，通常用长半径a，短半径b和扁率α三个几何参数来确定。
a=63771404、地理参照系：1、经纬度坐标系（地理坐标）2、笛卡尔平面坐标（投影坐标），3、高程系统5、我国GIS常用的平面坐标系：北京54，西安80，中国2000，WGS-84。
高程坐标系：56黄海，85国家（黄海）。
6、空间变换：为什么要进行？——数据坐标系统不一致，投影不一致。
如何处理：——建立两个平面上点之间的一一对应关系；内容：——包括几何纠正和投影变换。