第四章 GIS的空间数据结构及编码.

1、返返 回回GIS所存贮记录、管理分析、显示应用的内容是地理信息，而地理信息的描述必须要有指定的地理参照系，且地理位置应以地理坐标或平面坐标的方式表示出来。返返 回回地图投影与变换。地图投影与变换。返返 回回高斯克吕格投影是一种横轴等角切横轴等角切椭圆柱投影椭圆柱投影。它是将一椭圆柱横切于地球椭球体上，该椭圆柱面与椭球体表面的切线为一经线，投影中将其称为中央经线中央经线，然后根据一定的约束条件即投影条件，将中央经线两侧规定范围内的点投影到椭圆柱面上，从而得到点的高斯投影我国地理信息系统中常用的地图投影配置与计算高斯克吕格投影分带示意图1）我国基本比例尺地形图（1：100万、1：50万、1：25万

2、、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公里即中央经线以东公里即中央经线以东14

3、2公里（公里（642-500）。3576是指该坐标线上所有是指该坐标线上所有的点离赤道的点离赤道3576公里公里。返返 回回试指出图中3547和40388所代表的含义？3547是指该坐标线上所有的点离赤道3547公里40388表示其为40投影带，离移轴纵线388公里即中央经线以西112公里返返 回回矢量数据表示栅格数据表示本章概述：地理信息系统的操作对象是空间地理实体，建立一个地理信息系统的首要任务是建立空间数据库，即将反映地理实体特性的地理数据存储在计算机中，这需要解决地理数据具体以什么形式在计算机中存储和处理即空间数据结构问题。返返 回回 理解拓扑变换和拓扑属性时，我们可以设想理解拓扑变换

4、和拓扑属性时，我们可以设想一块高质量的橡皮，它的表面是欧几里德平一块高质量的橡皮，它的表面是欧几里德平面，可被任意拉伸压缩，但不能扭转折叠。面，可被任意拉伸压缩，但不能扭转折叠。表面上有由结点、弧、环和区域组成的图形。表面上有由结点、弧、环和区域组成的图形。若对该橡皮进行任意拉伸、压缩，但不扭转若对该橡皮进行任意拉伸、压缩，但不扭转和折叠，则在橡皮形状的这些变换中，图形和折叠，则在橡皮形状的这些变换中，图形的一些属性将得到保留，有些属性将消失。的一些属性将得到保留，有些属性将消失。返返 回回aabcdebcde返返 回回abcdea1001b1101c0110d0011e1101aabcdeb

5、cde返返 回回abcdea1001b1101c0110d0011e1101aabcdebcde返返 回回abcdea1001b1101c0110d0011e1101aabcdebcdeabcdabcdd思考题思考题?:P2P1P3P1P2返返 回回P3P2P1简单包含简单包含 多层包含多层包含 等价包含等价包含拓扑的包含性拓扑的包含性拓扑和非拓扑属性拓扑和非拓扑属性两点之间的距离两点之间的距离一个点指向另一个点的方向一个点指向另一个点的方向弧段的长度弧段的长度一个区域的周长一个区域的周长一个区域的面积一个区域的面积一个点在一个弧段的端点一个点在一个弧段的端点一个弧段是一个简单的弧段一个弧段是

6、一个简单的弧段一个点在一个区域的边界上一个点在一个区域的边界上一个点在一个区域的内部一个点在一个区域的内部一个点在一个区域的外部一个点在一个区域的外部一个面是一个简单的面（无岛）一个面是一个简单的面（无岛）一个面的连通性一个面的连通性非拓扑属性非拓扑属性拓扑属性拓扑属性 拓扑变换拓扑变换 （橡皮变换）（橡皮变换）空间对象的空间对象的拓扑空间关系拓扑空间关系0 拓扑元素：拓扑元素：q 点：孤立点、线的端点、面的首尾点、链的连接点点：孤立点、线的端点、面的首尾点、链的连接点q 线：两结点之间的有序弧段，包括链、弧段和线段线：两结点之间的有序弧段，包括链、弧段和线段q 面：若干弧段组成的多边形面：若

7、干弧段组成的多边形0 基本拓扑关系基本拓扑关系q 关联：不同拓扑元素之间的关系关联：不同拓扑元素之间的关系q 邻接：相同拓扑元素之间的关系邻接：相同拓扑元素之间的关系q 包含：面与其他元素之间的关系包含：面与其他元素之间的关系q 层次：相同拓扑元素之间的层次关系层次：相同拓扑元素之间的层次关系q 拓扑元素量之间的关系：欧拉公式拓扑元素量之间的关系：欧拉公式0 点、线、面之间的拓扑关系点、线、面之间的拓扑关系起点终点中间点弧段1弧段3弧段2弧段4点:面:弧:相邻相邻相交相交重叠重叠分离分离包含包含点点点点点点线线点点面面线线面面面面面面线线线线返返 回回N3N1N2N4P1P2P3N5P4a1a

