GIS的空间数据结构及编码工程

内容回顾：返回地图投影与变换。内容回顾：返回

高斯—克吕格投影是一种横轴等角切椭圆柱投影。它是将一椭圆柱横切于地球椭球体上，该椭圆柱面与椭球体表面的切线为一经线，投影中将其称为中央经线，然后根据一定的约束条件即投影条件，将中央经线两侧规定范围内的点投影到椭圆柱面上，从而得到点的高斯投影

我国地理信息系统中常用的地图投影配置与计算高斯—克吕格投影分带示意图1）我国基本比例尺地形图（1：100万、1：50万、1：25万、1：10万、1：5万、1：2.5万、1：1万、1：5000）除1：100万外均采用高斯-克吕格投影为地理基础；2）我国1：100万地形图采用了Lambert投影，其分幅原则与国际地理学会规定的全球统一使用的国际百万分之一地图投影保持一致；返回试指出图中A和B两点所处哪个投影带(按高斯—克吕格投影6度分带方案)？两者所处投影带是否一致？AB射阳县A点所处投影带为20带B点所处投影带为21带返回试指出图中3576和20642所代表的含义？20642表示其投影带为20带，离移轴纵线642公里即中央经线以东142公里（642-500）。3576是指该坐标线上所有的点离赤道3576公里。返回试指出图中3547和40388所代表的含义？3547是指该坐标线上所有的点离赤道3547公里40388表示其为40投影带，离移轴纵线388公里即中央经线以西112公里返回矢量数据表示栅格数据表示第四章GIS的空间数据结构及编码

本章概述：地理信息系统的操作对象是空间地理实体，建立一个地理信息系统的首要任务是建立空间数据库，即将反映地理实体特性的地理数据存储在计算机中，这需要解决地理数据具体以什么形式在计算机中存储和处理即空间数据结构问题。第四章GIS的空间数据结构及编码

§4.1空间数据的特征和拓扑关系§4.2空间数据结构的概念§4.3栅格数据结构及其编码§4.4矢量数据结构及其编码§4.5栅格数据结构与矢量数据结构的比较§4.1空间数据的特征和拓扑关系

一、空间数据的基本特征要完整地描述空间实体或现象的状态，一般需要同时有空间数据和属性数据。如果要描述空间实体的变化，则还需记录空间实体或现象在某一个时间的状态。所以，一般认为空间数据具有三个基本特征：

1、定位特征:表示现象的空间位置或现在所处的地理位置,一般以坐标数据表示。2、拓扑特征:描述地理实体的相对位置关系.3、属性特征:表示地理实体或现象的专题属性特征，例如数量、分类、名称等数据和时间特征数据。时间特征是

指现象或物体随时间的变化。

空间数据的基本特征位置数据和属性数据相对于时间来说，常常呈相互独立的变化，即在不同的时间，空间位置不变，但是属性类型可能已经发生变化，或者相反。因此，空间数据的管理是十分复杂的

返回二、空间数据的拓扑关系1拓扑的基本概念(topology)拓扑关系是明确定义空间结构关系的一种数学方法。

理解拓扑变换和拓扑属性时，我们可以设想一块高质量的橡皮，它的表面是欧几里德平面，可被任意拉伸压缩，但不能扭转折叠。表面上有由结点、弧、环和区域组成的图形。若对该橡皮进行任意拉伸、压缩，但不扭转和折叠，则在橡皮形状的这些变换中，图形的一些属性将得到保留，有些属性将消失。返回aabcdebcde返回abcdea—1001b1—101c01—10d001—1e1101—aabcdebcde返回abcdea—1001b1—101c01—10d001—1e1101—aabcdebcde返回abcdea—1001b1—101c01—10d001—1e1101—aabcdebcdeabcdabcdd思考题?:2拓扑邻接、关联、包含拓扑邻接：指空间图形中同类元素之间的拓扑关系。

拓扑关联拓扑关联：指空间图形中不同类元素之间的拓扑关系。

拓扑包含拓扑包含：指空间图形中不同等级元素之间的拓扑关系。如查询：某铁路所经过的省份拓扑查询P2P1P3P1P2简单包含复杂包含返回P3P2P1

拓扑包含:对等包含P1P2P1P2P3P1P2P3简单包含多层包含等价包含拓扑的包含性拓扑和非拓扑属性两点之间的距离一个点指向另一个点的方向弧段的长度一个区域的周长一个区域的面积一个点在一个弧段的端点一个弧段是一个简单的弧段一个点在一个区域的边界上一个点在一个区域的内部一个点在一个区域的外部一个面是一个简单的面（无岛）一个面的连通性非拓扑属性拓扑属性

