第三章空间数据结构 数据结构即指数据组织的形式,是适合于计算机存储、管理和处理的数据逻辑结构。对 空间数据则是地理实体的空间排列方式和相互关系的抽象描述。它是对数据的一种理解和解 释,不说明数据结构的数据是毫无用处的,不仅用户无法理解,计算机程序也不能正确的处 理,对同样一组数据,按不同的数据结构去处理,得到的可能是截然不同的内容。空间数据 结构是地理信息系统沟通信息的桥梁,只有充分理解地理信息系统所采用的特定数据结构, 才能正确有效地使用系统。 地理信息系统的空间数据结构主要有栅格结构和矢量结构 第一节栅格数据结构 简单柵格数据结构 栅格结构是最简单最直观的空间数据结构,又称为网格结构( raster或 grid cel)或象元结构 ( pixel),是指将地球表面划分为大小均匀紧密相邻的网格阵列,每个网格作为一个象元或象素 由行、列号定义,并包含一个代码,表示该象素的属性类型或量值,或仅仅包含指向其属性记 录的指针。因此,栅格结构是以规则的阵列来表示空间地物或现象分布的数据组织,组织中 的每个数据表示地物或现象的非几何属性特征。 在栅格结构中,点用一个栅格单元表示:线状地物则用沿线走向的一组相邻栅格单元表示 每个栅格单元最多只有两个相邻单元在线上:面或区域用记有区域属性的相邻栅格单元的集 合表示,每个栅格单元可有多于两个的相邻单元同属一个区域。任何以面状分布的对象(土地 利用、土壤类型、地势起伏、环境污染等),都可以用栅格数据逼近。遥感影像就属于典型的 栅格结构,每个象元的数字表示影像的灰度等级 栅格结构的显著特点是:属性明显,定位隐含,即数据直接记录属性的指针或属性本身 而所在位置则根据行列号转换为相应的坐标给出,也就是说定位是根据数据在数据集中的位 置得到的。由于栅格结构是按一定的规则排列的,所表示的实体的位置很容易隐含在网格文 件的存贮结构中,在后面讲述柵格结构编码时可以看到,每个存贮单元的行列位置可以方便 地根据其在文件中的记录位置得到,且行列坐标可以很容易地转为其他坐标系下的坐标 在网格文件中每个代码本身明确地代表了实体的属性或属性的编码,如果为属性的编码,则 该编码可作为指向实体属性表的指针。由于栅格行列阵列容易为计算机存储、操作和显示
31 第三章 空间数据结构 数据结构即指数据组织的形式，是适合于计算机存储、管理和处理的数据逻辑结构。对 空间数据则是地理实体的空间排列方式和相互关系的抽象描述。它是对数据的一种理解和解 释，不说明数据结构的数据是毫无用处的，不仅用户无法理解，计算机程序也不能正确的处 理，对同样一组数据，按不同的数据结构去处理，得到的可能是截然不同的内容。空间数据 结构是地理信息系统沟通信息的桥梁，只有充分理解地理信息系统所采用的特定数据结构， 才能正确有效地使用系统。 地理信息系统的空间数据结构主要有栅格结构和矢量结构。 第一节 栅格数据结构 一 、简单栅格数据结构 栅格结构是最简单最直观的空间数据结构，又称为网格结构(raster 或 grid cell)或象元结构 (pixel)，是指将地球表面划分为大小均匀紧密相邻的网格阵列，每个网格作为一个象元或象素, 由行、列号定义，并包含一个代码,表示该象素的属性类型或量值，或仅仅包含指向其属性记 录的指针。因此，栅格结构是以规则的阵列来表示空间地物或现象分布的数据组织，组织中 的每个数据表示地物或现象的非几何属性特征。 在栅格结构中，点用一个栅格单元表示；线状地物则用沿线走向的一组相邻栅格单元表示， 每个栅格单元最多只有两个相邻单元在线上；面或区域用记有区域属性的相邻栅格单元的集 合表示，每个栅格单元可有多于两个的相邻单元同属一个区域。任何以面状分布的对象(土地 利用、土壤类型、地势起伏、环境污染等)，都可以用栅格数据逼近。遥感影像就属于典型的 栅格结构，每个象元的数字表示影像的灰度等级。 栅格结构的显著特点是：属性明显，定位隐含，即数据直接记录属性的指针或属性本身， 而所在位置则根据行列号转换为相应的坐标给出，也就是说定位是根据数据在数据集中的位 置得到的。由于栅格结构是按一定的规则排列的，所表示的实体的位置很容易隐含在网格文 件的存贮结构中，在后面讲述栅格结构编码时可以看到，每个存贮单元的行列位置可以方便 地根据其在文件中的记录位置得到，且行列坐标可以很容易地转为其他坐标系 下的坐标。 在网格文件中每个代码本身明确地代表了实体的属性或属性的编码，如果为属性的编码，则 该编码可作为指向实体属性表的指针。由于栅格行列阵列容易为计算机存储、操作和显示
因此这种结构容易实现,算法简单,且易于扩充、修改,也很直观,特别是易于同遥感影像 结合处理,给地理空间数据处理带来了极大的方便,受到普遍欢迎,许多系统都部分和全部 采取了栅格结构,栅格结构的另一个优点是,特别适合于 FORTRAN、 BASIC等高级语言作 文件或矩阵处理,这也是栅格结构易于为多数地理信息系统设计者接受的原因之 栅格结构表示的地表是不连续的,是量化和近似离散的数据。在栅格结构中,地表被分 成相互邻接、规则排列的矩形方块(特殊的情况下也可以是三角形或菱形、六边形等,每个地 块与一个栅格单元相对应。栅格数据的比例尺就是栅格大小与地表相应单元大小之比。在许 多栅格数据处理时,常假设栅格所表示的量化表面是连续的,以便使用某些连续函数。由于 栅格结构对地表的量化,在计算面积、长度、距离、形状等空间指标时,若柵格尺寸较大, 则会造成较大的误差,同时由于在一个栅格的地表范围内,可能存在多于一种的地物,而表 示在相应的栅格结构中常常只能是一个代码。这类似于遥感影像的混合象元问题,如 landsat MSS卫星影像单个象元对应地表79×79m2的矩形区域,影像上记录的光谱数据是每个象元所 对应的地表区域内所有地物类型的光谱辐射的总和效果。因而,这种误差不仅有形态上的畸 变,还可能包括属性方面的偏差。 栅格结构数据主要可由四个途径得到,即 ①目读法:在专题图上均匀划分网格,逐个网格地决定其代码,最后形成栅格数字地图 文件 ②数字化仪手扶或自动跟踪数字化地图,得到矢量结构数据后,再转换为栅格结构 ③扫描数字化:逐点扫描专题地图,将扫描数据重采样和再编码得到柵格数据文件; ④分类影像输入:将经过分类解译的遥感影像数据直接或重采样后输入系统,作为栅格 数据结构的专题地图 在转换和重新采样时,需尽可能保持原图或原始数据精度,通常有两种办法: 第一,在决定栅格代码时尽量保持地表的真实性,保证最大的信息容量。图3-1所示的一 块矩形地表区域。内部含有A、B、C三种地物类型,O点为中心点,将这个矩形区域近似地 表示为栅格结构中的一个栅格单元时,可根据需要,采取如下方案之一决定该栅格单元的代 中心点法:用处于栅格中心处的地物类型或现 象特性决定栅格代码。在图3-3所示的矩形区域中 中心点O落在代码为C的地物范围内,按中心点法的 规则,该矩形区域相应的栅格单元代码应为C,中心 点法常用于具有连续分布特性的地理要素,如降雨量 C 分布,人口密度图等 A 图3-1栅格单元代码的确定
32 因此这种结构容易实现，算法简单，且易于扩充、修改，也很直观，特别是易于同遥感影像 结合处理，给地理空间数据处理带来了极大的方便，受到普遍欢迎，许多系统都部分和全部 采取了栅格结构，栅格结构的另一个优点是，特别适合于 FORTRAN、BASIC 等高级语言作 文件或矩阵处理，这也是栅格结构易于为多数地理信息系统设计者接受的原因之一。 栅格结构表示的地表是不连续的，是量化和近似离散的数据。在栅格结构中，地表被分 成相互邻接、规则排列的矩形方块(特殊的情况下也可以是三角形或菱形、六边形等，每个地 块与一个栅格单元相对应。栅格数据的比例尺就是栅格大小与地表相应单元大小之比。在许 多栅格数据处理时，常假设栅格所表示的量化表面是连续的，以便使用某些连续函数。由于 栅格结构对地表的量化，在计算面积、长度、距离、形状等空间指标时，若栅格尺寸较大， 则会造成较大的误差，同时由于在一个栅格的地表范围内，可能存在多于一种的地物，而表 示在相应的栅格结构中常常只能是一个代码。这类似于遥感影像的混合象元问题，如 landsat MSS 卫星影像单个象元对应地表 79×79m2 的矩形区域，影像上记录的光谱数据是每个象元所 对应的地表区域内所有地物类型的光谱辐射的总和效果。因而，这种误差不仅有形态上的畸 变，还可能包括属性方面的偏差。 栅格结构数据主要可由四个途径得到，即 ①目读法：在专题图上均匀划分网格，逐个网格地决定其代码，最后形成栅格数字地图 文件； ②数字化仪手扶或自动跟踪数字化地图，得到矢量结构数据后，再转换为栅格结构； ③扫描数字化：逐点扫描专题地图，将扫描数据重采样和再编码得到栅格数据文件； ④分类影像输入：将经过分类解译的遥感影像数据直接或重采样后输入系统，作为栅格 数据结构的专题地图。 在转换和重新采样时，需尽可能保持原图或原始数据精度，通常有两种办法： 第一，在决定栅格代码时尽量保持地表的真实性，保证最大的信息容量。图 3-1 所示的一 块矩形地表区域。内部含有 A、B、C 三种地物类型，O 点为中心点，将这个矩形区域近似地 表示为栅格结构中的一个栅格单元时，可根据需要，采取如下方案之一决定该栅格单元的代 码： ①中心点法：用处于栅格中心处的地物类型或现 象特性决定栅格代码。在图 3-3 所示的矩形区域中， 中心点 O 落在代码为 C 的地物范围内，按中心点法的 规则，该矩形区域相应的栅格单元代码应为 C，中心 点法常用于具有连续分布特性的地理要素，如降雨量 分布，人口密度图等。 图 3-1 栅格单元代码的确定
②面积占优法:以占矩形区域面积最大的地物类型或现象特性决定栅格单元的代码。在 图3-1所示的例中,显见B类地物所占面积最大,故相应栅格代码定为B。面积占优法常用 于分类较细,地物类别斑块较小的情况 ③重要性法:根据栅格内不同地物的重要性,选取最重要的地物类型决定相应的栅格单 元代码、假设图3-1中A类为最重要的地物类型,即A比B和C类更为重要,则栅格单元的 代码应为A。重要性法常用于具有特殊意义而面积较小的地理要素,特别是点、线状地理要 素,如城镇、交通枢钮、交通线、河流水系等,在栅格中代码应尽量表示这些重要地物 ④百分比法:根据矩形区域内各地理要素所占面积的百分比数确定栅格单元的代码参与, 如可记面积最大的两类BA,也可根据B类和A类所占面积百分比数在代码中加入数字 逼近原始精度的第二种方法是缩小单个栅格单元的面积,即增加栅格单元的总数,行列 数也相应地增加。这样,每个栅格单元可代表更为精细的地面矩形单元,混合单元减少。混 合类别和混合的面积都大大减小,可以大大提高量算的精度;接近真实的形态,表现更细小 的地物类型 然而增加栅格个数、提高数据精度的同时也带来了一个严重的问题,那就是数据量的大 幅度增加,数据冗余严重。为了解决这个难题,已发展了一系列栅格数据压缩编码方法,如 游程长度编码、块码和四叉树码等。 二、栅格数据的压缩编码方式 1、链式编码( Chain codes) 链式编码又称为弗里曼链码( Freeman,1961)或边界 链码。链式编码主要是记录线状地物和面状地物的边 界。它把线状地物和面状地物的边界表示为:由某一起 始点开始并按某些基本方向确定的单位矢量链。基本方 向可定义为:东=0,东南=1,南=2,西南=3,西=4, 西北=5,北=6,东北=7等八个基本方向 链式编码的前两个数字表示起点的行、列数,从第 三个数字开始的每个数字表示单位矢量的方向,八个方图32链式编码的方向代码 向以07的整数代表 链式编码对线状和多边形的表示具有很强的数据压缩能力,且具有一定的运算功能,如 面积和周长计算等,探测边界急弯和凹进部分等都比较容易,类似矢量数据结构,比较适于 存储图形数据。缺点是对叠置运算如组合、相交等则很难实施,对局部修改将改变整体结构, 效率较低,而且由于链码以每个区域为单位存储边界,相邻区域的边界则被重复存储而产生
33 ②面积占优法：以占矩形区域面积最大的地物类型或现象特性决定栅格单元的代码。在 图 3-1 所示的例中，显见 B 类地物所占面积最大，故相应栅格代码定为 B。面积占优法常用 于分类较细，地物类别斑块较小的情况。 ③重要性法：根据栅格内不同地物的重要性，选取最重要的地物类型决定相应的栅格单 元代码、假设图 3-1 中 A 类为最重要的地物类型，即 A 比 B 和 C 类更为重要，则栅格单元的 代码应为 A。重要性法常用于具有特殊意义而面积较小的地理要素，特别是点、线状地理要 素，如城镇、交通枢钮、交通线、河流水系等，在栅格中代码应尽量表示这些重要地物。 ④百分比法：根据矩形区域内各地理要素所占面积的百分比数确定栅格单元的代码参与， 如可记面积最大的两类 BA，也可根据 B 类和 A 类所占面积百分比数在代码中加入数字。 逼近原始精度的第二种方法是缩小单个栅格单元的面积，即增加栅格单元的总数，行列 数也相应地增加。这样，每个栅格单元可代表更为精细的地面矩形单元，混合单元减少。混 合类别和混合的面积都大大减小，可以大大提高量算的精度；接近真实的形态，表现更细小 的地物类型。 然而增加栅格个数、提高数据精度的同时也带来了一个严重的问题，那就是数据量的大 幅度增加，数据冗余严重。为了解决这个难题，已发展了一系列栅格数据压缩编码方法，如 游程长度编码、块码和四叉树码等。 二、栅格数据的压缩编码方式 1、链式编码(Chain Codes) 链式编码又称为弗里曼链码(Freeman，1961)或边界 链码。链式编码主要是记录线状地物和面状地物的边 界。它把线状地物和面状地物的边界表示为：由某一起 始点开始并按某些基本方向确定的单位矢量链。基本方 向可定义为：东＝0，东南＝l，南＝2，西南＝3，西＝4， 西北＝5，北＝6，东北＝7 等八个基本方向。 链式编码的前两个数字表示起点的行、列数，从第 三个数字开始的每个数字表示单位矢量的方向，八个方 向以 0—7 的整数代表。 链式编码对线状和多边形的表示具有很强的数据压缩能力，且具有一定的运算功能，如 面积和周长计算等，探测边界急弯和凹进部分等都比较容易，类似矢量数据结构，比较适于 存储图形数据。缺点是对叠置运算如组合、相交等则很难实施，对局部修改将改变整体结构， 效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的边界则被重复存储而产生 6 7 0 3 2 1 4 5 图 3-2 链式编码的方向代码
冗余。 2、游程长度编码(run- length code) 游程长度编码是栅格数据压缩的重要编码方法,它的基本思路是:对于一幅栅格图像,常 常有行(或列)方向上相邻的若干点具有相同的属性代码,因而可采取某种方法压缩那些重复的 记录内容。其编码方案是,只在各行(或列)数据的代码发生变化时依次记录该代码以及相同代 码重复的个数,从而实现数据的压缩。 事实上,压缩比的大小是与图的复杂程度成反比的,在变化多的部分,游程数就多,变化 少的部分游程数就少,图件越简单,压缩效率就越高 游程长度编码在栅格加密时,数据量没有明显増加,压缩效率较高,且易于检索,叠加合 并等操作,运算简单,适用于机器存贮容量小,数据需大量压缩,而又要避免复杂的编码解 码运算增加处理和操作时间的情况 3、块状编码( block code) 块码是游程长度编码扩展到二维的情况,采用方形区域作为记录单元,每个记录单元包 括相邻的若干栅格,数据结构由初始位置(行、列号)和半径,再加上记录单元的代码组成 一个多边形所包含的正方形越大,多边形的边界越简单,块状编码的效率就越好。块状 编码对大而简单的多边形更为有效,而对那些碎部较多的复杂多边形效果并不好。块状编码 在合并、插入、检査延伸性、计算面积等操作时有明显的优越性。然而对某些运算不适应, 必须在转换成简单数据形式才能顺利进行。 4、四叉树编码(quad- tree code) 四又树结构的基本思想是将一幅栅格地图或图像等分为四部分。逐块检査其格网属性值 (或灰度)。如果某个子区的所有格网值都具有相同的值。则这个子区就不再继续分割,否则还 要把这个子区再分割成四个子区。这样依次地分割,直到每个子块都只含有相同的属性值或 灰度为止(见P48)。 四叉树编码法有许多有趣的优点:①容易而有效地计算多边形的数量特征;②阵列各部 分的分辨率是可变的,边界复杂部分四叉树较高即分级多,分辨率也高,而不需表示许多细 节的部分则分级少,分辨率低,因而既可精确表示图形结构又可减少存贮量;②栅格到四叉 树及四叉树到简单栅格结构的转换比其它压缩方法容易:④多边形中嵌套异类小多边形的表 示较方便 四叉树编码的最大缺点是转换的不定性,用同一形状和大小的多边形可能得出多种不同 的四叉树结构,故不利于形状分析和模式识别。但因它允许多边形中嵌套多边形即所谓“洞” 这种结构存在,使越来越多的地理信息系统工作者都对四叉树结构很感兴趣。上述这些压缩 数据的方法应视图形的复杂情况合理选用,同时应在系统中备有相应的程序。另外,用户的
34 冗余。 2、游程长度编码（run-length code） 游程长度编码是栅格数据压缩的重要编码方法，它的基本思路是：对于一幅栅格图像，常 常有行(或列)方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的 记录内容。其编码方案是，只在各行(或列)数据的代码发生变化时依次记录该代码以及相同代 码重复的个数，从而实现数据的压缩。 事实上，压缩比的大小是与图的复杂程度成反比的，在变化多的部分，游程数就多，变化 少的部分游程数就少，图件越简单，压缩效率就越高。 游程长度编码在栅格加密时，数据量没有明显增加，压缩效率较高，且易于检索，叠加合 并等操作，运算简单，适用于机器存贮容量小，数据需大量压缩，而又要避免复杂的编码解 码运算增加处理和操作时间的情况。 3、块状编码(block code) 块码是游程长度编码扩展到二维的情况，采用方形区域作为记录单元，每个记录单元包 括相邻的若干栅格，数据结构由初始位置(行、列号)和半径，再加上记录单元的代码组成。 一个多边形所包含的正方形越大，多边形的边界越简单，块状编码的效率就越好。块状 编码对大而简单的多边形更为有效，而对那些碎部较多的复杂多边形效果并不好。块状编码 在合并、插入、检查延伸性、计算面积等操作时有明显的优越性。然而对某些运算不适应， 必须在转换成简单数据形式才能顺利进行。 4、四叉树编码(quad-tree code) 四又树结构的基本思想是将一幅栅格地图或图像等分为四部分。逐块检查其格网属性值 (或灰度)。如果某个子区的所有格网值都具有相同的值。则这个子区就不再继续分割，否则还 要把这个子区再分割成四个子区。这样依次地分割，直到每个子块都只含有相同的属性值或 灰度为止（见Ｐ48）。 四叉树编码法有许多有趣的优点：①容易而有效地计算多边形的数量特征；②阵列各部 分的分辨率是可变的，边界复杂部分四叉树较高即分级多，分辨率也高，而不需表示许多细 节的部分则分级少，分辨率低，因而既可精确表示图形结构又可减少存贮量；②栅格到四叉 树及四叉树到简单栅格结构的转换比其它压缩方法容易；④多边形中嵌套异类小多边形的表 示较方便。 四叉树编码的最大缺点是转换的不定性，用同一形状和大小的多边形可能得出多种不同 的四叉树结构，故不利于形状分析和模式识别。但因它允许多边形中嵌套多边形即所谓“洞” 这种结构存在，使越来越多的地理信息系统工作者都对四叉树结构很感兴趣。上述这些压缩 数据的方法应视图形的复杂情况合理选用，同时应在系统中备有相应的程序。另外，用户的
分析目的和分析方法也决定着压缩方法的选取 四叉树结构按其编码的方法不同又分为常规四叉树和线性四叉树。常规四叉树除了记录 叶结点之外,还要记录中间结点。结点之间借助指针联系,每个结点需要用六个量表达:四 个叶结点指针,一个父结点指针和一个结点的属性或灰度值。这些指针不仅增加了数据贮存 量,而且增加了操作的复杂性。常规四叉树主要在数据索引和图幅索引等方面应用 线性四叉树则只存贮最后叶结点的信息。包括叶结点的位置、深度和本结点的属性或灰度 值。所谓深度是指处于四叉树的第几层上。由深度可推知子区的大小。 线性四叉树叶结点的编号需要遵循一定的规则,这种编号称为地址码,它隐含了叶结点 的位置和深度信息。最常用的地址码是四进制或十进制的 Morton码。 八叉树 八叉树结构(见P53)就是将空间区域不断地分解为八个同样大小的子区域(即将一个六 面的立方体再分解为八个相同大小的小立方体),分解的次数越多,子区域就越小,一直到同 区域的属性单一为止。按从下而上合并的方式来说,就是将研究区空间先按一定的分辨率 将三维空间划分为三维栅格网,然后按规定的顺序每次比较3个相邻的栅格单元,如果其属 性值相同则合并,否则就记盘。依次递归运算,直到每个子区域均为单值为止。 八叉树同样可分为常规八叉树和线性八叉树。常规八叉树的结点要记录十个位,即八个 指向子结点的指针,一个指向父结点的指针和一个属性值(或标识号)。而线性八叉树则只需要 记录叶结点的地址码和属性值。因此,它的主要优点是,其一节省存储空间,因为只需对叶 结点编码,节省了大量中间结点的存储。每个结点的指针也免除了,而从根到某一特定结点 的方向和路径的信息隐含在定位码之中,定位码数字的个位数显示分辨率的高低或分解程度 其次,线性八叉树可直接寻址,通过其坐标值则能计算出任何输入结点的定位码(称编码),而 不必实际建立八叉树,并且定位码本身就是坐标的另一种形式,不必有意去存储坐标值。若 需要的话还能从定位码中获取其坐标值(称解码):其三,在操作方面,所产生的定位码容易存 储和执行,容易实现象集合、相加等组合操作 八叉树主要用来解决地理信息系统中的三维问题 第二节矢量数据结构 地理信息系统中另一种最常见的图形数据结构为矢量结构,即通过记录坐标的方式尽可 能精确地表示点、线、多边形等地理实体,坐标空间设为连续,允许任意位置、长度和面积 的精确定义,事实上,因为如下原因,也不可能得到绝对精确的值:1、表示坐标的计算机字 长有限;2、所有矢量输出设备包括绘图仪在内,尽管分辨率比栅格设备高,但也有一定的步
35 分析目的和分析方法也决定着压缩方法的选取。 四叉树结构按其编码的方法不同又分为常规四叉树和线性四叉树。常规四叉树除了记录 叶结点之外，还要记录中间结点。结点之间借助指针联系，每个结点需要用六个量表达：四 个叶结点指针，一个父结点指针和一个结点的属性或灰度值。这些指针不仅增加了数据贮存 量，而且增加了操作的复杂性。常规四叉树主要在数据索引和图幅索引等方面应用。 线性四叉树则只存贮最后叶结点的信息。包括叶结点的位置、深度和本结点的属性或灰度 值。所谓深度是指处于四叉树的第几层上。由深度可推知子区的大小。 线性四叉树叶结点的编号需要遵循一定的规则，这种编号称为地址码，它隐含了叶结点 的位置和深度信息。最常用的地址码是四进制或十进制的 Morton 码。 5、八叉树 八叉树结构（见Ｐ53）就是将空间区域不断地分解为八个同样大小的子区域(即将一个六 面的立方体再分解为八个相同大小的小立方体)，分解的次数越多，子区域就越小，一直到同 —区域的属性单一为止。按从下而上合并的方式来说，就是将研究区空间先按—定的分辨率 将三维空间划分为三维栅格网，然后按规定的顺序每次比较 3 个相邻的栅格单元，如果其属 性值相同则合并，否则就记盘。依次递归运算，直到每个子区域均为单值为止。 八叉树同样可分为常规八叉树和线性八叉树。常规八叉树的结点要记录十个位，即八个 指向子结点的指针，—个指向父结点的指针和一个属性值(或标识号)。而线性八叉树则只需要 记录叶结点的地址码和属性值。因此，它的主要优点是，其一节省存储空间，因为只需对叶 结点编码，节省了大量中间结点的存储。每个结点的指针也免除了，而从根到某一特定结点 的方向和路径的信息隐含在定位码之中，定位码数字的个位数显示分辨率的高低或分解程度； 其次，线性八叉树可直接寻址，通过其坐标值则能计算出任何输入结点的定位码(称编码)，而 不必实际建立八叉树，并且定位码本身就是坐标的另—种形式，不必有意去存储坐标值。若 需要的话还能从定位码中获取其坐标值(称解码)；其三，在操作方面，所产生的定位码容易存 储和执行，容易实现象集合、相加等组合操作。 八叉树主要用来解决地理信息系统中的三维问题。 第二节 矢量数据结构 地理信息系统中另一种最常见的图形数据结构为矢量结构，即通过记录坐标的方式尽可 能精确地表示点、线、多边形等地理实体，坐标空间设为连续，允许任意位置、长度和面积 的精确定义，事实上，因为如下原因，也不可能得到绝对精确的值：1、表示坐标的计算机字 长有限；2、所有矢量输出设备包括绘图仪在内，尽管分辨率比栅格设备高，但也有一定的步
长;3、矢量法输入时曲线选取的点不可能太多;4、人工输图中不可避免的定位误差。 在前面第二章中已知道,矢量数据存储是以隐式关系以最小的存储空间存储复杂的数据。 当然这只是相对而言,在地理信息系统中没有绝对“最好”的方法 、矢量数据结构编码的基本内容 1、点实体 点实体包括由单独一对x,y坐标定位的一切地理或制图实体。在矢量数据结构中,除点 实体的x,y坐标外还应存储其它一些与点实体有关的数据来描述点实体的类型、制图符号和 显示要求等。点是空间上不可再分的地理实体,可以是具体的也可以是抽象的,如地物点 文本位置点或线段网络的结点等,如果点是一个与其它信息无关的符号,则记录时应包括符 号类型、大小、方向等有关信息:如果点是文本实体,记录的数据应包括字符大小、字体、 排列方式、比例、方向以及与其它非图形属性的联系方式等信息。对其它类型的点实体也应 做相应的处理 2、线实体 线实体可以定义为直线元素组成的各种线性要素,直线元素由两对以上的x,y坐标定义。 最简单的线实体只存储它的起止点坐标、属性、显示符等有关数据。例如,线实体输出时可 能用实线或虚线描绘,这类信息属符号信息,它说明线实体的输出方式。虽然线实体并不是 以虚线存储,仍可用虚线输出。 弧、链是n个坐标对的集合,这些坐标可以描述任何连续而又复杂的曲线。组成曲线的 线元素越短,x,y坐标数量越多,就越逼近于一条复杂曲线,既要节省存储空间,又要求较 为精确地描绘曲线,唯一的办法是增加数据处理工作量。亦即在线实体的纪录中加入一个指 示字,当起动显示程序时,这个指示字告诉程序:需要数学内插函数(例如样条函数加密数据 点且与原来的点匹配。于是能在输出设备上得到较精确的曲线。不过,数据内插工作却增加 了。弧和链的存储记录中也要加入线的符号类型等信息。 线的网络结构:简单的线或链携带彼此互相连接的空间信息,而这种连接信息又是供排 水网和道路网分析中必不可少的信息。因此要在数据结构中建立指针系统才能让计算机在复 杂的线网结构中逐线跟踪每一条线。指针的建立要以结点为基础。如建立水网中每条支流之 间连接关系时必须使用这种指针系统。指针系统包括结点指向线的指针。每条从结点出发的 线汇于结点处的角度等,从而完整地定义线网络的拓扑关系。 如上所述,线实体主要用来表示线状地物(公路、水系、山脊线)、符号线和多边形边界, 有时也称为“弧”、“链”、“串”等。 其中唯一标识是系统排列序号:线标识码可以标识线的类型:起始点和终止点可以用点
36 长；3、矢量法输入时曲线选取的点不可能太多；4、人工输图中不可避免的定位误差。 在前面第二章中已知道，矢量数据存储是以隐式关系以最小的存储空间存储复杂的数据。 当然这只是相对而言，在地理信息系统中没有绝对“最好”的方法。 一、矢量数据结构编码的基本内容 1、点实体 点实体包括由单独一对 x，y 坐标定位的一切地理或制图实体。在矢量数据结构中，除点 实体的 x，y 坐标外还应存储其它一些与点实体有关的数据来描述点实体的类型、制图符号和 显示要求等。点是空间上不可再分的地理实体，可以是具体的也可以是抽象的，如地物点、 文本位置点或线段网络的结点等，如果点是一个与其它信息无关的符号，则记录时应包括符 号类型、大小、方向等有关信息；如果点是文本实体，记录的数据应包括字符大小、字体、 排列方式、比例、方向以及与其它非图形属性的联系方式等信息。对其它类型的点实体也应 做相应的处理。 2、线实体 线实体可以定义为直线元素组成的各种线性要素，直线元素由两对以上的 x，y 坐标定义。 最简单的线实体只存储它的起止点坐标、属性、显示符等有关数据。例如，线实体输出时可 能用实线或虚线描绘，这类信息属符号信息，它说明线实体的输出方式。虽然线实体并不是 以虚线存储，仍可用虚线输出。 弧、链是 n 个坐标对的集合，这些坐标可以描述任何连续而又复杂的曲线。组成曲线的 线元素越短，x，y 坐标数量越多，就越逼近于一条复杂曲线，既要节省存储空间，又要求较 为精确地描绘曲线，唯一的办法是增加数据处理工作量。亦即在线实体的纪录中加入一个指 示字，当起动显示程序时，这个指示字告诉程序：需要数学内插函数(例如样条函数)加密数据 点且与原来的点匹配。于是能在输出设备上得到较精确的曲线。不过，数据内插工作却增加 了。弧和链的存储记录中也要加入线的符号类型等信息。 线的网络结构：简单的线或链携带彼此互相连接的空间信息，而这种连接信息又是供排 水网和道路网分析中必不可少的信息。因此要在数据结构中建立指针系统才能让计算机在复 杂的线网结构中逐线跟踪每一条线。指针的建立要以结点为基础。如建立水网中每条支流之 间连接关系时必须使用这种指针系统。指针系统包括结点指向线的指针。每条从结点出发的 线汇于结点处的角度等，从而完整地定义线网络的拓扑关系。 如上所述，线实体主要用来表示线状地物(公路、水系、山脊线)、符号线和多边形边界， 有时也称为“弧”、“链”、“串”等。 其中唯一标识是系统排列序号：线标识码可以标识线的类型；起始点和终止点可以用点
号或直接用坐标表示;显示信息是显示线的文本或符号等;与线相联的非几何属性可以直接 存储于线文件中,也可单独存储,而由标识码联接查找。 3、面实体 多边形(有时称为区域)数据是描述地理空间信息的最重要的一类数据。在区域实体中,具 有名称属性和分类属性的,多用多边形表示,如行政区、土地类型、植被分布等;具有标量 属性的有时也用等值线描述(如地形、降雨量等) 多边形矢量编码,不但要表示位置和属性,更重要的是能表达区域的拓扑特征,如形状 邻域和层次结构等,以便使这些基本的空间单元可以作为专题图的资料进行显示和操作,由 于要表达的信息十分丰富,基于多边形的运算多而复杂,因此多边形矢量编码比点和线实体 的矢量编码要复杂得多,也更为重要。 在讨论多边形数据结构编码的时候,首先对多边形网提出如下的要求 (1)组成地图的每个多边形应有唯一的形状、周长和面积。它们不象栅格结构那样具有简 单而标准的基本单元。即使大多数美国的规划街区也不能设想它们具有完全一样的形状和大 小。对土壤或地质图上的多边形来说更不可能有相同的形状和大小 (2)地理分析要求的数据结构应能够记录每个多边形的邻域关系,其方法与水系网中记录 连接关系一样 (3)专题地图上的多边形并不都是同一等级的多边形,而可能是多边形内嵌套小的多边形 (次一级)。例如,湖泊的水涯线在土地利用图上可算是个岛状多边形,而湖中的岛屿为“岛中 之岛”。这种所谓“岛”或“洞”的结构是多边形关系中较难处理的问题。 二、矢量数据结构编码的方法 矢量数据结构的编码形式,按照其功能和方法可分为:实体式、索引式、双重独立式和 链状双重独立式。 1、实体式 实体式数据结构是指构成多边形边界的各个线段,以多边形为单元进行组织。按照这种 数据结构,边界坐标数据和多边形单元实体一一对应,各个多边形边界都单独编码和数字 化 这种数据结构具有编码容易、数字化操作简单和数据编排直观等优点。但这种方法也有 以下明显缺点 (1)相邻多边形的公共边界要数字化两遍,造成数据冗余存储,可能导致输出的公共边界出 现间隙或重叠 (2)缺少多边形的邻域信息和图形的拓扑关系
37 号或直接用坐标表示；显示信息是显示线的文本或符号等；与线相联的非几何属性可以直接 存储于线文件中，也可单独存储，而由标识码联接查找。 3、面实体 多边形(有时称为区域)数据是描述地理空间信息的最重要的一类数据。在区域实体中，具 有名称属性和分类属性的，多用多边形表示，如行政区、土地类型、植被分布等；具有标量 属性的有时也用等值线描述(如地形、降雨量等)。 多边形矢量编码，不但要表示位置和属性，更重要的是能表达区域的拓扑特征，如形状、 邻域和层次结构等，以便使这些基本的空间单元可以作为专题图的资料进行显示和操作，由 于要表达的信息十分丰富，基于多边形的运算多而复杂，因此多边形矢量编码比点和线实体 的矢量编码要复杂得多，也更为重要。 在讨论多边形数据结构编码的时候，首先对多边形网提出如下的要求： (1)组成地图的每个多边形应有唯一的形状、周长和面积。它们不象栅格结构那样具有简 单而标准的基本单元。即使大多数美国的规划街区也不能设想它们具有完全一样的形状和大 小。对土壤或地质图上的多边形来说更不可能有相同的形状和大小。 (2)地理分析要求的数据结构应能够记录每个多边形的邻域关系，其方法与水系网中记录 连接关系一样。 (3)专题地图上的多边形并不都是同一等级的多边形，而可能是多边形内嵌套小的多边形 (次一级)。例如，湖泊的水涯线在土地利用图上可算是个岛状多边形，而湖中的岛屿为“岛中 之岛”。这种所谓“岛”或“洞”的结构是多边形关系中较难处理的问题。 二、矢量数据结构编码的方法 矢量数据结构的编码形式，按照其功能和方法可分为：实体式、索引式、双重独立式和 链状双重独立式。 1、实体式 实体式数据结构是指构成多边形边界的各个线段，以多边形为单元进行组织。按照这种 数据结构，边界坐标数据和多边形单元实体一一对应，各个多边形边界都单独编码和数 字 化。 这种数据结构具有编码容易、数字化操作简单和数据编排直观等优点。但这种方法也有 以下明显缺点： (1)相邻多边形的公共边界要数字化两遍，造成数据冗余存储，可能导致输出的公共边界出 现间隙或重叠； (2)缺少多边形的邻域信息和图形的拓扑关系；
(3)岛只作为一个单个图形,没有建立与外界多边形的联系。 因此,实体式编码只用在简单的系统中。 2、索引式 索引式数据结构采用树状索引以减少数据冗余并间接增加邻域信息,具体方法是对所有 边界点进行数字化,将坐标对以顺序方式存储,由点索引与边界线号相联系,以线索引与各 多边形相联系,形成树状索引结构 树状索引结构消除了相邻多边形边界的数据冗余和不一致的问题,在简化过于复杂的边 界线或合并多边形时可不必改造索引表,邻域信息和岛状信息可以通过对多边形文件的线索 引处理得到,但是比较繁琐,因而给邻域函数运算、消除无用边、处理岛状信息以及检查拓 扑关系等带来一定的困难,而且两个编码表都要以人工方式建立,工作量大且容易出错。 3、双重独立式 这种数据结构最早是由美国人口统计局研制来进行人口普查分析和制图的,简称为 DIM( Dual Independent Map Encoding)系统或双重独立式的地图编码法。它以城市街道为编码 的主体。其特点是采用了拓扑编码结构。 双重独立式数据结构是对图上网状或面状要素的任何一条线段,用其两端的节点及相邻 面域来予以定义。在双重独立式数据结构中,节点与节点或者面域与面域之间为邻接关系, 节点与线段或者面域与线段之间为关联关系。这种邻接和关联的关系称为拓朴关系。利用这 种拓朴关系来组织数据,可以有效地进行数据存储正确性检查,同时便于对数据进行更新和 检索。因为在这种数据结构中,当编码数据经过计算机编辑处理以后,面域单元的第一个始 节点应当和最后一个终节点相一致,而且当按照左侧面域或右侧面域来自动建立一个指定的 区域单元时,其空间点的坐标应当自行闭合。如果不能自行闭合,或者出现多余的线段,则 表示数据存储或编码有错,这样就达到数据自动编辑的目的。 此外,这种数据结构除了通过线文件生成面文件外,还需要点文件,这里不在列出。 4、链状双重独立式 链状双重独立式数据结构是DME数据结构的一种改进。在DIME中,一条边只能用直 线两端点的序号及相邻的面域来表示,而在链状数据结构中,将若干直线段合为一个弧段(或 链段),每个弧段可以有许多中间点 在链状双重独立数据结构中,主要有四个文件:多边形文件、弧段文件、弧段坐标文件、 结点文件。多边形文件主要由多边形记录组成,包括多边形号、组成多边形的弧段号以及周 长、面积、中心点坐标及有关“洞”的信息等,多边形文件也可以通过软件自动检索各有关 弧段生成,并同时计算出多边形的周长和面积以及中心点的坐标,当多边形中含有“洞”时 则此“洞”的面积为负,并在总面积中减去,其组成的弧段号前也冠以负号:弧段文件主要
38 (3)岛只作为一个单个图形，没有建立与外界多边形的联系。 因此，实体式编码只用在简单的系统中。 2、 索引式 索引式数据结构采用树状索引以减少数据冗余并间接增加邻域信息，具体方法是对所有 边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各 多边形相联系，形成树状索引结构。 树状索引结构消除了相邻多边形边界的数据冗余和不一致的问题，在简化过于复杂的边 界线或合并多边形时可不必改造索引表，邻域信息和岛状信息可以通过对多边形文件的线索 引处理得到，但是比较繁琐，因而给邻域函数运算、消除无用边、处理岛状信息以及检查拓 扑关系等带来一定的困难，而且两个编码表都要以人工方式建立，工作量大且容易出错。 3、双重独立式 这种数据结构最早是由美国人口统计局研制来进行人口普查分析和制图的，简称为 DIME(Dual lndependent Map Encoding)系统或双重独立式的地图编码法。它以城市街道为编码 的主体。其特点是采用了拓扑编码结构。 双重独立式数据结构是对图上网状或面状要素的任何一条线段，用其两端的节点及相邻 面域来予以定义。在双重独立式数据结构中，节点与节点或者面域与面域之间为邻接关系， 节点与线段或者面域与线段之间为关联关系。这种邻接和关联的关系称为拓朴关系。利用这 种拓朴关系来组织数据，可以有效地进行数据存储正确性检查，同时便于对数据进行更新和 检索。因为在这种数据结构中，当编码数据经过计算机编辑处理以后，面域单元的第一个始 节点应当和最后一个终节点相一致，而且当按照左侧面域或右侧面域来自动建立一个指定的 区域单元时，其空间点的坐标应当自行闭合。如果不能自行闭合，或者出现多余的线段，则 表示数据存储或编码有错，这样就达到数据自动编辑的目的。 此外，这种数据结构除了通过线文件生成面文件外，还需要点文件，这里不在列出。 4、链状双重独立式 链状双重独立式数据结构是 DIME 数据结构的一种改进。在 DIME 中，一条边只能用直 线两端点的序号及相邻的面域来表示，而在链状数据结构中，将若干直线段合为一个弧段（或 链段），每个弧段可以有许多中间点。 在链状双重独立数据结构中，主要有四个文件：多边形文件、弧段文件、弧段坐标文件、 结点文件。多边形文件主要由多边形记录组成，包括多边形号、组成多边形的弧段号以及周 长、面积、中心点坐标及有关“洞”的信息等，多边形文件也可以通过软件自动检索各有关 弧段生成，并同时计算出多边形的周长和面积以及中心点的坐标，当多边形中含 有“洞”时 则此“洞”的面积为负，并在总面积中减去，其组成的弧段号前也冠以负号；弧段文件主要
有弧记录组成,存储弧段的起止结点号和弧段左右多边形号:弧段坐标文件由一系列点的位 置坐标组成,一般从数字化过程获取,数字化的顺序确定了这条链段的方向。结点文件由结 点记录组成,存储每个结点的结点号、结点坐标及与该结点连接的弧段。结点文件一般通过 软件自动生成,因为在数字化的过程中,由于数字化操作的误差,各弧段在同一结点处的坐 标不可能完全一致,需要进行匹配处理。当其偏差在允许范围内时,可取同名结点的坐标平 均值。如果偏差过大,则弧段需要重新数字化。 第三节两种数据结构的比较与转化 、两种数据结构的比较 栅格结构和矢量结构是模拟地理信息的两种不同的方法。栅格数据结构类型具有“属性 明显、位置隐含”的特点,它易于实现,且操作简单,有利于基于栅格的空间信息模型的分 析,如在给定区域内计算多边形面积、线密度,栅格结构可以很快算得结果,而采用矢量数 据结构则麻烦的多;但栅格数据表达精度不高,数据存储量大,工作效率较低。如要提高ˉ 倍的表达精度(栅格单元减小一半),数据量就需增加三倍,同时也增加了数据的冗余。因此 对于基于栅格数据结构的应用来说,需要根据应用项目的自身特点及其精度要求来恰当地平 衡栅格数据的表达精度和工作效率两者之间的关系。另外,因为栅格数据格式的简单性(不 经过压缩编码),其数据格式容易为大多数程序设计人员和用户所理解,基于栅格数据基础之 上的信息共享也较矢量数据容易。最后,遥感影象本身就是以象元为单位的栅格结构,所以, 可以直接把遥感影象应用于栅格结构的地理信息系统中,也就是说栅格数据结构比较容易和 遥感相结合。 矢量数据结构类型具有“位置明显、属性隐含”的特点,它操作起来比较复杂,许多分 析操作(如叠置分析等)用矢量数据结构难于实现;但它的数据表达精度较高,数据存储量小, 输出图形美观且工作效率较高。两者的比较见表3-1: 表3-1栅格、矢量数据结构特点比较 比较内容 矢量格式 栅格格式 数据量 大 图形精度 图形运算 复杂、高效 简单、低效 遥感影像格式 不一致 致或接近
39 有弧记录组成，存储弧段的起止结点号和弧段左右多边形号；弧段坐标文件由一系列点的位 置坐标组成，一般从数字化过程获取，数字化的顺序确定了这条链段的方向。结点文件由结 点记录组成，存储每个结点的结点号、结点坐标及与该结点连接的弧段。结点文件一般通过 软件自动生成，因为在数字化的过程中，由于数字化操作的误差，各弧段在同一结点处的坐 标不可能完全一致，需要进行匹配处理。当其偏差在允许范围内时，可取同名结点的坐标平 均值。如果偏差过大，则弧段需要重新数字化。 第三节 两种数据结构的比较与转化 一、两种数据结构的比较 栅格结构和矢量结构是模拟地理信息的两种不同的方法。栅格数据结构类型具有“属性 明显、位置隐含”的特点，它易于实现，且操作简单，有利于基于栅格的空间信息模型的分 析，如在给定区域内计算多边形面积、线密度，栅格结构可以很快算得结果，而采用矢量数 据结构则麻烦的多；但栅格数据表达精度不高，数据存储量大，工作效率较低。如要提高一 倍的表达精度（栅格单元减小一半），数据量就需增加三倍，同时也增加了数据的冗余。因此， 对于基于栅格数据结构的应用来说，需要根据应用项目的自身特点及其精度要求来恰当地平 衡栅格数据的表达精度和工作效率两者之间的关系。另外，因为栅格数据格式的简单性（不 经过压缩编码），其数据格式容易为大多数程序设计人员和用户所理解，基于栅格数据基础之 上的信息共享也较矢量数据容易。最后，遥感影象本身就是以象元为单位的栅格结构，所以， 可以直接把遥感影象应用于栅格结构的地理信息系统中，也就是说栅格数据结构比较容易和 遥感相结合。 矢量数据结构类型具有“位置明显、属性隐含”的特点，它操作起来比较复杂，许多分 析操作(如叠置分析等)用矢量数据结构难于实现；但它的数据表达精度较高，数据存储量小， 输出图形美观且工作效率较高。两者的比较见表 3-1： 表 3-1 栅格、矢量数据结构特点比较 比较内容 矢量格式 栅格格式 数据量 小 大 图形精度 高 低 图形运算 复杂、高效 简单、低效 遥感影像格式 不一致 一致或接近
抽象、昂贵 直观、便宜 数据共享 不易实玛 容易实现 拓扑和网络分析 容易实现 不易实现 、矢量数据结构向柵格数据结构的转换 在地理信息系统中栅格数据与矢量数据各具特点与适用性,为了在一个系统中可以兼容 这两种数据,以便有利于进一步的分析处理,常常需要实现两种结构的转换。 矢量数据结构向栅格数据结构的转换 许多数据如行政边界、交通干线、土地利用类型、土壤类型等都是用矢量数字化的方法 输人计算机或以矢量的方式存在计算机中,表现为点、线、多边形数据。然而,矢量数据直 接用于多种数据的复合分析等处理将比较复杂,特别是不同数据要在位置上一一配准,寻找 交点并进行分析。相比之下利用栅格数据模式进行处理则容易得多。加之土地覆盖和土地利 用等数据常常从遥感图象中获得,这些数据都是栅格数据,因此矢量数据与它们的叠置复合 分析更需要把其从矢量数据的形式转变为柵格数据的形式。 矢量数据的基本坐标是直角坐标X、Y,其坐标原点一般取图的左下角。网格数据的基本 坐标是行和列(ij其坐标原点一般取图的左上角。两种数据变换时,令直角坐标X和Y分别与 行与列平行。由于矢量数据的基本要素是点、线、面,因而只要实现点、线、面的转换,各 种线划图形的变换问题基本上都可以得到解决 (1)点的变换 点的变换十分简单,只要这个点落在那个网格中就是属于那个网格元素 (2)矢量线段的变换 曲线在数字化时输入多个点,形成折线,由于点多而密集,折线在视觉上就形成曲线。 因为相邻两点之间是直线,所以只要知道直线转换网格的方法,曲线和多边形边的转换就可 以完成 依次用同样方法找到直线经过的每一网格并用本直线的属性值(特征值)去填充这些网络, 完成直线的转换。对于曲线或多边形边上的每条直线作连续运算,可以完成曲线或多边形的 交换。 (3)多边形数据的转换 首先应当指出的是,虽然可以用特征码的形式来定义任何一条多边形线段的属性,但是,这 种属性只是线段的属性,而并不是面域的属性,要完成面域的栅格化,其首要前提是实现以 多边形线段反映其周围面域的属性待征。目前一般采用的是左码记录法
40 输出表示 抽象、昂贵 直观、便宜 数据共享 不易实现 容易实现 拓扑和网络分析 容易实现 不易实现 二、矢量数据结构向栅格数据结构的转换 在地理信息系统中栅格数据与矢量数据各具特点与适用性，为了在一个系统中可以兼容 这两种数据，以便有利于进一步的分析处理，常常需要实现两种结构的转换。 1、矢量数据结构向栅格数据结构的转换 许多数据如行政边界、交通干线、土地利用类型、土壤类型等都是用矢量数字化的方法 输人计算机或以矢量的方式存在计算机中，表现为点、线、多边形数据。然而，矢量数据直 接用于多种数据的复合分析等处理将比较复杂，特别是不同数据要在位置上一一配准，寻找 交点并进行分析。相比之下利用栅格数据模式进行处理则容易得多。加之土地覆盖和土地利 用等数据常常从遥感图象中获得，这些数据都是栅格数据，因此矢量数据与它们的叠置复合 分析更需要把其从矢量数据的形式转变为栅格数据的形式。 矢量数据的基本坐标是直角坐标 X、Y，其坐标原点一般取图的左下角。网格数据的基本 坐标是行和列(i,j),其坐标原点一般取图的左上角。两种数据变换时,令直角坐标 X 和 Y 分别与 行与列平行。由于矢量数据的基本要素是点、线、面，因而只要实现点、线、面的转换，各 种线划图形的变换问题基本上都可以得到解决。 （1）点的变换 点的变换十分简单，只要这个点落在那个网格中就是属于那个网格元素。 （2）矢量线段的变换 曲线在数字化时输入多个点，形成折线，由于点多而密集，折线在视觉上就形成曲线。 因为相邻两点之间是直线，所以只要知道直线转换网格的方法，曲线和多边形边的转换就可 以完成。 依次用同样方法找到直线经过的每一网格并用本直线的属性值(特征值)去填充这些网络， 完成直线的转换。对于曲线或多边形边上的每条直线作连续运算，可以完成曲线或多边形的 交换。 （3）多边形数据的转换 首先应当指出的是，虽然可以用特征码的形式来定义任何一条多边形线段的属性，但是，这 种属性只是线段的属性，而并不是面域的属性，要完成面域的栅格化，其首要前提是实现以 多边形线段反映其周围面域的属性待征。目前一般采用的是左码记录法