8、2a3a4a5a6a7返返 回回多边形号弧段号P1a1，a5，a6P2a2，a4，a6P3a3，a5，a4P4a7N3N1N2N4P1P2P3N5P4a1a2a3a4a5a6a7多边形号弧段号P1a1，a5，a6P2a2，a4，a6P3a3，a5，a4P4a7返返 回回返返 回回多边形号弧段号P1a4，a5，a6P2a1，a8，a5P3a3，a6，a7P4a2a7，a8返返 回回弧段号结点a1N1，N2a2N2，N4a3N4，N5a4N1，N5a5N1，N3a6N3，N5a7N3，N4a8N2，N3返返 回回结点弧段N1a1，a4，a5N2a1，a2，a8N3a5，a6，a7，a8N4a2，a

9、3，a7N5a3，a4，a6返返 回回弧段 左多边形 右多边形a1oP2a2oP4a3oP3a4P1oa5P2P1a6P3P1a7P4P3a8P4P2返返 回回ArcID起结点终结点左多边形右多边形坐标a1N1N2oP2Xn1,yn1,Xn1yn1a2N2N4OP4Xn2,yn2,Xn4yn4Arc/Info中的弧段数据结构4 4 点、线、面基本数据之间可能存在的空间关系有以下几种点、线、面基本数据之间可能存在的空间关系有以下几种点、线、面基本数据之间的关系，代表了空间实体点、线、面基本数据之间的关系，代表了空间实体之间的位置关系。分析点、线、面三种类型的数据，之间的位置关系。分析点、线、面三

10、种类型的数据，得出其可能存在的空间关系有以下几种：得出其可能存在的空间关系有以下几种： (1)点点点关系点关系 (2)点点线关系线关系(3)点点面关系面关系(4)线线线关系线关系(5)线线面关系面关系(6) 面面面关系面关系1)、点、点点关系点关系 点和点之间的关系主要有两点（通过某条线）是否相连，两点之间点和点之间的关系主要有两点（通过某条线）是否相连，两点之间的距离是多少？如城市中某两个点之间可否有通路，距离是多少？的距离是多少？如城市中某两个点之间可否有通路，距离是多少？这是在实际生活中常见的点和点之间的空间关系问题。这是在实际生活中常见的点和点之间的空间关系问题。 2)、点、点线关系线

11、关系点和线的关系主要表现在点和线的关联关系上。如点是否位于线上，点和线的关系主要表现在点和线的关联关系上。如点是否位于线上，点和线之间的距离等等。点和线之间的距离等等。 3)、点、点面关系面关系点和面的关系主要表现在空间包含关系上。如某个村子是否位于某点和面的关系主要表现在空间包含关系上。如某个村子是否位于某个县内？或某个县共有多少个村子？个县内？或某个县共有多少个村子？ 4)、线、线线关系线关系线和线是否邻接、相交是线和线关系的主要表现形式。如河流和铁线和线是否邻接、相交是线和线关系的主要表现形式。如河流和铁路的相交，两条公路是否通过某个点邻接？路的相交，两条公路是否通过某个点邻接？ 5)、

12、线、线面关系面关系线和面的关系表现为线是否通过面或和面关联或包含在面之内？线和面的关系表现为线是否通过面或和面关联或包含在面之内？ 6)、面、面面关系面关系面和面之间的关系主要表现为邻接和包含的关系。面和面之间的关系主要表现为邻接和包含的关系。返返 回回流感病例区域流感病例在区内分布举例举例返返 回回举例举例返返 回回举例举例5 5 空间数据的拓扑关系的意义空间数据的拓扑关系的意义空间数据的拓扑关系，对数据处理和空间分析具有重要空间数据的拓扑关系，对数据处理和空间分析具有重要的意义，因为：的意义，因为： (1)(1)根据拓扑关系，不需要利用坐标或距离，可以根据拓扑关系，不需要利用坐标或距离，可

13、以确定一种空间实体相对于另一种空间实体的位置关系。确定一种空间实体相对于另一种空间实体的位置关系。拓扑关系能清楚地反映实体之间的逻辑结构关系，它比拓扑关系能清楚地反映实体之间的逻辑结构关系，它比几何数据有更大的稳定性，不随地图投影而变化。几何数据有更大的稳定性，不随地图投影而变化。 (2)(2)利用拓扑关系有利于空间要素的查询，例如某利用拓扑关系有利于空间要素的查询，例如某条铁路通过哪些地区，某县与哪些县邻接。又如分析某条铁路通过哪些地区，某县与哪些县邻接。又如分析某河流能为哪些地区的居民提供水源，某湖泊周围的土地河流能为哪些地区的居民提供水源，某湖泊周围的土地类型及对生物栖息环境作出评价等。

14、类型及对生物栖息环境作出评价等。 (3)可以根据拓扑关系重建地理实体。例如根据弧段构可以根据拓扑关系重建地理实体。例如根据弧段构建多边形，实现道路的选取，进行最佳路径的选择等。建多边形，实现道路的选取，进行最佳路径的选择等。 返返 回回引例：引例：1854年年8月到月到9月月 英国伦敦霍乱流行英国伦敦霍乱流行琼琼斯诺博士斯诺博士 把道路、房屋、饮用水机井、霍乱病死者居住位置把道路、房屋、饮用水机井、霍乱病死者居住位置在在1：6500的城区图上标出来的城区图上标出来霍乱病死者霍乱病死者居住位置居住位置问题？问题？集中钦用集中钦用“布洛多布洛多斯托斯托”水机井水机井水井水井返返 回回在这个例子中利