拓扑变换（橡皮变换）空间对象的拓扑空间关系

拓扑元素：点：孤立点、线的端点、面的首尾点、链的连接点线：两结点之间的有序弧段，包括链、弧段和线段面：若干弧段组成的多边形基本拓扑关系关联：不同拓扑元素之间的关系邻接：相同拓扑元素之间的关系包含：面与其他元素之间的关系层次：相同拓扑元素之间的层次关系拓扑元素量之间的关系：欧拉公式点、线、面之间的拓扑关系起点终点中间点弧段1弧段3弧段2弧段4点:面:弧:相邻相交重叠分离包含点—点点—线点—面线—面面—面线—线返回

拓扑关系的举例N3N1N2N4P1P2P3N5P4a1a2a3a4a5a6a7

图形的拓扑关联性返回多边形号弧段号P1a1，a5，a6P2a2，a4，

a6P3a3

，a5，a4P4a7

拓扑关系的举例N3N1N2N4P1P2P3N5P4a1a2a3a4a5a6a7

图形的拓扑关联性多边形号弧段号P1a1，a5，a6P2a2，a4，

a6P3a3

，a5，a4P4a7返回3拓扑关系的关联表达（1）全显式表示返回多边形号弧段号P1a4，a5，a6P2a1，a8，

a5P3a3

，a6，a7P4a2a7，a8

返回弧段号结点a1N1

，N2a2

N2，N4a3N4，N5a4N1，N5

a5N1，N3a6N3，N5a7N3，N4a8N2，N3返回结点弧段N1a1

，a4，a5N2a1，a2，

a8N3a5

，a6，a7，a8N4a2，a3，a7

N5a3

，a4，a6返回弧段左多边形右多边形a1oP2a2oP4a3oP3a4P1o

a5P2P1a6P3P1a7P4P3a8P4P2返回（2）半隐式表示ArcID起结点终结点左多边形右多边形坐标a1N1N2oP2Xn1,yn1…,Xn1yn1a2N2N4OP4Xn2,yn2…,Xn4yn4………………Arc/Info中的弧段数据结构4点、线、面基本数据之间可能存在的空间关系有以下几种点、线、面基本数据之间的关系，代表了空间实体之间的位置关系。分析点、线、面三种类型的数据，得出其可能存在的空间关系有以下几种：(1)点—点关系(2)点—线关系(3)点—面关系(4)线—线关系(5)线—面关系(6)面—面关系1)、点—点关系点和点之间的关系主要有两点（通过某条线）是否相连，两点之间的距离是多少？如城市中某两个点之间可否有通路，距离是多少？这是在实际生活中常见的点和点之间的空间关系问题。

2)、点—线关系点和线的关系主要表现在点和线的关联关系上。如点是否位于线上，点和线之间的距离等等。

3)、点—面关系点和面的关系主要表现在空间包含关系上。如某个村子是否位于某个县内？或某个县共有多少个村子？

4)、线—线关系线和线是否邻接、相交是线和线关系的主要表现形式。如河流和铁路的相交，两条公路是否通过某个点邻接？

5)、线—面关系线和面的关系表现为线是否通过面或和面关联或包含在面之内？

6)、面—面关系面和面之间的关系主要表现为邻接和包含的关系。返回流感病例区域流感病例在区内分布举例返回举例返回举例5空间数据的拓扑关系的意义空间数据的拓扑关系，对数据处理和空间分析具有重要的意义，因为：

(1)根据拓扑关系，不需要利用坐标或距离，可以确定一种空间实体相对于另一种空间实体的位置关系。拓扑关系能清楚地反映实体之间的逻辑结构关系，它比几何数据有更大的稳定性，不随地图投影而变化。

(2)利用拓扑关系有利于空间要素的查询，例如某条铁路通过哪些地区，某县与哪些县邻接。又如分析某河流能为哪些地区的居民提供水源，某湖泊周围的土地类型及对生物栖息环境作出评价等。

(3)可以根据拓扑关系重建地理实体。例如根据弧段构建多边形，实现道路的选取，进行最佳路径的选择等。

返回引例：1854年8月到9月英国伦敦霍乱流行琼·斯诺博士把道路、房屋、饮用水机井、霍乱病死者居住位置在1：6500的城区图上标出来霍乱病死者居住位置问题？集中钦用“布洛多斯托”水机井水井返回

