第三章空间数据结构 数据结构即指数据组织的形式,是适合于计算机存储、管理和处理的数据逻辑结构。对 空间数据则是地理实体的空间排列方式和相互关系的抽象描述。它是对数据的一种理解和解 释,不说明数据结构的数据是毫无用处的,不仅用户无法理解,计算机程序也不能正确的处 理,对同样一组数据,按不同的数据结构去处理,得到的可能是截然不同的内容。空间数据 结构是地理信息系统沟通信息的桥梁,只有充分理解地理信息系统所采用的特定数据结构, 才能正确有效地使用系统。 地理信息系统的空间数据结构主要有栅格结构和矢量结构 第一节栅格数据结构 简单柵格数据结构 栅格结构是最简单最直观的空间数据结构,又称为网格结构( 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、所有矢量输出设备包括绘图仪在内，尽管分辨率比栅格设备高，但也有一定的步