15、用了什么关系？水井水井在这个例子中，分析了患者的居住地与饮用水的空间位置关系。揭示了霍乱发病的传播途径。 1.数据结构数据结构即数据组织的形式，是适合于计算机存储、管理、处理的数据逻辑结构。换句话说，是指数据以什么形式在计算机中存储和处理。数据按一定的规律储存在计算机机中，是计算机正确处理和用户正确理解的保证。 2.空间数据结构空间数据结构是是指适合于计算机系统存储、管理和处理的地学图形的逻辑结构，是地理实体的空间排列方式和相互关系的抽象描述。即空间数据在计算机中的具体组织方式。一般来说，属性数据与其他信息系统一样常用二维关系表格形式存储。元数据以特定的空间元数据格式存储，而描述地理位置及其空

16、间关系的空间特征数据是地理信息系统所特有的数据类型，主要以矢量数据结构和栅格数据结构两种形式存储。目前尚无一种统一的数据结构能够同时存储上述各种类型的数据，而是将不同类型的空间数据以不同的数据结构存储。返返 回回矢量结构数据拓扑型数据实体型数据明确表示地理实体的空间关系栅格结构数据游程编码链式编码四叉树编码压缩编码方式的不同返返 回回矢量数据表示栅格数据表示返返 回回 栅格数据结构是栅格数据结构是最简单最直观的空间数据结构，又称为网格结构(raster或gridcell)或象元结构(pixel)，是指将地球表面划分为大小均匀紧密相邻的网格阵列，每个网格作为一个象元或象素,由行、列号定义，并包含

17、一个代码,表示该象素的属性类型或量值，或仅仅包含指向其属性记录的指针。因此，栅格数据结构是以规则的阵列阵列来表示空间地物或现象分布的数据组织，组织中的每个数据表示地物或现象的非几何属性特征。 返返 回回返返 回回栅格数据表示在栅格结构中点、线、面表示在栅格结构中点、线、面表示点点: :用一个栅格单元表示；用一个栅格单元表示；线线: :线状地物则用沿线走向的线状地物则用沿线走向的一组相邻栅格单元表示，一组相邻栅格单元表示，面面: :面面( (或区域或区域) )用记有区域属用记有区域属性的相邻栅格单元的集合表示，性的相邻栅格单元的集合表示，每个栅格单元可有多于两个的每个栅格单元可有多于两个的相邻单

18、元同属一个区域。相邻单元同属一个区域。 返返 回回返返 回回返返 回回返返 回回返返 回回AACCBCCCBDDCDDDD以占矩形区域面积以占矩形区域面积最大的地物类型或最大的地物类型或现象特性决定栅格现象特性决定栅格单元的代码。单元的代码。 显见C类地物所占面积最大返返 回回AACCBACCBDCCDDDD用处于栅格中心处用处于栅格中心处的地物类型或现象的地物类型或现象特性决定栅格代码特性决定栅格代码 中心点落在代码为 A类的地物范围内返返 回回AACCBCCBDCDDDD横线所占最长部分的属性值代码为 A类的地物返返 回回AACCBDCDDCDDDD假设图D类属性为最重要的地物类型，即D比

19、A、B和C类更为重要，则栅格单元的代码应为D返返 回回ACCCBCCBDCDDCC假设假设图中图中C C类类属性为最重属性为最重要的地物类型，要的地物类型，即C比A、B和D类属性更为重要，则栅格单元的代码应为C返返 回回游程编码栅格数据链式编码四叉树编码压缩编码直接栅格编码返返 回回v直接栅格编码是最简单直观而又非常重要的一种栅格结构编码方法，通常称这种编码的图像文件为网格文件或栅格文件。v栅格结构不论采用何种压缩编码方法，其逻辑原型都是直接编码网格文件。v直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行都从左到右逐个象元记录，也可以奇数行地从左到右而偶数行地从右向

20、左记录，为了特定目的还可采用其他特殊的顺序（图）。（一）直接栅格编码返返 回回举例：举例：数据矩阵用100个整数表示返返 回回返返 回回游程编码游程编码是栅格数据压缩的重要编码方法。它的基本思路基本思路是：对于一幅栅格图像，常常有行(或列)方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。其编码方案是，只在各行(或列)数据的代码发生变化时依次记录该代码以及相同代码重复的个数，从而实现数据的压缩。（二）游程编码（二）游程编码返返 回回游程游程：指相邻同属性值的连续网格视为一游程。指相邻同属性值的连续网格视为一游程。游程编码结构是逐将相邻同属性值的网格合并，并记录合并