在这个例子中利用了什么关系？水井在这个例子中，分析了患者的居住地与饮用水的空间位置关系。揭示了霍乱发病的传播途径。1.数据结构即数据组织的形式，是适合于计算机存储、管理、处理的数据逻辑结构。换句话说，是指数据以什么形式在计算机中存储和处理。数据按一定的规律储存在计算机机中，是计算机正确处理和用户正确理解的保证。

§4.2空间数据结构

一、空间数据结构基本概念

2.空间数据结构是指适合于计算机系统存储、管理和处理的地学图形的逻辑结构，是地理实体的空间排列方式和相互关系的抽象描述。即空间数据在计算机中的具体组织方式。一般来说，属性数据与其他信息系统一样常用二维关系表格形式存储。元数据以特定的空间元数据格式存储，而描述地理位置及其空间关系的空间特征数据是地理信息系统所特有的数据类型，主要以矢量数据结构和栅格数据结构两种形式存储。目前尚无一种统一的数据结构能够同时存储上述各种类型的数据，而是将不同类型的空间数据以不同的数据结构存储。返回矢量结构数据拓扑型数据实体型数据明确表示地理实体的空间关系栅格结构数据游程编码链式编码四叉树编码压缩编码方式的不同地理信息系统的空间数据结构主要有栅格结构和矢量结构。

返回矢量数据表示栅格数据表示返回§4.3栅格数据结构及其编码

一、概念

栅格数据结构是最简单最直观的空间数据结构，又称为网格结构(raster或gridcell)或象元结构(pixel)，是指将地球表面划分为大小均匀紧密相邻的网格阵列，每个网格作为一个象元或象素,由行、列号定义，并包含一个代码,表示该象素的属性类型或量值，或仅仅包含指向其属性记录的指针。因此，栅格数据结构是以规则的阵列来表示空间地物或现象分布的数据组织，组织中的每个数据表示地物或现象的非几何属性特征。

返回返回栅格数据表示在栅格结构中点、线、面表示点:用一个栅格单元表示；线:线状地物则用沿线走向的一组相邻栅格单元表示，面:面(或区域)用记有区域属性的相邻栅格单元的集合表示，每个栅格单元可有多于两个的相邻单元同属一个区域。

返回返回返回返回特点：属性明显，定位隐含栅格数据结构类型1、栅格矩阵结构2、游程编码结构3、链式编码结构4、四叉树编码结构5、八叉树和十六叉树编码结构属性明显：即数据直接记录属性的指针或属性本身，定位隐含：指所在位置则根据行列号转换为相应的坐标给出，也就是说定位是根据数据在数据集中的位置得到的。

二、栅格数据的特点及其主要类型1.面积占优法2.中心点法3.长度占优法4.重要性法三、栅格数据的取值返回AACCBCCCBDDCDDDD1.面积点优法以占矩形区域面积最大的地物类型或现象特性决定栅格单元的代码。

显见C类地物所占面积最大

返回AACCBACCBDCCDDDD2中心点法

用处于栅格中心处的地物类型或现象特性决定栅格代码中心点落在代码为A类的地物范围内返回AACCBACCBDCCDDDD3.长度占优法（请同学自已思考？作为课堂习题）长度占优法是将网格中心画一横线，然后取横线所占最长部分的属性值作为本栅格元素的值。横线所占最长部分的属性值代码为A类的地物返回AACCBDDCDDDCDDDD4.重要性法根据栅格内不同地物的重要性，选取最重要的地物类型决定相应的栅格单元代码。假设图D类属性为最重要的地物类型，即D比A、B和C类更为重要，则栅格单元的代码应为D返回ACCCBCCCBDCCDDCC假设图中C类属性为最重要的地物类型，当采用重要性法进行取值时，写出其取值结果。即C比A、B和D类属性更为重要，则栅格单元的代码应为C（请同学自已思考？作为课堂习题）返回游程编码栅格数据链式编码四叉树编码压缩编码直接栅格编码四、栅格数据编码返回直接栅格编码是最简单直观而又非常重要的一种栅格结构编码方法，通常称这种编码的图像文件为网格文件或栅格文件。栅格结构不论采用何种压缩编码方法，其逻辑原型都是直接编码网格文件。直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行都从左到右逐个象元记录，也可以奇数行地从左到右而偶数行地从右向左记录，为了特定目的还可采用其他特殊的顺序（图）。

