第二章空间数据结构与编码教案.doc

1第二章第二章空间数据结构与编码空间数据结构与编码学习目标学习目标 掌握地理空间数据的特征，了解 GIS 的数据源 理解 GIS 数据的测量尺度 理解拓扑的概念和意义 掌握地理空间数据的拓扑关系与表示 掌握栅格数据结构特点及其编码方法 掌握矢量数据结构特点及其编码方法 了解栅格与矢量数据之间得转化方法第一节第一节地理空间数据及其特征地理空间数据及其特征一、一、GISGIS 的空间数据的空间数据地理空间是指物质、能量、信息的形式与形态、结构过程、功能关系上的分布方式和格局及其在时间上的延续。地球表层构成了地理空间，表征地理空间内事物的数量、质量、分布、内在联系和变化规律的图形、图像、符号、文字和数据等统称为地理（空间）数据。地理数据是 GIS 的核心，也有人称它是 GIS 的血液，因为 GIS 操作对象是地理数据，因此设计和使用 GIS 的第一步工作就是根据系统的功能，获取所需要的地理数据，并创建地理空间数据库。GIS 中的数据来源和数据类型繁多，概括起来主要有以下几种类型：1.1.地图数据地图数据各种类型的地图（包括电子的与非电子的地图）都是对空间事物和现象的一种相似或抽象模拟，它有严密的数学基础，并经过制图综合，利用符号系统所表示出来的丰富地理内容，明晰的再现了客观实体的空间关系和要素之间的内在联系，所以地图是地理信息的主要载体，同时2也是地理信息系统最重要的信息源。2.2.遥感数据遥感数据各种遥感数据及其制成的图像资料（航片、卫片）包含着及其丰富的地理内容，尤其是先进的卫星遥感技术的广泛应用，能为地理信息系统提供源源不断的、现势性很强的数据。所以遥感数据是地理信息系统另一个重要的信息源。3.3.统计数据、实测数据及各种文字报告统计数据、实测数据及各种文字报告各种地理要素的统计数据、实验和各种观测数据、研究报告等，是地理信息系统不可缺少的重要或补充数据源。二、地理数据的基本特征二、地理数据的基本特征地理数据一般具有三个基本特征:1.1.空间特征空间特征空间特征又称定位特征或几何特征。数据的空间性是指这些数据反映现象的空间位置及空间位置关系。通常以坐标数据形式来表示空间位置，以拓扑关系来表示空间位置关系。2.2.属性特征属性特征数据的属性是指描述实体的特征，如实体的名称、类别、质量特征和数量特征等。属性数据本身属于非空间数据，但它是空间数据中的重要数据成分.3.3.时间特征时间特征空间数据的时间性是指空间数据的空间特征和属性特征随时间而变化。它们可以同时随时间变化，也可以分别独立随时间变化。实体随时间的变化具有周期性，其变化的周期有超短周期的、短期的、中期的和长期的。必须指出，随时间流逝留下的过时数据是重要的历史资料。空间特征是地理信息区别于其他信息的最重要的特征之一，地理信息的定位特征与时间过程相结合，大大提高了地理信息的应用价值。3三、地理空间数据类型三、地理空间数据类型空间数据记录的是空间实体的位置、拓扑关系和形态、大小等几何特征。表示地理要素的空间数据可分为如下七种不同类型：1.1.类型数据类型数据如居民点、交通线、土地类型分布等。2.2.面域数据面域数据多边形中心点、行政区域界限和行政单元等。3.3.网络数据网络数据如道路交叉点、街道和街区等。4.4.样本数据样本数据如气象站、航线和野外样方的分布区等。5.5.曲面数据曲面数据如高程点、等高线和等值区域。6.6.文本数据文本数据如地名、河流名和区域名称。7.7.符号数据符号数据如点状符号、线状符号和面状符号等。上述各种类型的空间数据都可以用点、线、面三种不同的图形来表示，并可分别采用平面坐标、地理坐标或网格法表示。图 22 显示的就是空间数据类型及其表示方法。四、数据的测量尺度四、数据的测量尺度测量就是根据一定的标准给特定现象赋值或打分。为了描述地理世界，对任何事物都要鉴别、分类和命名。他们所使用的参考标准或尺度是不同的。测量的尺度大致可以分成四个层次,由粗略到详细依次为：定定名量或类型、次序量、间隔量和比率量。名量或类型、次序量、间隔量和比率量。1.1.定名量定名量定性而非定量地对众多地理事物进行区分和标识，不能进行任何算术运算。定名量是对地理现象属性特征的分类描述，它是现象类型的测量尺度。2.2.次序量次序量通过排序来区分和标识地理现象的量称为次序量。它是按照地理数据的等级序列，由低到高（或由高到低）进一步细分的。序数值相互之间可以比较大小，但不能进行算术运算。它们能定性地说出它们的大与小，重要与次要等，但不能指出差别的具体数量。43.3.间隔量间隔量不参照某个固定点，而是按间隔表示相对位置的数。利用某种标准单位（可以是任意的）作为间隔量来表示不同的量，是一种较精确区分和标识地理现象的测量方法。间隔量比定名量和顺序量能提供更多、更准确的信息，但应用时要正确理解标准单位的特性和含义。譬如，不能说40比20暖一倍。4.4.比率量比率量比率量是间隔量的精确化。它提供的定量值是具有真零值而且测量单位的间隔是相等的数据，比率测量尺度与使用的测量单位无关。比率数据或间隔数据可以比较容易地转变成顺序或命名数据。而命名数据则很难转换成顺序、间隔数据或比率数据。由此可见，尽管命名数据或次序数据便于使用，便于理解，但有时不够精确，不能用于较高级的算术运算。而比率数据或间隔数据比较精确，便于计算机处理，但是在比较复杂的 GIS 应用中，往往上述几种测量尺度的数据均须用到。第二节第二节空间数据的拓扑关系空间数据的拓扑关系一、拓扑的概念和意义一、拓扑的概念和意义1.1.拓扑的概念拓扑的概念拓扑学是几何学的一个分支，它研究图形在连续变形下（拓扑变换）的那些不变的几何属性。组成一个图形的各元素（结点、弧段、面域）之间都存在着二元关系，即邻接关系和关联关系。在地图上这种关系可以借助图形来识别，而在计算机中这种关系需用拓扑关系加以定义。拓拓扑关系是明确定义空间结构关系的一种数学方法。扑关系是明确定义空间结构关系的一种数学方法。2.2.拓扑关系的重要意义拓扑关系的重要意义在地理信息系统中，空间数据的拓扑关系，对地理信息系统的数据处理和空间分析具有重要的意义，主要表现在如下三个方面：（1）根据拓扑关系可以确定地理实体间的相对空间位置，而无需利用坐标和距离（2）利用拓扑关系有利于空间要素的查询。5（3）可以利用拓扑数据重建地理事体。如建立封闭多边形，实现道路的选取，进行最佳路径的计算等。二、空间数据的拓扑关系二、空间数据的拓扑关系在地理信息系统中对于具用网状结构特征（如多边形）的地理要素，不仅要表示出要素的形状、大小、位置和属性信息，而且还要反映出要素之间的相互关系，即要表示出构成网状结构地理要素的结点、弧段和多边形之间的拓扑关系。空间数据的拓扑关系包括拓扑邻接、拓扑关联和拓扑包含三个方面。图 2-3 空间数据的拓扑关系1.1.拓扑邻接拓扑邻接拓扑邻接是指存在于空间图形的同类元素之间的拓扑关系，如多边形之间的邻接性，弧段之间的邻接性以及结点之间的邻接关系（连通性）。2.2.拓扑关联拓扑关联拓扑关联是指存在于空间图形的不同类元素之间的拓扑关系。3.3.拓扑包含拓扑包含拓扑包含是指存在于空间图形的同类但不同级的元素之间的拓扑关系。包含关系分简单包含、多层包含和等价包含三种形式。6三、拓扑结构的表达三、拓扑结构的表达各种类型的空间数据，都可以用点、线、面三种图形来表示。因此，结点、弧段和多边形之间的拓扑结构可用四个关系表达出来。以图 2-3为例，如表 2-1、表 2-2、表 2-3 和表 2-4 所示。表 2-2弧段与结点的拓扑关系弧段结点始结点终结点e1e2e3N2N3N1N1N2N3表 2-1结点与弧段的拓扑关系结点弧段N1N2N3e1,e3,e6e1,e2,e5e2,e3,e4表 2-3弧段与多边形的拓扑关系弧段多 边 形左多边形右多边形e1e2e3P0P0P0P1P2P1表 2-4多边形与弧段的拓扑关系多 边 形弧段P1P2P3e1,e6,e5e2,e4,-e5e3,-e4,-e67第三节第三节空间数据结构空间数据结构一、空间数据结构的概念和类型一、空间数据结构的概念和类型空间数据结构空间数据结构也称为图形数据格式，是指适用于计算机系统存贮、管理和处理的地理图形数据的逻辑结构，是地理实体的空间排列方式和相互关系的抽象描述。在地理信息系统中，常用的空间数据结构有两种，即栅格数据结构和矢量数据结构。在矢量表示中，曲线是由一系列带有 x，y 坐标的特征点所组成的一条近似折线来表示。而在栅格形式中则借助于把该线通过的按行和列(矩阵形式)作为规则划分的栅格中的每个小格(像元)标以数字或代码来表示。这两种不同形式的数据被称为计算机的两种兼容数据。这是因为计算机不仅能存贮、识别和处理它们，而且可以对它们进行互相转换。图 25同一条曲线的矢量与栅格表示法二、矢量数据结构二、矢量数据结构1.1.定义定义矢量结构是通过记录坐标的形式来表示点、线、面(多边形)等地理实体。8矢量数据结构能最好的逼近地理实体的空间分布特征，数据精度高，数据存储的冗余度低，便于进行地理实体的网络分析，但对多层空间数据的叠合分析比较困难。对于点实体，对于点实体，在矢量结构中只记录点位的坐标和属性代码。对于线实体，对于线实体，可以用一系列足够短的直线段首位相连来表示一条曲线。在矢量结构中只记录小线段的端点坐标。因此，一条曲线实际上是有一个坐标系列来表示的。对于多边形对于多边形，在地理信息系统中是指一个任意形状、边界完全闭合的空间区域。之所以把这样的闭合区域称为多边形是由于区域的边界线同线实体一样，可以被看作是有一系列微小直线段组成，每个小线段作为这个区域的一条边，因此，这种区域就可以看作是有这些边组成的多边形了。所以多边形的矢量数据可以由组成这个多边形的小线段的坐标系列来表示。2.2.特点特点矢量结构的特点是：定位明显、属性隐含。这种特点使得其图形运算的算法总体上比栅格数据复杂得多，但在计算长度、面积、形状和图形编辑、几何变换操作中，矢量结构有很高的效率和精度，而在叠加运算、邻域搜索等操作时，则比较困难。3.3.矢量数据的获取矢量数据的获取（1）手工数字化法:（2）手扶跟踪数字化法：（3）数据结构转换法：三、栅格数据结构三、栅格数据结构1.1.定义定义栅格结构是一种简单直观的空间数据结构，又称网格结构或像元结构，是将地球表面划分为大小相等的网格阵列，每个网格作为一个像元或像素由行、列定义，并包含一个代码表示该像素的属性类型或量值，或仅仅包含指向其属性记录的指针。因此，栅格数据是以规则的阵列来表示空间地物或现象分布的数据组织，组织中的每个数据表示地理要素9的非几何属性特征如图 2-6 所示。图 26 物体的栅格表示（1）点状物体 在栅格数据中，借助于在其中心点处的单独像元来表示。（2）面状物体 借助于为其所覆盖的像元的集合来表示（如森林）。（3）线状物体 借助于其中心轴线上的像元来表示。2.2.特点特点栅格结构的显著特点是：属性明显，定位隐含，即数据直接记录属性的指针或属性本身，而所在位置则根据行列号转换为相应的坐标给出，由于栅格行列阵列容易为计算机存贮、操作和显示、因此，这种结构容易实现，算法简单，且易于扩充、修改，也很直观，特别是易于同遥感影像的结合处理，给地理空间数据处理带来了极大的方便。栅格数据的比例尺就是栅格大小与地表相应单元格大小之比。其表示地物的精度取决于栅格尺寸的大小。3 3栅格数据的获取栅格数据的获取栅格数据的获取，主要通过以下四种方法得到:（1）手工网格法：（2）扫描数字化法：（3）分类影像输入法：10（4）数据结构转换法：4.4.提高栅格数据精度的方法提高栅格数据精度的方法在栅格结构数据获取过程中，应尽可能保持原图或原始数据的精度，为减少信息损失提高精度，通常采取两种方法：（1）决定栅格代码的方式：在决定栅格代码时，尽量保持地表的真实性，保证最大的信息量。对于一个栅格单元中含有两个或两个以上地物类型时，可根据需要，选用如下方案之一决定该栅格单元的代码：.中心点法：面积占优法：在图 27 中，B 类地物所占面积最大，故应取栅格代码为 B。图 27 栅格单元代码的确定 长度占优法：重要性法：（2）缩小栅格单元的面积：即增加栅格单元的总数，行列数也相应的增加。第四节第四节矢量结构与栅格结构的比较及转换矢量结构与栅格结构的比较及转换一、栅格结构与矢量结构的比较一、栅格结构与矢量结构的比较栅格结构与矢量结构是 GIS 中常用的两种数据结构，栅格结构“属性明显，位置隐含”。而矢量结构“位置明显，属性隐含”，矢量结构与栅格结构各有不同的优点和缺点，两者的比较如表 25 所示。11表 25矢量结构与栅格结构的比较数据结构优点缺点矢量数据结构1.便于面向对象的数字表示2.数据结构紧凑、冗余度低3.有利于网络与检索分析4.图形显示质量好、精度高1.数据结构复杂2.多边形叠加分析比较困难3.缺乏同遥感数据及数字地形模型结合的能力栅格数据结构1.数据结构简单2.便于空间分析和地理现象的模拟3.易于遥感数据结合1.图形.数据量大2.投影转换比较困难3.图形显示质量差4.不易表示空间的拓扑关系二、矢量数据与栅格数据的相互转换二、矢量数据与栅格数据的相互转换1.1.矢量数据向栅格数据的转换矢量数据向栅格数据的转换（1）确定栅格单元的大小栅格单元的大小就是它的分辨率，应根据原图的精度，变换后的用途及存储空间等因素予以决定。栅格单元的边长在 X，Y 坐标系中的大小用X 和Y 表示。设 Xmax、Xmin 和 Ymax、Ymin 分别表示全图 X坐标和 Y 坐标的最大值与最小值，I，J 表示全图格网的行数和列数如图 2-8 图所示。它们之间的关系为：YmaxxXmaxminXYJyIminX(0,0)Y图 2-8两种坐标关系12X=（Xmax-Xmin）/JY=（Ymax-Ymin）/I这里 I 和 J 可以由原地图比例尺根据地图对应的地面长宽和网格分辨率相除求得，并取整数。（2）点的栅格化点的变换只要这个点落在某一个栅格中，就属于那个栅格单元，其行、列号 I、J 可由下式求出：I=1+INT（Ymax-Y）/YJ=1+INT（X-Xmin）/X式中 INT 表示取整函数。栅格点的值用点的属性表示。（3）线的栅格化图 2-9线的转换如图 2-9 所示，设两个端点的行、列号已经求出，其行号为 3 和 7，则中间网格的行号必为 4、5、6。其网格中心线的 Y 坐标应为：Yi=Ymax-Y(I-1/2)而与直线段交点的 X 坐标为：Xi=(X2-X1)/(Y2-Y1)(Yi-Y1)+X153467Y)(X2,XY12),(X1Y13（4）多边形（面域）栅格化.左码记录法：要完成面域的栅格化，其首要前提是实现以多边形线段反映其周围面域的属性特征。目前一般采用的是左码记录法。其原理是：如图 210 所示，有一闭合多边形，它将整个矩形面域分割成属性为 1 和 0 的两部分。如果在矢量数字化取数时，没有在数字化点的属性码中反映面域属性差异状况，转换的第一步工作即是要实现这个目标。图 2-10闭合多边形第一步，从数字化数据的第一点开始依次记录每一点左边面域的属性值（面域外为 0，面域内为 1）。记录方法可由计算机自动完成，这样，每一个多边形数字化点便实现了“三值化”，即坐标值、线段自身属性值及左侧面域属性值。第二步，对多边形每一条边，按以上所述的线段栅格化的方法进行转换，得到如图 211 所示的数据组成。图 211 多边形矢量结构向栅格结构转换第三步，节点处理，使节点的栅格值惟一而准确。14第四步，排序，从第一行起逐行按列的先后顺序排序，这时，所得到的数据结构完全等同于栅格数据压缩编码的数据结构形式。最后，展开为全栅格数据结构，完成由矢量数据系统向栅格数据系统转换如图 212 所示。图 2-12全栅格数据结构.部点扩散算法：.射线算法：由待判点向图外某点引射线，判断该射线与某多边形所有边界相交的总次数，如果相交偶数次，则待判点在该多边形外部，如为奇数次，则待判点在该多边形内部如图 2-13 所示。图 2-13 射线算法扫描算法：2.2.栅格数据向矢量数据的转换栅格数据向矢量数据的转换栅格数据向矢量数据转换通常包括以下四个基本步骤：多边形边界提取n=0内部点外部点n=2n=1n=3n=4n交点个数15采用高通滤波将栅格图像二值化，并经过细化标识边界点，如图 214 所示二值化。线划图形扫描后产生栅格数据，这些数据是按从 0255的灰度值量度的，设以 G（i，j）表示，为了将这种 256 或 128 级不同的灰阶压缩到 2 两个灰阶，即 0 和 1 两级，首先要在最大和最小灰阶之间定义一个阙值，设阙值为 T，则如果 G（i，j）大于等于 T，则记此栅格的值为 1。如果 G（i，j）小于 T 则记此栅格的值为 0，得到一幅二值图，如图 214（a）。（a）(b)(c)(d)图 214栅格矢量转换过程细化。细化是消除线划横断面栅格数的差异，使得每一条线只保留代表其轴线或周围轮廓线（对面状符号而言）位置的单个栅格的宽度，对于栅格线划的“细化”方法，可分为“剥皮法”和“骨架法”两大类。剥皮法的实质是从曲线的边缘开始，每次剥掉等于一个栅格宽的一层，直到最后留下彼此连通的由栅格点组成的图形。因为一条线在不同位置可能有不同的宽度，故在剥皮过程中必须注意一个条件，即不允许剥去会导致曲线不连通的栅格。这是这一方法的关键所在。其解决方法是，借助一个在计算机中存储的，由待剥栅格为中心的 33 栅格组合图（图215）来决定。16图 215栅格组合图如图 215 所示，一个 33 的栅格窗口，其中心栅格有八邻域，因此组合图共有 28 种不同的排列方式，若将相对位置关系的差异只是转置 900，1800，2700。或互为镜象发射的方法进行归并，则共有 51种排列格式。显然，其中只有格式 2，3，4，5，10，11，12，16，21，24，28，33，34，35，38，42，43，46 和 50，可以将中心点剥去。这样，通过最多核查 2568 个栅格，便可确定中间栅格点保留或删除，直到最后得到经细化处理后应予保留的栅格系列（图 214（c），并写入数据文件。边界线追踪边界线跟踪的目的就是将写入数据文件的细化处理后的栅格数据，整理为从结点出发的线段或闭合的线条，并以矢量形式存储于特征栅格点中心的坐标图 214（d）。跟踪时，从图幅西北角开始，按顺时针或逆时针方向，从起始点开始，根据八个邻域进行搜索，依次跟踪相邻点。并记录结点坐标，然后搜索闭曲线，直到完成全部栅格数据的矢量化，写入矢量数据库。拓扑关系生成对于矢量表示的边界弧段，判断其与原图上各多边形空间关系，形成完整的拓扑结构，并建立与属性数据的联系。去除多余点及曲线圆滑由于搜索是逐个栅格进行的，必须去除由此造成的多余点记录，以17减少冗余。搜索结果曲线由于栅格精度的限制，可能不够圆滑，需要采用一定的插补算法进行光滑处理。常用的算法有线性叠代法、分段三次多项式插值法、正轴抛物线平均加权法、斜轴抛物线平均加权法、样条函数插值法等。值得注意的是，无论采用哪种转换方法，转换的结果都会程度不同的引起原始信息的损失。三、矢量与栅格一体化三、矢量与栅格一体化矢量栅格一体化，对于提高 GIS 的空间分辨率、数据压缩和增强系统分析、输入输出的灵活性十分重要。1.1.传统的矢量与栅格一体化方案传统的矢量与栅格一体化方案栅格结构和矢量结构在表示空间数据上是同样有效的，栅格结构与矢量结构相结合是较为理想的方案，用计算机程序实现两种结构的高效转换。由程序自动根据操作需要选取合适的结构，以获取最强的分析能力和时间效率，用户不必介入结构类型的选择。2.2.矢量与栅格一体化数据结构矢量与栅格一体化数据结构新一代的集成化地理信息系统，要求能够统一管理图形数据、属性数据、影像数据和数字高程模型（DEM）数据，称为四库合一。图形数据与属性数据的统一管理，近年来已取得突破性的进展，通过空间数据库引擎（SDE），初步解决了图形数据与属性数据的一体化管理。而矢量与栅格数据按传统的观念，认为是两类完全不同性质的数据结构。当利用它们来表达空间目标时，对于线状实体，习惯使用矢量数据结构。对于面状实体，在基于矢量的 GIS 中，主要使用边界表达法，而在基于栅格的 GIS 中，一般用元子空间填充表达法。由此，人们联想到对于用矢量方法表示的线状实体，是不是也可以采用元子空间填充法来表示，即在数字化一个线状实体时，除记录原始采样点外，还记录所通过的栅格。同样，每个面状地物除记录它的多边形边界外，还记录中间包含的栅格。这样，既保持了矢量特性，又具有栅格的性质，就能将矢量与栅格统一起来，这就是矢量与栅格一体化数据结构的基本内涵。为了建立矢量与栅格一体化数据结构，要对点、线、面目标数据结18构的存储作如下统一约定：（1）对点状目标，因为没有形状和面积，在计算机内部只需要表示该点的一个位置数据及与结点关联的弧段信息。（2）对线状目标，它有形状但没有面积，在计算机内部需用一组元子来填满整个路径，并表示该弧段相关的拓扑信息。（3）对面状目标，它既有形状，又有面积，在计算机内部需表示由元子填满路径的一组边界和由边界组成的紧凑空间。由于栅格数据结构的精度较低，需利用细分格网的方法，来提高点、线和面状目标边界线的数据表达精度。如在有点、线目标通过的基本格网内，在细分成 256256 个细格网。当精度要求较低时，也可以细分成 1616 个细格网。第五节第五节空间数据的编码方法空间数据的编码方法一、编码的概念和意义一、编码的概念和意义空间数据编码空间数据编码，是根据 GIS 的目的和任务，把地图、图像等资料按一定数据结构转化为适于计算机存贮和处理的数据过程。空间数据的编码是地理信息系统设计中最重要的技术步骤，它表现由现实世界到数据世界之间的接口，是联接从现实世界到数据世界的纽带。如图 216 所示。图 2-16现实世界与数据世界之间的联点二、栅格数据编码方法二、栅格数据编码方法1 1直接栅格编码直接栅格编码直接栅格编码是最简单直观而又非常重要的一种栅格结构编码方法，直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个19记录代码，可以每行从左到右逐像元记录，也可奇数行从左到右而偶数行由右向左记录，为了特定的目的还可采用其他特殊的顺序。图 2-17多边形的网格2 2链码链码链码又称弗里曼链码（Freeman）或边界链码，它将线状地物或区域边界，由起点和一系列在基本方向上的单位矢量给出每个后续点相对应其前继点的可能的 8 个基本方向之一表示，单位矢量的长度默认为一个栅格像元。如图 218 所示，(a)(b)图 218链码的表示方法链码可以有效地压缩栅格数据，而且对于估算面积、长度、转折方向的凹凸度等运算十分方便，比较适宜存贮图形数据。缺点是对边界合并、插入等修改编辑工作比较困难，对局部的修改将改变整体结构，效率低下，而且由于链码以每个区域为单位存贮边界，相邻区域的边界将20被重复存贮而产生冗余。图 2-19线的网格3 3游程编码游程编码游程编码的基本思路是：对于一幅栅格图像，常常有行（或列）方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容，其方法有两种方案。一种编码方案一种编码方案是，只在各行（或列）数据的代码发生变化时依次记录该代码以及相同代码重复的个数，从而实现数据的压缩。如图 217 所示栅格数据，可沿行方向进行游程长度编码：（0，1），（2，2），（5，5）；（2，5），（5，3）；（2，4），（3，2），（5，2）；（0，2），（2，1），（3，3），（5，2）；（0，2），（3，4），（5，1），（3，1）；（0，3），（3，5）；（0，4），（3，4）；（0，5），（3，3）。另一种游程长度编码方案另一种游程长度编码方案是，逐个记录各行（或列）代码发生变化的位置和相应代码，如图 214 所示，沿列方向游程长度编码如下：21（1，0），（2，2），（4，0）；（1，2），（4，0）；（1，2），（5，3），（6，0）；（1，5），（2，2），（4，3），（7，0）；（1，5），（2，2），（3，3），（8，0）；（1，5），（3，3）；（1，5），（6，3）；（1，5），（5，3）。游程长度编码是栅格数据压缩的重要编码方法。在栅格加密时，这种编码数量没有明显增加，压缩效率较高，且易于检索、叠加合并等操作，运算简单，适用于计算机存贮。4.4.块码块码块码是游程长度编码扩展到二维的情况，采用方形区域作为纪录单元每个记录单元包括相邻的若干栅格，数据编码由初始位置行列号加上半径，再加上记录单元的代码组成。如图 220 是图 217 的块码分解图，其块码表示如下：（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，1，1，2），（3，2，1，2），（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）。22图 2-20 块码的单元分解5 5四叉树编码四叉树编码四叉树又称四元树或四分树，是根据栅格数据二维空间分布的特点，将空间区域按照 4 个象限进行递归分割（2n2n，且 n1）,直到子象限的数值单调为止，最后得到一棵四分叉的倒向树。也就是说将栅格区域划分为 4 个象限，其终止的依据是，不管是哪一层的象限，只要划分到仅代表一种地物或符合既定要求的少数几种地物时，则不在继续划分，否则一直划分到单个栅格单元为止。四叉树中象限的大小不一，位于高层次的象限较大，深度小，即分解次数少，而低层次上的象限较小，但深度大即分解的次数多。正是由于四叉树编码能够自动依照图形变化而调整象限尺寸，因此，它具有极高的压缩效率，是最有效的栅格压缩编码方法之一。23图 2-18四叉树分解为了保证四叉树分解能不断地进行下去，要求图像必须为 2n2n的栅格阵列。n 为极限分割次数，n1 是四叉树最大层数或最大高度，图222 为 2323的栅格，所以最多划分三次，最大层次为 4，对于不标准尺寸的图像，需通过增加背景的方法将图像扩充为 2n2n的标准栅格图像。为了使计算机能以最小的冗余存贮图像对应的四叉树，又能方便地完成各种图形图像操作，下面介绍美国马里兰大学地理信息系统中采用的编码方式。该方法记录每个叶子结点的地址和值，值就是子区的代码，其中地址包括两部分共 32 位（二进制，最右边 4 位记录该叶子结点的深度，即处于四叉树的第几层上，有了深度可以推知子区的大小；地址由从根结点到该叶子结点的路径表示；SW、SE、NW、NE 分别用 0，1，2，3 表示，从右边第 5 位开始用 2n 位记录这些方向路径。如图 213 所示的第 5 个结点深度为 3。第一层处于 SW 象限，记为 0；第二层处于 NE 象限，记为 3；第三层处于 SE 象限，记为 1。每层象限位置由两位二进制数表示，共 6 位。这样，记录了各个叶子的地址，再记上相应的代码值，就记录了整个图像，并可在此编码基础上进行多种图像操作。事实上叶子结点的地址可以直接由子区左下角24的行列坐标，按二进制按位交错得到。如对于 5 号叶子结点，在以图像左下角为原点的行列坐标中，其左下角行、列坐标为（2，3），表示为二进制分别为 010 和 011，按位交错就是 001101，正是 5 号方块。图 2-22四叉树表示四叉树编码具有可变的分辨率，并且有区域性质，压缩数据灵活，许多运算可以在编码数据上直接实现，大大提高了运算效率，是优秀的栅格压缩编码之一。四叉树编码最大的问题就是树状表示具有可变性，相同形状、大小的两个区域可能表示为截然不同的结构，故形态分析和模式识别比较困难，难以设计统一的算法。以上介绍了五种编码方法，直接栅格编码简单直观，是压缩编码方法的逻辑原型（栅格文件）；链码的压缩效率较高，已接近矢量结构，对边界的运算比较方便，但不具有区域性质，区域运算较难；游程长度编码在很大程度上压缩数据，又最大限度地保留了原始栅格结构，编码解码十分容易，十分适合于微机地理信息系统采用；块码和四叉数编码具有区域性质，又具有可变的分辨率，有较高的压缩效率，四叉数编码可以直接进行大量图形图像运算，效率较高，是很有前途的编码方法。总之，各种栅格数据编码方法各有其优缺点，在实际应用中，要根据具体25图件情况及要求，选择适当的编码方法。三、矢量数据编码方法三、矢量数据编码方法1.1.点实体矢量编码方法点实体矢量编码方法点实体矢量编码比较简单，只是将空间信息和属性信息记录完全就可以了。图 2-23 表示了点的矢量编码的基本内容：其他非几何属性线交汇角线指针符号点 结文本字体朝向比例字符文本点朝向比例符号简单点的属性建立和显示数据库联系x，y坐标列号类别或序结点文本点简单点点类型统一标识符图 2-23点实体的编码2.2.线实体矢量编码方法线实体矢量编码方法线实体主要用来表示线状地物其矢量内容为：惟一标识码；线标识码；起始点；终止点；坐标对序列；显示信息；非几何属性。惟一标识码是指系统排列的序号；线标识是指标识线的类型；起始点和终止点可以用点号或直接用坐标表示；坐标对序列是指坐标对的排列顺序；显示信息是指显示符号或文本等；非几何属性是指与线相联系的属性数据，可以直接存贮于线文件中，也可以单独存贮，由标识码联接查找。3.3.多边形矢量编码方法多边形矢量编码方法26（1 1）多边形环路法）多边形环路法多边形环路法又叫坐标序列法（Spaghetti 方式）或独立实体法，即每个多边形的编码与存贮毫不顾及相邻的多边形，由多边形边界的 x，y坐标对集合及说明信息组成，是最简单的一种多边形矢量编码。如图 224 所示图 2-24矢量编码示例五个多边形 P1、P2、P3、P4、P5可记录为以下坐标文件：P1x1，y1；x2，y2；x3，y3；x4，y4；x5，y5；x6，y6；x7，y7；x8，y8；x9，y9；P2x1，y1；x10，y10；x11，y11；x12，y12；x13，y13；x14，y14；x15，y15；x16，y16；x17，y17；x18，y18；x19，y19；x20，y20；x8，y8；x9，y9；P3x29，y29；x30，y30；x31，y31；x32，y32；x33，y33；x34，y34；x35，y35；P4x17，y17；x18，y18；x19，y19；x23，y23；x24，y24；x25，y25；x26，y26；x27，y27；x28，y28；P5x19，y19；x20，y20；x8，y8；x7，y7；x6，y6；x21，y21；x22，y22；x23，y23。多边形环路法文件结构简单，易于实现多边形为单位的运算和显27示。这种方法的缺点主要是：多边形之间公共边界被数字化和存贮两次，由此产生数据冗余和图形裂隙或重叠；（2 2）树状索引编码法）树状索引编码法本法采用树状索引以减少数据冗余并间接增加邻域信息，方法是对所有边界点进行数字化，将坐标对以顺序方式存贮，由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状索引结构。图 225 和图 226 分别为图 224 的多边形线和点树状索引示意图。图 2-25线与多边形之间树状索引图 2-26点与边界之间的树状索引以上树状索引示意图的文件结构如下：28点文件点号坐标1x1，y12x2，y235x35，y35线文件线号起点终点点号161，2，3，4，5，6；686，7，8；293529，30，31，32，33，34，35。多边形文件多边形号边界线号1，；2，；3；4，；5，；树状索引编码消除了相邻多边形边界的数据冗余和不一致的问题，可以简化过于复杂的边界线或合并相邻多边形，邻域信息和岛状信息可以通过对多边形文件的线索引处理得到，但比较繁琐，因而给邻域函数运算、消除无用边、处理岛状信息以及检查拓扑关系带来一定困难，而且两个编码表都需要人工方式建立，工作量大且容易出错。（3）拓扑结构编码法拓扑结构一般应包括如下内容：惟一标识，外包多边形指针，邻接多边形指针，边界链表，范围（最大和最小 x，y 坐标值）。拓扑结构可以在用户将多边形边界数字化后由程序自动搜索建立，与非几何属性的29联系通过数字化每个多边形一个内部点建立，也可以由用户在数字化的同时输入部分信息，如输入多边形组成的编号，边界链交点的序号，边界链的左右多边形编号等标识信息。采用拓扑结构编码可以较好地解决空间关系查询等问题。但增加了算法的复杂性和数据库的大小。矢量编码最重要的是信息的完整性和运算的灵活性，这是由矢量结构自身特点决定的，目前矢量编码尚无统一的最佳编码方法，在具体工作中应根据数据的特点和任务的要求灵活设计。