21、后网格的值及网格的长度。根据每个游程数据结构（编码方式）的不同分为游程长游程长度编码和游程终止编码度编码和游程终止编码2228800058888770第一行：第一行：4个游程个游程第二行：第二行：3个游程个游程游程举例游程举例: :返返 回回游程编码游程编码其目的是栅格数据的数据量其目的是栅格数据的数据量, ,减少数减少数据间冗余据间冗余。建立方法：将栅格矩阵的数据序列x1, x2,xn映射为相应的二元组序列（Ai,li）,i=1,2, ,m（mn）, A为属性， l为游程，m为游程序号。v在游程长度编码中，在游程长度编码中，li表示游程的连续长度游程的连续长度；v和游程终止编码，和游程终止编

22、码，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个整数表

23、示可见游程长度编码压缩数据是十分有效又简便的返返 回回(0,7),(2,8),(0,10)(0,2),(2,6),(0,7),(3,9),(0,10)优点：优点：数据压缩率高，易于实现叠置，检索数据压缩率高，易于实现叠置，检索运算。运算。缺点：缺点：只考虑水平分解元素之间相关性而未考只考虑水平分解元素之间相关性而未考虑垂直分解元素之间相关性，又称一维虑垂直分解元素之间相关性，又称一维游程编码。游程编码。返返 回回（三）链式编码链式编码又称为弗里曼链码链式编码又称为弗里曼链码(Freeman(Freeman，1961)1961)或边或边界链码。链式编码主要是记录线状地物和面状地物界链码。链式编码