（一）直接栅格编码返回举例：数据矩阵用100个整数表示返回返回游程编码是栅格数据压缩的重要编码方法。它的基本思路是：对于一幅栅格图像，常常有行(或列)方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。其编码方案是，只在各行(或列)数据的代码发生变化时依次记录该代码以及相同代码重复的个数，从而实现数据的压缩。（二）游程编码返回游程：指相邻同属性值的连续网格视为一游程。游程编码结构是逐将相邻同属性值的网格合并，并记录合并后网格的值及网格的长度。根据每个游程数据结构（编码方式）的不同分为游程长度编码和游程终止编码2228800058888770第一行：4个游程第二行：3个游程游程举例:返回游程编码其目的是栅格数据的数据量,减少数据间冗余。建立方法：将栅格矩阵的数据序列x1,x2,…,xn映射为相应的二元组序列（Ai,li）,i=1,2,…,m（m<n）,A为属性，

l为游程，m为游程序号。在游程长度编码中，li表示游程的连续长度；和游程终止编码，li表示游程的终止点列号。返回(0,7),(2,1),(0,2)(0,1),(1,1),(0,4),(2,1),(0,1),(3,2)(0,5),(2,1),(0,1),(3,3)(0,2),(2,4),(0,1),(3,1),(0,1),(2,1)(0,1),(2,5),(0,2),(2,1),(0,1)(0,1),(2,7),(0,2)(0,2),(2,4),(0,1),(3,2),(0,1)(0,1),(2,1),(0,4),(3,4)(2,1),(0,5),(3,4)(2,1),(0,9)例如对图所示的栅格数据，可沿行方向进行如下游程长度编码：用82个整数表示可见游程长度编码压缩数据是十分有效又简便的

返回游程终止编码(同学思考题)同学思考题(0,7),(2,8),(0,10)(0,2),(2,6),(0,7),(3,9),(0,10)优点：数据压缩率高，易于实现叠置，检索运算。缺点：只考虑水平分解元素之间相关性而未考虑垂直分解元素之间相关性，又称一维游程编码。返回（三）链式编码链式编码又称为弗里曼链码(Freeman，1961)或边界链码。链式编码主要是记录线状地物和面状地物的边界。它把线状地物和面状地物的边界表示为：由某一起始点开始并按某些基本方向确定的单位矢量链。基本方向可定义为：东＝0，东南＝l，南＝2，西南＝3，西＝4，西北＝5，北＝6，东北＝7等八个基本方向（如图3-4所示）。10234567链式编码举例：如果对于图所示的线状地物确定其起始点为像元(1，5)，则其链式编码为：

1，5,3,2,2,3,3,2,3对于图所示的面状地物，假设其原起始点定为像元（5，8），则该多边形边界按顺时针方向的链式编码为：5，8，3,2,4,4,6,6,7,6,0,2,1

链式编码的前两个数字表示起点的行、列数，从第三个数字开始的每个数字表示单位矢量的方向，八个方向以0—7的整数代表.优缺点：数据压缩率强，便于计算长度，面积，便于表示图形凹凸部分，易于储存。但难于实现叠置运算，不便于合并插入操作。适于对曲线和边界进行编码（四）块状编码

以正方形区域为单元对块状地物的栅格数据进行编码，实质是把栅格阵列中同一属性方形区域各元素映射成一个元素系列。编码方式：（行号，列号，半径，代码）（四）块状编码及其举例块码是游程长度编码扩展到二维的情况，采用方形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置（行、列号）和半径，再加上记录单位的代码组成。(1,1,1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7),(1,6,2,7),(1,8,1,7),(2,1,1,4),(2,4,1,4),(2,5,1,4),(2,8,1,7),(3,1,1,4),(3,2,1,4),(3,3,1,4),(3,4,1,4),(3,5,2,8),(3,7,2,7),(4,1,2,0),(4,3,1,4),(4,4,1,8),(5,3,1,8),(5,4,2,8),(5,6,1,8),(5,7,1,7),(5,8,1,8),(6,1,3,0),(6,6,3,8),(7,4,1,0),(7,5,1,8),(8,4,1,0),(8,5,1,0)。

对图所示图像的块码编码为：块码分割0225555522222555000003332222335500233355003333530003333300003333（1，1，1，0），（1，2，2，2），（1，4，1，5），（1，5，1，5），（1，6，2，5），（1，8，1，5）；（2，1，1，2），（2，4，1，2），（2，5，1，2），（2，8，1，5）；（3，3，1，2），（3，4，1，2），（3，5，2，3），（3，7，2，5）；（4，1，2，0），（4，3，1，2），（4，4，1，3）；（5，3，1，3），（5，4，2，3），（5，6，1，3），（5，7，1，5），（5，8，1，3）；（6，1，3，0），（6，6，3，3）；（7，4，1，0），（7，5，1，3）；（8，4，1，0），（8，5，1，0）。（四）块状编码举例特点：1、面状地物所能包含的正文形越大，多边形边界越简单，块码编码效率超高；2、图形比较碎，多边形边界复杂的图形，数据压缩率低；3、利于计算面积、合并插入等操作。返回（五）四叉树编码

(quad-treecode)

四又树结构的基本思想是将一幅栅格地图或图像等分为四部分。逐块检查其格网属性值(或灰度)。如果某个子区的所有格网值都具有相同的值。则这个子区就不再继续分割，否则还要把这个子区再分割成四个子区。这样依次地分割，直到每个子块都只含有相同的属性值或灰度为止。

四叉树分割

四叉树分割

返回23×23012310111213

NW0NE1SW2SE3A122对一幅2N

×2N的栅格阵列，最大深度为N，可能有的层次为0，1，2，…，N，那么，每层的栅格宽度为：

2（最大深度-当前层次）反映了所在叶结点表示的正方形集合的大小。

对于一个有2nX2n个像元的图像，可分的层数最多有n+1层（初始层为0层,最后一层为第n层，如下图是个8X8个像元组成的图像，可有3+1=4层。每一层不能分的块（即所有像元具有同一属性）称为叶结点，否则称为叉结点。叉结点和叶结点的位置由所在的层号及同一层所在的象限号唯一表示。象限号的排列见下图。因此编码时只要将每个叶结点的位置（层路径及象限号）和其属性记录下来即可。叶结点的包含的像元越多，压缩的效率就越高。0123仍用上面的例子，对0层先做十字四分，显然，所分出的四块都不一致（第一层），再四分，得到第二层。每个第一层中的第二层均有二块或一块同质，它们可不再分形成叶结点，其余相异的块还可做第三次也就是最后一次划分，得到第三层，第三层每块即为一个像元，划分结束。其过程用下图表示。MMRMMMMMMMRRMRMMMRRRRRRMMRRRRRRMMRRRRRRMMRRRRRRMMMRRRRRMMMMRRMMM1234567812345678MMRMMMMMMMRRMRMMMRRRRRRMMRRRRRRMMRRRRRRMMRRRRRRMMMRRRRRMMMMRRMMM叉结点叶结点1234567812345678MMRMMMMMMMRRMRMMMRRRRRRMMRRRRRRMMRRRRRRMMRRRRRRMMMRRRRRMMMMRRMMM0层1层2层3层其编码步骤是：1.逐级十字四分区划01230123012301232.编码NW（0）NE（1）NW（2）SE（3）0层1层2层3层记录每个叶子结点的地址和属性。按下述几种方法编码。0123202122232002012022032302312322331）.按层次和象限对叶结点直接编码（美国马里兰大学）0层1层2层3层012320212223200201202203230231232233该方法用二进制（共32位）记录每个叶结点的地址和属性值，其中地址包括两个部分，即深度（层）和路径（所经过的层及其象限）。见下图。000……1属性编码