24、主要是记录线状地物和面状地物的边界。的边界。它把线状地物和面状地物的边界表示为：由某一起始点开始并按某些基本方向确定的单位矢量链。基本方向可定义为：东0，东南l，南2，西南3，西4，西北5，北6，东北7等八个基本方向（如图3-4所示）。10234567链式编码举例：32233233246676021起始点起始点如果对于图所示的线状地物确定其起始点为像元(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 链式编码的前两个数字表示起点的行、列

25、数，从第三个数字开始的每个数字表示单位矢量的方向，八个方向以07的整数代表.优缺点：优缺点： 数据压缩率强，便于计算长度，面积，数据压缩率强，便于计算长度，面积，便于表示图形凹凸部分，易于储存。便于表示图形凹凸部分，易于储存。但难于实现叠置运算，不便于合并插入操但难于实现叠置运算，不便于合并插入操作。作。适于对曲线和边界进行编码适于对曲线和边界进行编码（四）块状编码（四）块状编码以正方形区域为单元对块状地物的栅格以正方形区域为单元对块状地物的栅格数据进行编码，实质是把栅格阵列中同一属数据进行编码，实质是把栅格阵列中同一属性方形区域各元素映射成一个元素系列。性方形区域各元素映射成一个元素系列。编

26、码方式：（行号，列号，半径，代码）编码方式：（行号，列号，半径，代码）（四）块状编码及其举例块码是游程长度编码扩展到二维的情况，采用方形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置（行、列号）和半径，再加上记录单位的代码组成。(1,1,1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7), (1,6,2,7),(1,8,1,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),(2,1,1,4),(2

27、,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), (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),(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), (5,3,1,8),(5,4,2,8),(5,6,1,8),(5,7,1,7

28、),(5,8,1,8), (6,1,3,0),(6,6,3,8),(7,4,1,0),(7,5,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)(8,4,1,0),(8,5,1,0)。 对图所示图像的块码编码为：块码分割 0225555522222555000003332222335500233355003333530003333300003333（1 1，1 1，1 1，0 0），（），（1 1，2 2，2 2，2 2），），（1 1，4 4，1 1，5 5），（），（1 1，5 5，1 1，5 5），），（

29、1 1，6 6，2 2，5 5），（），（1 1，8 8，1 1，5 5）；）；（2 2，1 1，1 1，2 2），（），（2 2，4 4，1 1，2 2），），（2 2，5 5，1 1，2 2），（），（2 2，8 8，1 1，5 5）；）；（3 3，3 3，1 1，2 2），（），（3 3，4 4，1 1，2 2），），（3 3，5 5，2 2，3 3），（），（3 3，7 7，2 2，5 5）；）；（4 4，1 1，2 2，0 0），（），（4 4，3 3，1 1，2 2），），（4 4，4 4，1 1，3 3）；（）；（5 5，3 3，1 1，3 3），），（5 5，4 4，2 2，3

30、 3），（），（5 5，6 6，1 1，3 3），），（5 5，7 7，1 1，5 5），（），（5 5，8 8，1 1，3 3）；）；（6 6，1 1，3 3，0 0），（），（6 6，6 6，3 3，3 3）；）；（7 7，4 4，1 1，0 0），（），（7 7，5 5，1 1，3 3）；）；（8 8，4 4，1 1，0 0），（），（8 8，5 5，1 1，0 0）。）。（四）块状编码举例（四）块状编码举例特点：特点：1、面状地物所能包含的正文形越大，多边、面状地物所能包含的正文形越大，多边形边界越简单，块码编码效率超高；形边界越简单，块码编码效率超高；2、图形比较碎，多边形边界复杂的

31、图形，、图形比较碎，多边形边界复杂的图形，数据压缩率低；数据压缩率低；3、利于计算面积、合并插入等操作。、利于计算面积、合并插入等操作。返返 回回（五）四叉树编码 (quad-treecode)四又树结构的基本思想基本思想是将一幅栅格地图或图像等分为四部分。逐块检查其格网属性值(或灰度)。如果某个子区的所有格网值都具有相同的值。则这个子区就不再继续分割，否则还要把这个子区再分割成四个子区。这样依次地分割，直到每个子块都只含有相同的属性值或灰度为止。四叉树分割 四叉树分割 返返 回回NW 0 NE 1 SW 2 SE 3A122对一幅对一幅2N 2N的栅格阵列，最大深度为的栅格阵列，最大深度为N

32、，可能有的层次为可能有的层次为0，1，2，N，那么，每，那么，每层的栅格宽度为：层的栅格宽度为： 2（最大深度（最大深度-当前层次）当前层次）反映了所在叶结点表示的正方形集合的大小。反映了所在叶结点表示的正方形集合的大小。对于一个有2nX2n个像元的图像，可分的层数最多有n+1层（初始层为0层,最后一层为第n层，如下图是个8X8个像元组成的图像，可有3+1=4层。每一层不能分的块（即所有像元具有同一属性）称为叶结点，否则称为叉结点。叉结点和叶结点的位置由所在的层号及同一层所在的象限号唯一表示。象限号的排列见下图。因此编码时只要将每个叶结点的位置（层路径及象限号）和其属性记录下来即可。叶结点的包

33、含的像元越多，压缩的效率就越高。0123仍用上面的例子，对仍用上面的例子，对0 0层先做十字四分，显然，所分出的四块都不一致层先做十字四分，显然，所分出的四块都不一致（第一层），再四分，得到第二层。每个第一层中的第二层均有二块（第一层），再四分，得到第二层。每个第一层中的第二层均有二块或一块同质，它们可不再分形成叶结点，其余相异的块还可做第三次或一块同质，它们可不再分形成叶结点，其余相异的块还可做第三次也就是最后一次划分，得到第三层，第三层每块即为一个像元，划分也就是最后一次划分，得到第三层，第三层每块即为一个像元，划分结束。其过程用下图表示。结束。其过程用下图表示。MMRMMMMMMMRRM

34、RMMMRRRRRRMMRRRRRRMMRRRRRRMMRRRRRRMMMRRRRRMMMMRRMMM1234567812345678MMRMMMMMMMRRMRMMMRRRRRRMMRRRRRRMMRRRRRRMMRRRRRRMMMRRRRRMMMMRRMMM叉结点叶结点1234567812345678MMRMMMMMMMRRMRMMMRRRRRRMMRRRRRRMMRRRRRRMMRRRRRRMMMRRRRRMMMMRRMMM0 0层层1 1层层2 2层层3 3层层其编码步骤是：其编码步骤是：1.1.逐级十字四分区划逐级十字四分区划0 01 12 23 30 01 12 23 30 01

35、12 23 30 01 12 23 32. 2. 编码编码NW NW （0 0）NE NE （1 1）NW NW （2 2）SE SE （3 3）0 0层层1 1层层2 2层层3 3层层记录每个叶子结点的地址和属性。按下述记录每个叶子结点的地址和属性。按下述几种方法编码。几种方法编码。0 01 12 23 32020212122222323200200201201202202 203203 230230231231 2322322332331）.按层次和象限对叶结点直接编码（美国马里兰大学）按层次和象限对叶结点直接编码（美国马里兰大学）0 0层层1 1层层2 2层层3 3层层01232021

36、2223200201202 203230231 232233该方法用二进制（共32位）记录每个叶结点的地址和属性值，其中地址包括两个部分，即深度（层）和路径（所经过的层及其象限）。见下图。000001011000011属性编码属性编码 2222位位路径路径2n2n位位深度深度4 4位位1 1层层2 2象象限限2 2层层3 3象象限限3 3层层0 0象象限限第第3 3层层2）.基于四进制的四叉树编码基于四进制的四叉树编码四进制编码是用四进位表示各层叶结点的位置。编码采用自上而四进制编码是用四进位表示各层叶结点的位置。编码采用自上而下进行。其步骤是：下进行。其步骤是：（a）将各栅格点的生行列坐标用

37、二进制表示，见下图；）将各栅格点的生行列坐标用二进制表示，见下图；（b）将二进位换算成四进位，方法是：）将二进位换算成四进位，方法是：列行IIM 24如第如第4列（列（100）第）第3行（行（011）用四进制表）用四进制表示为示为2 x 011+100=122其反算规则是：其反算规则是：行行 0和和1 为为0 如如122 的行为的行为 011 2和和3 为为1列列 0和和2 为为0 如如122的列为的列为 100 1和和3 为为100000101001110010111011100000101001110010111011100000101001110010111011100000000110

38、0101001002003102103010020021030031130131011022023032033132133100200201210211300301101202203212213302303110220221230231330331111222223232233332334M4=2*I行+I列0000010100111001011101110000000011001010010020031021030100200210300311301310110220230320331321331002002012102113003011012022032122133023031102202

39、21230231330331111222223232233332334（c c）将每个叶结点换成四进制，它实际是叶结点的路径位置）将每个叶结点换成四进制，它实际是叶结点的路径位置（如下图），注意，各叶结点的四进位码的位数与其层次相同，（如下图），注意，各叶结点的四进位码的位数与其层次相同，例如，第二层的叶结点其位数为例如，第二层的叶结点其位数为2 2，如下图中的，如下图中的0000，1111，3030等。等。其数字由这个叶结点左上角的第一个像元的四制码取前其数字由这个叶结点左上角的第一个像元的四制码取前n(n(所在号所在号层）位得到，如第二层则取层）位得到，如第二层则取2 2位。位。MMRMM

40、MMMMMRRMRMMMRRRRRRMMRRRRRRMMRRRRRRMMRRRRRRMMMRRRRRMMMMRRMMM00012010011013100101102103110210230220200312302122232230231213202200201203132130131133312310311313322320321323332330331333（d）写成记录）写成记录位置码属性码00M010R011M012R013R3) .基于十进制的四叉树编码基于十进制的四叉树编码与四进位编码基本相同，其步骤是：与四进位编码基本相同，其步骤是：（a）与四进制类似，每个像元的行、列号用二进制表

41、示。）与四进制类似，每个像元的行、列号用二进制表示。（b）将行列号换算成十进制。二转十的方法是：）将行列号换算成十进制。二转十的方法是： 将每个像元的行、列号交叉排位，如将每个像元的行、列号交叉排位，如 行为行为 011， 列为列为 100，交，交叉排位后为叉排位后为011010。然后将此排位数换成。然后将此排位数换成10进位。即进位。即26202120212120012345（c）对每个叶结点编码，如叶结点包含多个像元，用此叶结点的）对每个叶结点编码，如叶结点包含多个像元，用此叶结点的左上角像元的十进位码，见下图左上角像元的十进位码，见下图0 1 1 0 1 0行号行号= 0 1 1100=

42、列号列号MMRMMMMMMMRRMRMMMRRRRRRMMRRRRRRMMRRRRRRMMRRRRRRMMMRRRRRMMMMRRMMM34340645716171819209111081224483640464445473233353028293154525355585657596260616334位置码属性码0M4R5M6R7R8M9R10M11R12R位置码属性码16M17M18M19R20M24R28R29M30R31M位置码属性码32M33R34M35R36R40M44R45R46M47R位置码属性码48R52R53M54R55M56R57R58R59M60R位置码属性码61M62M

43、63M（d）写成记录）写成记录（e）再进行游程编码）再进行游程编码即将上述记录中，属性相同且连续的记录合并，写成下列形式。即将上述记录中，属性相同且连续的记录合并，写成下列形式。此时原此时原43条记录变成条记录变成29条记录。条记录。位置码属性码0M4R5M6R8M9R10M11R位置码属性码16M19R20M24R29M30R31M位置码属性码33R34M35R40M44R46M47R位置码属性码53M54R55M56R59M60R位置码属性码61M图栅格单元的十进制的十进制的Morton码码图栅格单元的十进制的编码十进制的编码MMRMMMMMMMRRMRMMMRRRRRRMMRRRRRRM

44、MRRRRRRMMRRRRRRMMMRRRRRMMMMRRMMM34340645716171819209111081224483640464445473233353028293154525355585657596260616334举例举例: :十进制的十进制的MortonMorton码码1 1、一种按位操作的方法、一种按位操作的方法：如行为如行为2 2、列为、列为3 3的栅格的的栅格的MDMD步骤：步骤： (1)(1)行、列号为二进制行、列号为二进制 Ib= 1 0 JbIb= 1 0 Jb= 1 1= 1 1(2)I(2)I行行J J列交叉列交叉 1 1 0 1 = 131 1 0 1 =

45、13(3)(3)再化为十进制再化为十进制. . 实质上是按左上、右上、左下、右下的顺序，从零开始对实质上是按左上、右上、左下、右下的顺序，从零开始对每个栅格进行自然编码。每个栅格进行自然编码。 A0A1A4A5A2B3B6B7A8A9B12B13A10A11B14B15四进制四进制MortonMorton码直观上切合四叉树分割，但许多语言不支持四进制变量，需用十进码直观上切合四叉树分割，但许多语言不支持四进制变量，需用十进制表示制表示MortonMorton码码. .2 2、把一幅把一幅2 2n n2 2n n的图像压缩成线性四叉树的过程的图像压缩成线性四叉树的过程 1 1、按、按Morton

46、Morton码把图象读入一维数组。码把图象读入一维数组。 2 2、相邻的四个象元比较，一致的合并，只记录第一个象、相邻的四个象元比较，一致的合并，只记录第一个象元的元的MortonMorton码。循环比较所形成的大块，相同的再合并，直到码。循环比较所形成的大块，相同的再合并，直到不能合并为止。不能合并为止。 3 3、进一步用游程长度编码压缩。压缩时只记录第一个象、进一步用游程长度编码压缩。压缩时只记录第一个象元的元的Morton码。码。A0A1A4A5A2B3B6B7A8A9B12B13A10A11B14B15右图的压缩处理过程为：右图的压缩处理过程为：1、按、按Morton码读入一维数组。码

47、读入一维数组。 Morton码：码：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15象象 元元 值：值： A A A B A B B B A A A A B B B B2、四相邻象元合并，只记录第一个象元的、四相邻象元合并，只记录第一个象元的Morton码。码。 0 1 2 3 4 5 6 7 8 12 A A A B A A B B A B3、由于不能进一步合并，则用游程长度编码压缩。、由于不能进一步合并，则用游程长度编码压缩。 0 3 4 6 8 12 A B A B A B A0A1A4A5A2B3B6B7A8A9B12B13A10A11B14B15举例举例:

48、:十进制的十进制的MortonMorton码码这种从上而下的分割需要大量的运算，因为大量数据需要重复检查才能确定划分。当n*n的矩阵比较大，且区域内容要素又比较复杂时，建立这种四叉树的速度比较慢。 另一种是采用从下而上的方法建立。对栅格数据按如下的顺序进行检测。如果每相邻四个网格值相同则进行合并，逐次往上递归合并，直到符合四叉树的原则为止。这种方法重复计算较少，运算速度较快。 从图中可以看出，为了保证四叉树能不断的分解下去，要求图象必须为2n*2n的栅格阵列，n为极限分割次数，n+1是四叉树的最大高度或最大层数。对于非标准尺寸的图象需首先通过增加背景的方法将图象扩充为2n*2n的图象 .(问题

49、？）四叉树编码法有许多有趣的优点：容易而有效地计算多边形的数量特征；阵列各部分的分辨率是可变的，边界复杂部分四叉树较高即分级多，分辨率也高，而不需表示许多细节的部分则分级少，分辨率低，因而既可精确表示图形结构又可减少存贮量；栅格到四叉树及四叉树到简单栅格结构的转换比其它压缩方法容易；多边形中嵌套异类小多边形的表示较方便。 四叉树编码的最大缺点是转换的不定性，用同一形状和大小的多边形可能得出多种不同的四叉树结构，故不利于形状分析和模式识别。 四叉树编码的优缺点：四叉树编码的优缺点：四叉树结构按其编码的方法不同又分为常规四叉树和线性四叉树常规四叉树和线性四叉树 。常规四叉树常规四叉树除了记录叶结点

50、之外，还要记录中间结点。结点之间借助指针联系，每个结点需要用六个量表达：四个叶结点指针，一个父结点指针和一个结点的属性或灰度值。 线性四叉树线性四叉树则只存贮最后叶结点的信息。包括叶结点的位置、深度和本结点的属性或灰度值。所谓深度是指处于四叉树的第几层上。由深度可推知子区的大小。 线性四叉树叶结点的编号需要遵循一定的规则，这种编号称为地址码，它隐含了叶结点的位置和深度信息。最常用的地址码是四进制或十进制的Morton码。 栅格数据的获取栅格数据的获取1、目读法：适用于所选区域范围小，栅格、目读法：适用于所选区域范围小，栅格单元尺寸大的情况。单元尺寸大的情况。2、从扫描仪获取：高精度，快速度，数

51、据、从扫描仪获取：高精度，快速度，数据格式标准化。格式标准化。3、从摄像机获取：栅格元素数固定、从摄像机获取：栅格元素数固定 512512 102410244、从遥感中获取：周期性，动态性，可自、从遥感中获取：周期性，动态性，可自动提取专题信息。动提取专题信息。5、从矢量数据转换成栅格数据、从矢量数据转换成栅格数据返返 回回返返 回回 在地理系统中，由于空间数据代表着现实世界地理在地理系统中，由于空间数据代表着现实世界地理实体或现象在信息世界中的映射；因此它反映的特征实体或现象在信息世界中的映射；因此它反映的特征同样应包括自然界地理实体向人类传递的基本信息。同样应包括自然界地理实体向人类传递的

52、基本信息。栅格数据结构栅格数据结构矢量数据结构矢量数据结构主要有：主要有：返返 回回矢量数据拓扑型数据实体型数据明确表示地理实体的空间关系栅格数据游程编码链式编码四叉树编码压缩编码方式的不同返返 回回返返 回回矢量数据表示栅格数据表示返返 回回矢量数据拓扑型数据实体型数据明确表示地理实体的空间关系v矢量数据结构是利用欧几里得（Euclid）几何学中的点、线、面及其组合体来表示地理实体空间分布的一种数据组织方式。v这种数据组织方式能最好的逼近地理实体的空间分布特征，数据精度高。v矢量数据结构主要有以下几种数据类型：（1）、简单数据结构（2）、拓扑数据结构（3）、曲面数据结构返返 回回返返 回回返

53、返 回回实体型数据结构实体型数据结构（spaghetti）- 面条模型面条模型:以实体为以实体为单位记录其坐标单位记录其坐标缺点缺点： 1、相邻多边形的公共边界被数字化并存储两次，造成数据冗余和碎屑多边相邻多边形的公共边界被数字化并存储两次，造成数据冗余和碎屑多边形形数据不一致，浪费空间，导致双重边界不能精确匹配。数据不一致，浪费空间，导致双重边界不能精确匹配。2、自成体系，自成体系，缺少多边形的邻接信息，无拓扑关系缺少多边形的邻接信息，无拓扑关系，难以进行邻域处理，如消除多，难以进行邻域处理，如消除多边形公共边界，合并多边形。边形公共边界，合并多边形。3、岛作为一个单个图形，没有与外界多边形

54、联系。不易检查拓扑错误。岛作为一个单个图形，没有与外界多边形联系。不易检查拓扑错误。所以，这种结构只用于简单的制图系统中，显示图形。所以，这种结构只用于简单的制图系统中，显示图形。优点优点：结构简单、直观、易实现以实体：结构简单、直观、易实现以实体为单位的运算和显示。为单位的运算和显示。多边形坐标串P1P21234567891011 1213 1415P PP PP P返返 回回这种数据结构的主要特点是：v数据按点、线或多边形为单元进行组织。数据编排直观，数字化操作简单v每个多边形都以闭合线段存储，多边形的公共边界被数字化两次和存储两次。v点、线或多边形都有各自的坐标数据，但没有拓扑数据v岛只

55、作为一个单个的图形，没有与外界多边形的联系二、索引式（树状）二、索引式（树状）对所有点的坐标按顺序建坐标文件，再建点与边（线）、线与多边形的索引文件。对所有点的坐标按顺序建坐标文件，再建点与边（线）、线与多边形的索引文件。1234567891011 1213 1415P PP PP PMap1、点文件：、点文件：点号点号坐标坐标1x1,y1索引文件：索引文件：面号面号弧段号弧段号P1A,B,C3、面文件：、面文件：2、弧段文件、弧段文件: 弧段号弧段号起点起点终点终点点号点号A527,8,9,10与实体式相比与实体式相比：优点：优点：用建索引的方法消除多边形数据的冗余和不一致，邻接信息、岛用建

56、索引的方法消除多边形数据的冗余和不一致，邻接信息、岛信息可在多边形文件中通过是否公共弧段号的方式查询。信息可在多边形文件中通过是否公共弧段号的方式查询。缺点缺点：表达拓扑关系较繁琐，给相邻运算、消除无用边、处理岛信息、：表达拓扑关系较繁琐，给相邻运算、消除无用边、处理岛信息、检索拓扑关系等带来困难，以人工方式建立编码表，工作量大，易出错。检索拓扑关系等带来困难，以人工方式建立编码表，工作量大，易出错。三、双重独立式编码三、双重独立式编码简称简称DIME(Dual Independent Map Encoding)，是美国人口统计系统采用的，是美国人口统计系统采用的一种编码方式，是一种一种编码方

57、式，是一种拓扑拓扑编码结构。编码结构。 1、点文件、点文件点号点号坐标坐标1x1,y12、线文件、线文件: :线文件是以线文件是以线段线段为记录单位为记录单位 线号线号左多边形左多边形 右多边形右多边形 起点起点终点终点L210P1P22101234567891011 1213 1415P PP PP P3、面文件、面文件面号面号线号线号P1L210,L109关联关联邻接邻接关联关联连通连通拓扑关系明确拓扑关系明确在在DIMEDIME中做如下改进：中做如下改进： 将以将以线段线段为记录单位改为以为记录单位改为以弧段弧段为单位为单位链状双重独立式编码链状双重独立式编码四、四、链状双重独立式编码链

58、状双重独立式编码-拓扑数据结构拓扑数据结构 1、弧段坐标文件、弧段坐标文件：弧段号弧段号坐标系列（串坐标系列（串)Ax2,y2,X10,y102 2、弧段文件：链、弧段文件：链面，链面，链结点关系结点关系 弧段号弧段号 左多边形左多边形 右多边形右多边形 起点起点终点终点AP1P2251234567891011 1213 1415P PP PP P3、面文件、面文件面号面号弧段号弧段号 P1A,B,-C4 4、点拓扑文件、点拓扑文件： 结点结点链关系链关系 点号点号 弧段号弧段号 2A,B,D在拓扑结构中，多边形（面）的边界被分割成一系列的线在拓扑结构中，多边形（面）的边界被分割成一系列的线（

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

60、道）为研究对象的折线为研究对象，而应以整条弧段（某条街道）为研究对象. . 国际著名国际著名GIS软件平台开发商美国软件平台开发商美国ESRI公司的公司的ARCGIS产产品中的品中的COVERAGE数据模型就是采用链状双重独立编码数据模型就是采用链状双重独立编码数据结构的。数据结构的。返返 回回1多边形编辑返返 回回返返 回回v曲面是指连续分布现象的覆盖表面，具有这种覆盖表面的要素有地形、降水量、温度、磁场等。v表示和存储这些要素的基本要求是必须便于连续现象在任一点的内插计算，因些常采用不规则三角网来拟合连续分布现象的覆盖表面，称为TIN(TriangulatedIrregularNetwor