22位路径2n位深度4位1层2象限2层3象限3层0象限第3层2）.基于四进制的四叉树编码四进制编码是用四进位表示各层叶结点的位置。编码采用自上而下进行。其步骤是：（a）将各栅格点的生行列坐标用二进制表示，见下图；（b）将二进位换算成四进位，方法是：如第4列（100）第3行（011）用四进制表示为2x011+100=122其反算规则是：行0和1为0如122的行为0112和3为1列0和2为0如122的列为1001和3为1000001010011100101110111000001010011100101110111000001010011100101110111000000001010011100101110111001002003012013102103112113010020021030031120121130131011022023032033122123132133100200201210211300301310311101202203212213302303312313110220221230231330331111222223232233332334M4=2*I行+I列000001010011100101110111000000001010011100101110111001002003012013102103112113010020021030031120121130131011022023032033122123132133100200201210211300301310311101202203212213302303312313110220221230231330331111222223232233332334（c）将每个叶结点换成四进制，它实际是叶结点的路径位置（如下图），注意，各叶结点的四进位码的位数与其层次相同，例如，第二层的叶结点其位数为2，如下图中的00，11，…30等。其数字由这个叶结点左上角的第一个像元的四制码取前n(所在号层）位得到，如第二层则取2位。MMRMMMMMMMRRMRMMMRRRRRRMMRRRRRRMMRRRRRRMMRRRRRRMMMRRRRRMMMMRRMMM00012010011013100101102103110210230220200312302122232230231213202200201203132130131133312310311313322320321323332330331333（d）写成记录位置码属性码00M010R011M012R013R……3).基于十进制的四叉树编码与四进位编码基本相同，其步骤是：（a）与四进制类似，每个像元的行、列号用二进制表示。（b）将行列号换算成十进制。二转十的方法是：将每个像元的行、列号交叉排位，如行为011，列为100，交叉排位后为011010。然后将此排位数换成10进位。即（c）对每个叶结点编码，如叶结点包含多个像元，用此叶结点的左上角像元的十进位码，见下图011010行号=011100=列号MMRMMMMMMMRRMRMMMRRRRRRMMRRRRRRMMRRRRRRMMRRRRRRMMMRRRRRMMMMRRMMM340645716171819209111081224483640464445473233353028293154525355585657596260616334位置码属性码0M4R5M6R7R8M9R10M11R12R位置码属性码16M17M18M19R20M24R28R29M30R31M位置码属性码32M33R34M35R36R40M44R45R46M47R位置码属性码48R52R53M54R55M56R57R58R59M60R位置码属性码61M62M63M（d）写成记录（e）再进行游程编码即将上述记录中，属性相同且连续的记录合并，写成下列形式。此时原43条记录变成29条记录。位置码属性码0M4R5M6R8M9R10M11R位置码属性码16M19R20M24R29M30R31M位置码属性码33R34M35R40M44R46M47R位置码属性码53M54R55M56R59M60R位置码属性码61M图栅格单元的十进制的Morton码图栅格单元的十进制的编码MMRMMMMMMMRRMRMMMRRRRRRMMRRRRRRMMRRRRRRMMRRRRRRMMMRRRRRMMMMRRMMM340645716171819209111081224483640464445473233353028293154525355585657596260616334举例:十进制的Morton码1、一种按位操作的方法：如行为2、列为3的栅格的MD步骤：

(1)行、列号为二进制Ib=10Jb=11(2)I行J列交叉

1101=13(3)再化为十进制.实质上是按左上、右上、左下、右下的顺序，从零开始对每个栅格进行自然编码。

A0A1A4A5A2B3B6B7A8A9B12B13A10A11B14B15四进制Morton码直观上切合四叉树分割，但许多语言不支持四进制变量，需用十进制表示Morton码.2、把一幅2n×2n的图像压缩成线性四叉树的过程

1°、按Morton码把图象读入一维数组。

2°、相邻的四个象元比较，一致的合并，只记录第一个象元的Morton码。循环比较所形成的大块，相同的再合并，直到不能合并为止。

3°、进一步用游程长度编码压缩。压缩时只记录第一个象元的Morton码。A0A1A4A5A2B3B6B7A8A9B12B13A10A11B14B15右图的压缩处理过程为：1°、按Morton码读入一维数组。

Morton码：0123456789101112131415象元值：AAABABBBAAAABBBB2°、四相邻象元合并，只记录第一个象元的Morton码。

01234567812AAABAABBAB3°、由于不能进一步合并，则用游程长度编码压缩。

0346812ABABABA0A1A4A5A2B3B6B7A8A9B12B13A10A11B14B15举例:十进制的Morton码这种从上而下的分割需要大量的运算，因为大量数据需要重复检查才能确定划分。当n*n的矩阵比较大，且区域内容要素又比较复杂时，建立这种四叉树的速度比较慢。另一种是采用从下而上的方法建立。对栅格数据按如下的顺序进行检测。如果每相邻四个网格值相同则进行合并，逐次往上递归合并，直到符合四叉树的原则为止。这种方法重复计算较少，运算速度较快。从图中可以看出，为了保证四叉树能不断的分解下去，要求图象必须为2n*2n的栅格阵列，n为极限分割次数，n+1是四叉树的最大高度或最大层数。对于非标准尺寸的图象需首先通过增加背景的方法将图象扩充为2n*2n的图象.(问题？）四叉树编码法有许多有趣的优点：①容易而有效地计算多边形的数量特征；②阵列各部分的分辨率是可变的，边界复杂部分四叉树较高即分级多，分辨率也高，而不需表示许多细节的部分则分级少，分辨率低，因而既可精确表示图形结构又可减少存贮量；②栅格到四叉树及四叉树到简单栅格结构的转换比其它压缩方法容易；④多边形中嵌套异类小多边形的表示较方便。四叉树编码的最大缺点是转换的不定性，用同一形状和大小的多边形可能得出多种不同的四叉树结构，故不利于形状分析和模式识别。四叉树编码的优缺点：四叉树结构按其编码的方法不同又分为常规四叉树和线性四叉树。常规四叉树除了记录叶结点之外，还要记录中间结点。结点之间借助指针联系，每个结点需要用六个量表达：四个叶结点指针，一个父结点指针和一个结点的属性或灰度值。线性四叉树则只存贮最后叶结点的信息。包括叶结点的位置、深度和本结点的属性或灰度值。所谓深度是指处于四叉树的第几层上。由深度可推知子区的大小。线性四叉树叶结点的编号需要遵循一定的规则，这种编号称为地址码，它隐含了叶结点的位置和深度信息。最常用的地址码是四进制或十进制的Morton码。五、栅格数据的获取1、目读法：适用于所选区域范围小，栅格单元尺寸大的情况。2、从扫描仪获取：高精度，快速度，数据格式标准化。3、从摄像机获取：栅格元素数固定512×5121024×10244、从遥感中获取：周期性，动态性，可自动提取专题信息。5、从矢量数据转换成栅格数据返回§4.4矢量数据结构及其编码返回

在地理系统中，由于空间数据代表着现实世界地理实体或现象在信息世界中的映射；因此它反映的特征同样应包括自然界地理实体向人类传递的基本信息。

栅格数据结构矢量数据结构主要有：返回矢量数据拓扑型数据实体型数据明确表示地理实体的空间关系栅格数据游程编码链式编码四叉树编码压缩编码方式的不同返回返回矢量数据表示栅格数据表示返回矢量数据拓扑型数据实体型数据明确表示地理实体的空间关系矢量数据结构是利用欧几里得（Euclid）几何学中的点、线、面及其组合体来表示地理实体空间分布的一种数据组织方式。这种数据组织方式能最好的逼近地理实体的空间分布特征，数据精度高。矢量数据结构主要有以下几种数据类型：（1）、简单数据结构（2）、拓扑数据结构（3）、曲面数据结构返回一、实体型数据结构(简单数据结构)返回返回实体型数据结构（spaghetti）--面条模型:以实体为单位记录其坐标缺点：1、相邻多边形的公共边界被数字化并存储两次，造成数据冗余和碎屑多边形—数据不一致，浪费空间，导致双重边界不能精确匹配。2、自成体系，缺少多边形的邻接信息，无拓扑关系，难以进行邻域处理，如消除多边形公共边界，合并多边形。3、岛作为一个单个图形，没有与外界多边形联系。不易检查拓扑错误。所以，这种结构只用于简单的制图系统中，显示图形。优点：结构简单、直观、易实现以实体为单位的运算和显示。多边形坐标串P1…P2…123456789101112131415PPP返回这种数据结构的主要特点是：数据按点、线或多边形为单元进行组织。数据编排直观，数字化操作简单每个多边形都以闭合线段存储，多边形的公共边界被数字化两次和存储两次。点、线或多边形都有各自的坐标数据，但没有拓扑数据岛只作为一个单个的图形，没有与外界多边形的联系二、索引式（树状）对所有点的坐标按顺序建坐标文件，再建点与边（线）、线与多边形的索引文件。123456789101112131415PPPMap1、点文件：点号坐标1x1,y1索引文件：面号弧段号P1A,B,C3、面文件：2、弧段文件:弧段号起点终点点号A527,8,9,10与实体式相比：优点：用建索引的方法消除多边形数据的冗余和不一致，邻接信息、岛信息可在多边形文件中通过是否公共弧段号的方式查询。缺点：表达拓扑关系较繁琐，给相邻运算、消除无用边、处理岛信息、检索拓扑关系等带来困难，以人工方式建立编码表，工作量大，易出错。三、双重独立式编码简称DIME(DualIndependentMapEncoding)，是美国人口统计系统采用的一种编码方式，是一种拓扑编码结构。

1、点文件点号坐标1x1,y12、线文件:线文件是以线段为记录单位线号左多边形

右多边形

起点终点L210P1P2210123456789101112131415PPP3、面文件面号线号P1L210,L109…关联邻接关联连通拓扑关系明确在DIME中做如下改进：将以线段为记录单位改为以弧段为单位链状双重独立式编码四、链状双重独立式编码--拓扑数据结构1、弧段坐标文件：弧段号坐标系列（串)Ax2,y2,X10,y10…2、弧段文件：链—面，链—结点关系弧段号

左多边形

右多边形

起点终点AP1P225123456789101112131415PPP3、面文件面号弧段号

P1A,B,-C4、点拓扑文件：结点—链关系点号

弧段号

2A,B,D在拓扑结构中，多边形（面）的边界被分割成一系列的线（弧、链、边）和点（结点）等拓扑要素，点、线、面之间的拓扑关系在属性表中定义，多边形边界不重复。链状双重独立式编码特点拓扑关系明确，也能表达岛信息，而且以弧段为记录单位，满足实际应用需要。因为一般数字化一条街道时，必然有许多中间点，但我们在做空间分析是却没有必要以这些中间点所组成的折线为研究对象，而应以整条弧段（某条街道）为研究对象.

国际著名GIS软件平台开发商美国ESRI公司的ARCGIS产品中的COVERAGE数据模型就是采用链状双重独立编码数据结构的。

返回五、拓扑编辑举例1多边形编辑返回2结点编辑返回六、曲面数据结构曲面是指连续分布现象的覆盖表面，具有这种覆盖表面的要素有地形、降水量、温度、磁场等。表示和存储这些要素的基本要求是必须便于连续现象在任一点的内插计算，因些常采用不规则三角网来拟合连续分布现象的覆盖表面，称为TIN(TriangulatedIrregularNetwork)数据结构。在所有可能的三角网中，狄洛尼(Delaunay)三角网在地形拟合方面表现最为出色，因此常被用于TIN的生成。返回六、曲面数据结构返回七返回返回问题返回返回返回正常多边形不规则多边形返回八、拓扑关系的意义反映地物之间的稳定空间位置关系可进行空间查询可重建地理实体空间数据的拓扑关系，对数据处理和空间分析具有重要的意义，因为：

(1)根据拓扑关系，不需要利用坐标或距离，可以确定一种空间实体相对于另一种空间实体的位置关系。拓扑关系能清楚地反映实体之间的逻辑结构关系，它比几何数据有更大的稳定性，不随地图投影而变化。

(2)利用拓扑关系有利于空间要素的查询，例如某条铁路通过哪些地区，某县与哪些县邻接。又如分析某河流能为哪些地区的居民提供水源，某湖泊周围的土地类型及对生物栖息环境作出评价等。

(3)可以根据拓扑关系重建地理实体。例如根据弧段构建多边形，实现道路的选取，进行最佳路径的选择等。外业测量获取（如GPS）可利用测量仪器自动记录测量成果(常称为电子手薄)，然后转到地理数据库中。用跟踪数字化方法获取数据利用栅格数据矢量化技术，把栅格数据转换为矢量数据从栅格数据转换成矢量数据

用跟踪数字化的方法，把地图变成离散的矢量数据。九、矢量数据的获取返回十、矢量数据的特点优点缺点矢量数据结构1.便于面向现象(土壤类、土地利用单元等)的数据表示；

2.数据结构紧凑、冗余度低；

3.有利于网络分析；

4.图形显示质量好、精度高。1.数据结构复杂；

2.软件与硬件的技术要求比较高；

3.多边形叠合等分析比较困难；

4.显示与绘图成本比较高。返回§4.5栅格数据结构与

矢量数据结构的比较返回一、返回优点缺点矢量数据结构1.便于面向现象(土壤类、土地利用单元等)的数据表示；

2.数据结构紧凑、冗余度低；

3.有利于网络分析；

4.图形显示质量好、精度高。1.数据结构复杂；

2.软件与硬件的技术要求比较高；

3.多边形叠合等分析比较困难；

4.显示与绘图成本比较高。栅格数据结构1.数据结构简单；

2.空间分析和地理现象的模拟均比较容易；

3.有利于与遥感数据的匹配应用和分析；

4.输出方法快速，成本比较低廉。1.图形数据量大；

2.投影转换比较困难；

3.栅格地图的图形质量相对较低；

4.现象识别的效果不如矢量方法。返回二、矢量、栅格数据结构的选择栅格结构:大范围小比例尺的自然资源等区域问题的研究。矢量结构：城市分区或详细规划、土地管理、公用事业管理等方面的应用。

在GIS建立