第4章 空间数据结构

1、第第4章章 空间数据结构空间数据结构 朱朱 莹莹 主要内容主要内容 矢量数据结构矢量数据结构 栅格数据结构栅格数据结构 矢栅一体化数据结构矢栅一体化数据结构 镶嵌数据结构镶嵌数据结构 三维数据结构三维数据结构 矢量数据结构矢量数据结构 空间数据结构是指对空间数据逻辑模型描述的数空间数据结构是指对空间数据逻辑模型描述的数 据组织关系和编排方式，对地理信息系统中数据据组织关系和编排方式，对地理信息系统中数据 存储、查询检索和应用分析等操作处理的效率有存储、查询检索和应用分析等操作处理的效率有 着至关重要的影响着至关重要的影响 矢量数据结构通过记录实体坐标及其关系，尽可矢量数据结构通过记录实体坐标及

2、其关系，尽可 能精确地表示点、线、多边形等地理实体，坐标能精确地表示点、线、多边形等地理实体，坐标 空间设为连续，允许任意位置、长度和面积的精空间设为连续，允许任意位置、长度和面积的精 确定义确定义 矢量数据结构直接以几何空间坐标为基础，记录矢量数据结构直接以几何空间坐标为基础，记录 取样点坐标取样点坐标 矢量数据结构矢量数据结构 矢量数据结构中，传统的方法是几何图形及其关矢量数据结构中，传统的方法是几何图形及其关 系用文件方式组织，而属性数据通常采用关系型系用文件方式组织，而属性数据通常采用关系型 表文件记录，两者通过实体标识符连接表文件记录，两者通过实体标识符连接 矢量数据结构的分类矢量数

3、据结构的分类 实体数据结构实体数据结构 拓扑数据结构拓扑数据结构 实体数据结构实体数据结构 实体数据结构也称实体数据结构也称spaghetti数据结构，是指构成数据结构，是指构成 多边形边界的各个线段，以多边形为单元进行组多边形边界的各个线段，以多边形为单元进行组 织织 边界坐标数据和多边形单元实体一一对应，各个边界坐标数据和多边形单元实体一一对应，各个 多边形边界点单独编码并记录坐标多边形边界点单独编码并记录坐标 实体数据结构实体数据结构 1 2 8 5 43 18 17 16 15 14 13 12 11 10 9 7 20 D 19 25 24 22 216 23 C B A c f g

4、 a b d e 多边形多边形ID坐标坐标类别码类别码 A（x1，y1），（），（x2，y2），（），（x3，y3），（），（x4，y4），（），（x5，y5），（），（x6， y6），（），（x7，y7），（），（x8，y8），（），（x1，y1） A102 B（x1，y1），（），（x8，y8），（），（x7，y7），（），（x13，y13），（），（x12，y12），（），（x11， y11），（），（x10，y10），（），（x9，y9），（），（x1，y1） B203 C（x20，y20），（），（x25，y25），（），（x24，y24），（），（x23，y23），（），（x22，

5、y22），）， （x21，y21），（），（x20，y20） A178 D（x5，y5），（），（x19，y19），（），（x18，y18），（），（x17，y17），（），（x16，y16），）， （x15，y15），（），（x14，y14），（），（x7，y7），（），（x6，y6），（），（x5，y5） C523 实体数据结构实体数据结构 点号点号坐标坐标 1x1，y1 2x2，y2 3x3，y3 4x4，y4 25x25，y25 多边形多边形ID点号串点号串类别码类别码 A1,2,3,4,5,6,7,8,1A102 B7,8,1,9,10,11,12,13,7B203 C20,21,2

6、2,23,24,25,20A178 D7,13,15,16,17,18,19,5,6,7C523 实体数据结构实体数据结构 实体数据结构具有编码容易、数字化操作简单和实体数据结构具有编码容易、数字化操作简单和 数据编排直观等优点；但这种方法有明显缺点：数据编排直观等优点；但这种方法有明显缺点： 相邻多边形的公共边界要数字化两遍，造成数据冗余相邻多边形的公共边界要数字化两遍，造成数据冗余 存储，可能导致输出的公共边界出现间隙或重叠存储，可能导致输出的公共边界出现间隙或重叠 缺少多边形的邻域信息和图形的拓扑关系缺少多边形的邻域信息和图形的拓扑关系 岛只作为一个单个图形，没有建立与外界多边形的联岛只

7、作为一个单个图形，没有建立与外界多边形的联 系系 拓扑数据结构拓扑数据结构 拓扑关系是一种对空间结构关系进行明确定义的拓扑关系是一种对空间结构关系进行明确定义的 数学方法数学方法 具有拓扑关系的矢量数据结构就是拓扑数据结构具有拓扑关系的矢量数据结构就是拓扑数据结构 拓扑数据结构的特点拓扑数据结构的特点 点是相互独立的，点连成线，线构成面点是相互独立的，点连成线，线构成面 每条线始于起始结点，止于终止结点，并与左右多边每条线始于起始结点，止于终止结点，并与左右多边 形相邻接形相邻接 拓扑数据结构拓扑数据结构 拓扑数据结构最重要的特征是具有拓扑编辑功能；拓扑数据结构最重要的特征是具有拓扑编辑功能；

8、 这种拓扑编辑功能可以保证数字化原始数据的自这种拓扑编辑功能可以保证数字化原始数据的自 动差错编辑，可以自动形成封闭的多边形边界动差错编辑，可以自动形成封闭的多边形边界 拓扑数据结构拓扑数据结构 索引式索引式 双重独立编码结构双重独立编码结构 链状双重独立编码结构链状双重独立编码结构 拓扑数据结构拓扑数据结构 索引式数据结构索引式数据结构 采用树状索引以减少数据冗余并间接增加邻域信息，采用树状索引以减少数据冗余并间接增加邻域信息， 具体方法是对所有边界点进行数字化，将坐标对以顺具体方法是对所有边界点进行数字化，将坐标对以顺 序方式存储，由点索引与边界线号相联系，以线索引序方式存储，由点索引与边

9、界线号相联系，以线索引 与各多边形相联系与各多边形相联系 fe dgdcbe ba DCB A 多边形与线之间索引多边形与线之间索引 20 21 22 23 24 25 13 14 15 16 17 18 19 56 7137 1 9 10 11 12 13 12345 abcdefg 187 点与线之间的树状索引点与线之间的树状索引 点点ID坐标坐标 1x1,y1 边边 ID 组成的组成的 点点ID a1,2,3,4, 5 多边多边 形形ID 组成的组成的 边边ID Aa,b,c 点文件点文件 边文件边文件 多边形文件多边形文件 拓扑数据结构拓扑数据结构 双重独立编码结构双重独立编码结构 最

10、早由美国人口统计系统采用的一种编码方式，简称最早由美国人口统计系统采用的一种编码方式，简称 DIME（DualIndependentMapEncoding）编码系统，）编码系统， 以城市街道为编码主体，特点是采用了拓扑编码结构，以城市街道为编码主体，特点是采用了拓扑编码结构， 该结构适合于城市信息系统该结构适合于城市信息系统 双重独立编码结构是对图上网状或面状要素的任何一双重独立编码结构是对图上网状或面状要素的任何一 条线段，用顺序的两点定义以及相邻多边形来予以定条线段，用顺序的两点定义以及相邻多边形来予以定 义义 多边形原始数据多边形原始数据 线号线号起点起点终点终点左多边形左多边形右多边形

11、右多边形 a16QA b21QA c32QA d43BA e54CA f65CA g67QC h78QC i89QC j94BC k910QB l103QB m1113AD n1312AD o1211AD 拓扑数据结构拓扑数据结构 在双重独立式数据结构中，结点与结点或者多边在双重独立式数据结构中，结点与结点或者多边 形与多边形之间为邻接关系，结点与线段或者多形与多边形之间为邻接关系，结点与线段或者多 边形与线段之间为关联关系边形与线段之间为关联关系 利用这种拓扑关系可以来组织数据，可以有效地利用这种拓扑关系可以来组织数据，可以有效地 进行数据存储正确性检查（如多边形是否封闭），进行数据存储正确

12、性检查（如多边形是否封闭）， 同时便于对数据进行更新和检索同时便于对数据进行更新和检索 除线段拓扑关系文件外，双重独立编码结构还需除线段拓扑关系文件外，双重独立编码结构还需 要点文件和面文件要点文件和面文件 拓扑数据结构拓扑数据结构 链状双重独立编码结构链状双重独立编码结构 链状双重独立式数据结构是链状双重独立式数据结构是DIME数据结构的一种改进数据结构的一种改进 在在DIME中，一条边只能用直线两端点的序号及相邻的多边形来表中，一条边只能用直线两端点的序号及相邻的多边形来表 示，而在链状数据结构中，将若干直线段合为一个示，而在链状数据结构中，将若干直线段合为一个弧段弧段（或链（或链 段），

13、每个弧段可以有许多中间点段），每个弧段可以有许多中间点 ESRI公司的公司的ARCGIS产品中的产品中的COVERAGE数据模型就是采用链数据模型就是采用链 状双重独立编码数据结构状双重独立编码数据结构 四个文件四个文件 多边形文件多边形文件 弧段文件弧段文件 弧段点文件弧段点文件 点坐标文件点坐标文件 拓扑数据结构拓扑数据结构 多边形文件多边形文件 多边形记录组成，包括多边形号、组成多边形的弧段多边形记录组成，包括多边形号、组成多边形的弧段 号以及周长、面积、中心点坐标及有关号以及周长、面积、中心点坐标及有关“洞洞”的信息的信息 等等 多边形文件也可以通过软件自动检索各有关弧段生成，多边形文

14、件也可以通过软件自动检索各有关弧段生成， 并同时计算出多边形的周长和面积以及中心点的坐标，并同时计算出多边形的周长和面积以及中心点的坐标， 当多边形中含有当多边形中含有“洞洞”时则此时则此“洞洞”的面积为负，并的面积为负，并 在总面积中减去，其组成的弧段号前也冠以负号在总面积中减去，其组成的弧段号前也冠以负号 拓扑数据结构拓扑数据结构 弧段文件弧段文件 弧段记录组成，存储弧段的起止结点号和弧段左右多边形号弧段记录组成，存储弧段的起止结点号和弧段左右多边形号 弧段坐标文件弧段坐标文件 由一系列点的位置坐标组成，一般从数字化过程获取，数字化的由一系列点的位置坐标组成，一般从数字化过程获取，数字化的

15、 顺序确定了这条链段的方向顺序确定了这条链段的方向 结点文件结点文件 由结点记录组成，存储每个结点的结点号、结点坐标及与该结点由结点记录组成，存储每个结点的结点号、结点坐标及与该结点 连接的弧段连接的弧段 结点文件一般通过软件自动生成，因为在数字化的过程中，由于结点文件一般通过软件自动生成，因为在数字化的过程中，由于 数字化操作的误差，各弧段在同一结点处的坐标不可能完全一致，数字化操作的误差，各弧段在同一结点处的坐标不可能完全一致， 需要进行匹配处理。当其偏差在允许范围内时，可取同名结点的需要进行匹配处理。当其偏差在允许范围内时，可取同名结点的 坐标平均值。如果偏差过大，则弧段需要重新数字化坐

16、标平均值。如果偏差过大，则弧段需要重新数字化 多边形多边形ID弧段号弧段号属性（如周长、面积等）属性（如周长、面积等） Aa,b,e Bc,d,b Cg Df,e,d,-g 弧段弧段ID起始点起始点终结点终结点左多边形左多边形右多边形右多边形 a51QA b71AB c113QB d137DB e75DA f135QD g2525DC 弧段弧段ID点号点号弧段弧段ID点号点号 a5,4,3,2,1e7,6,5 b7,8,1f13,14,15,16,17,18,19,5 c1,9,10,11,12,13g25,20,21,22,23,24,25 d13,7 点号点号坐标坐标点号点号坐标坐标 1（

17、x1，y1）14（x14，y14） 2（x2，y2）15（x15，y15） 12（x12，y12）25（x25，y25） 13（x13，y13） 以规则栅格阵列表示空间对象的数据结构称为栅以规则栅格阵列表示空间对象的数据结构称为栅 格数据结构格数据结构 点点 线线 面面 实体在栅格数据结构中的表示实体在栅格数据结构中的表示 栅格数据结构栅格数据结构 栅格数据结构栅格数据结构 栅格数据结构的特点栅格数据结构的特点 属性明显，定位隐含，即数据直接记录属性的指针或属性明显，定位隐含，即数据直接记录属性的指针或 属性本身，而所在位置则根据行列号转换为相应的坐属性本身，而所在位置则根据行列号转换为相应的

18、坐 标给出，也就是说定位是根据数据在数据集中的位置标给出，也就是说定位是根据数据在数据集中的位置 得到的得到的 同时具有数据结构简单、数学模拟方便的优点同时具有数据结构简单、数学模拟方便的优点 缺点：数据量大、难以建立实体间的拓扑关系、通过缺点：数据量大、难以建立实体间的拓扑关系、通过 改变分辨率而减少数据量时精度和信息量同时受损等改变分辨率而减少数据量时精度和信息量同时受损等 栅格单元的确定栅格单元的确定 栅格数据的参数栅格数据的参数 栅格形状栅格形状 栅格单元通常为矩形或正方形。特殊的情况下也可以按经纬网栅格单元通常为矩形或正方形。特殊的情况下也可以按经纬网 划分栅格单元划分栅格单元 栅格

19、单元大小栅格单元大小 也就是栅格单元的尺寸，即分辨率。栅格单元的合理尺寸应能也就是栅格单元的尺寸，即分辨率。栅格单元的合理尺寸应能 有效地逼近空间对象的分布特征，以保证空间数据的精度。但有效地逼近空间对象的分布特征，以保证空间数据的精度。但 是用栅格来逼近空间实体，不论采用多细小的栅格，与原实体是用栅格来逼近空间实体，不论采用多细小的栅格，与原实体 比都会有误差。通常以保证最小图斑不丢失为原则来确定合理比都会有误差。通常以保证最小图斑不丢失为原则来确定合理 的栅格尺寸的栅格尺寸 设研究区域某要素的最小图斑面积为设研究区域某要素的最小图斑面积为S，栅格单元的边长，栅格单元的边长L用用 如下公式计

20、算：如下公式计算： SL 2 1 栅格单元的确定栅格单元的确定 栅格原点栅格原点 栅格系统的起始坐标应和国家基本比例尺地形图公里栅格系统的起始坐标应和国家基本比例尺地形图公里 网的交点相一致，或者和已有的栅格系统数据相一致。网的交点相一致，或者和已有的栅格系统数据相一致。 并同时使用公里网的纵横坐标轴作为栅格系统的坐标并同时使用公里网的纵横坐标轴作为栅格系统的坐标 轴。这样在使用栅格数据时，就容易和矢量数据或已轴。这样在使用栅格数据时，就容易和矢量数据或已 有的栅格数据相配准有的栅格数据相配准 栅格的倾角栅格的倾角 栅格的坐标系统与国家坐标系统平行。特殊情况根据栅格的坐标系统与国家坐标系统平行

21、。特殊情况根据 应用的需要，可以将栅格系统倾斜某一个角度应用的需要，可以将栅格系统倾斜某一个角度 列列 行行 西南角格网坐标西南角格网坐标 （XWS，YWS） 格网分辨率格网分辨率 格网方向格网方向 栅格数据的坐标系及描述参数栅格数据的坐标系及描述参数 栅格形状栅格形状 栅格单元值的选取栅格单元值的选取 栅格单元取值是惟一的，但由于受到栅格大小的栅格单元取值是惟一的，但由于受到栅格大小的 限制，栅格单元中可能会出现多个地物，在决定限制，栅格单元中可能会出现多个地物，在决定 栅格单元值时应尽量保持其真实性栅格单元值时应尽量保持其真实性 方法方法 中心点法中心点法 面积占优法面积占优法 重要性法重

22、要性法 百分比法百分比法 栅格单元值的选取栅格单元值的选取 中心点法中心点法 用位于栅格中心处的地物类用位于栅格中心处的地物类 型决定其取值。由于中心点型决定其取值。由于中心点 位于代码为位于代码为C的地物范围内，的地物范围内， 故其取值为故其取值为C。这种方法常。这种方法常 用于有连续分布特性的地理用于有连续分布特性的地理 现象现象 面积占优法面积占优法 以占矩形区域面积最大的地以占矩形区域面积最大的地 物类型作为栅格单元的代码。物类型作为栅格单元的代码。 如图如图B类地物所占面积最大，类地物所占面积最大， 故相应栅格单元代码为故相应栅格单元代码为B B A C O 栅格单元属性值的选取栅格

23、单元属性值的选取 栅格单元值的选取栅格单元值的选取 重要性法重要性法 根据栅格内不同地物的重要性，选取最重要的地物类根据栅格内不同地物的重要性，选取最重要的地物类 型作为相应的栅格单元代码。设图中型作为相应的栅格单元代码。设图中A类地物为最重要类地物为最重要 的地物类型，则栅格代码为的地物类型，则栅格代码为A。这种方法常用于有特殊。这种方法常用于有特殊 意义而面积较小的地理要素，特别是点状和线状地理意义而面积较小的地理要素，特别是点状和线状地理 要素。如城镇、交通线、水系等。在栅格代码中应尽要素。如城镇、交通线、水系等。在栅格代码中应尽 量表示这些重要地物。量表示这些重要地物。 百分比法百分比

24、法 根据矩形区域内各地理要素所占面积的百分比数确定根据矩形区域内各地理要素所占面积的百分比数确定 栅格单元的取值，如可记面积最大的两类栅格单元的取值，如可记面积最大的两类BA，也可根，也可根 据据B类和类和A类所占面积百分比数在代码中加入数字类所占面积百分比数在代码中加入数字 栅格单元值的选取栅格单元值的选取 第二种方法第二种方法 缩小单个栅格单元的面积，即增加栅格单元的总数，缩小单个栅格单元的面积，即增加栅格单元的总数， 行列数也相应地增加。这样，每个栅格单元可代表更行列数也相应地增加。这样，每个栅格单元可代表更 为精细的地面矩形单元，混合单元减少。混合类别和为精细的地面矩形单元，混合单元减

25、少。混合类别和 混合的面积都大大减小，可以大大提高量算的精度；混合的面积都大大减小，可以大大提高量算的精度； 接近真实的形态，表现更细小的地物类型接近真实的形态，表现更细小的地物类型 数据量大幅度增加，数据冗余严重数据量大幅度增加，数据冗余严重 完全栅格数据结构完全栅格数据结构 完全栅格数据结构（也称编码）将栅格看作一个完全栅格数据结构（也称编码）将栅格看作一个 数据矩阵，逐行逐个记录栅格单元的值数据矩阵，逐行逐个记录栅格单元的值 每行都从左到右每行都从左到右 奇数行从左到右而偶数行从右到左奇数行从左到右而偶数行从右到左 完全栅格数据结构不采用任何压缩数据的处理，完全栅格数据结构不采用任何压缩

26、数据的处理， 是最直观最基本的栅格数据组织方式是最直观最基本的栅格数据组织方式 完全栅格数据的组织完全栅格数据的组织 基于象元基于象元 基于层基于层 基于面域基于面域 完全栅格数据结构完全栅格数据结构 基于像元基于像元 以像元为独立存储单元，每一个象元对应一条记录，每条记录中以像元为独立存储单元，每一个象元对应一条记录，每条记录中 的记录内容包括象元坐标及其各层属性值的编码；节省了许多存的记录内容包括象元坐标及其各层属性值的编码；节省了许多存 储坐标的空间，各层对应象元的坐标只需存储一次储坐标的空间，各层对应象元的坐标只需存储一次 基于层基于层 以层为存储基础，层中又以象元为序记录其坐标和对应

27、该层的属以层为存储基础，层中又以象元为序记录其坐标和对应该层的属 性值编码性值编码 基于面域基于面域 以层作为存储基础，层中再以面域为单元进行记录，记录的内容以层作为存储基础，层中再以面域为单元进行记录，记录的内容 包括：面域编号、面域对应该层的属性值编码、面域中所有栅格包括：面域编号、面域对应该层的属性值编码、面域中所有栅格 单元的坐标；同一属性的多个相邻象元只需记录一次属性值单元的坐标；同一属性的多个相邻象元只需记录一次属性值 完全栅格数据结构完全栅格数据结构 数据文件数据文件 像元像元1 x坐标坐标 y坐标坐标 层层1属性值属性值 层层2属性值属性值 层层N属性值属性值 像元像元2 像元

28、像元N 数据文件数据文件 层层1 层层2 层层N 像元像元1 像元像元2 像元像元N x坐标坐标 y坐标坐标 属性值属性值 数据文件数据文件 层层1 层层2 层层N 多边形多边形1 多边形多边形2 多边形多边形N 属性值属性值 像元像元1坐标坐标 像元像元2坐标坐标 像元像元N坐标坐标 （c） 基于面域方式基于面域方式 栅格数据组织方式栅格数据组织方式 （b b） 基于层方式基于层方式（a）基于象元方式）基于象元方式 压缩栅格数据结构压缩栅格数据结构 游程长度编码结构游程长度编码结构 游程长度（游程长度（run-length）编码，也称行程编码，不仅）编码，也称行程编码，不仅 是一种栅格数据无

29、损压缩的重要方法，也是一种栅格是一种栅格数据无损压缩的重要方法，也是一种栅格 数据结构数据结构 基本思想基本思想 对于一幅栅格数据（或影像），常常有行（或列）方向上相对于一幅栅格数据（或影像），常常有行（或列）方向上相 邻的若干点具有相同的属性代码，因而可采取某种方法压缩邻的若干点具有相同的属性代码，因而可采取某种方法压缩 那些重复的记录内容那些重复的记录内容 在各行（或列）数据值发生变化时依次记录该值以及相同值在各行（或列）数据值发生变化时依次记录该值以及相同值 重复的个数，实现数据的压缩和组织重复的个数，实现数据的压缩和组织 游程长度编码结构游程长度编码结构 0 0 0 0 0 4 4 4

30、 0 0 0 4 4 4 4 4 0 0 4 4 4 4 8 8 0 0 4 4 4 8 8 8 2 2 4 4 8 8 8 8 2 2 2 4 8 8 8 8 2 2 2 2 8 8 8 8 2 2 2 2 8 8 8 8 (0,5),(4,3) (0,3),(4,5) (0,2),(4,4),(8,2) (0,2),(4,3),(8,3) (2,2),(4,2),(8,4) (2,3),(8,1),(8,4) (2,4),(8,4) (2,4),(8,4) 游程长度编码结构游程长度编码结构 压缩比的大小与图的复杂程度成反比，原始栅格压缩比的大小与图的复杂程度成反比，原始栅格 类型越简单，压

31、缩效率就越高类型越简单，压缩效率就越高 适于类型面积较大的专题要素、遥感图像的分类适于类型面积较大的专题要素、遥感图像的分类 结构，而不适合于类型连续变化或类型分散的分结构，而不适合于类型连续变化或类型分散的分 类图类图 游程长度编码在栅格加密时，数据量没有明显增游程长度编码在栅格加密时，数据量没有明显增 加，压缩效率较高，易于检索、叠加合并等操作加，压缩效率较高，易于检索、叠加合并等操作 四叉树数据结构四叉树数据结构 将一幅栅格数据层或图像等分为四部分，逐块检将一幅栅格数据层或图像等分为四部分，逐块检 查其格网属性值（或灰度）；如果某个子区的所查其格网属性值（或灰度）；如果某个子区的所 有格

32、网值都具有相同的值，则这个子区就不再继有格网值都具有相同的值，则这个子区就不再继 续分割，否则还要把这个子区再分割成四个子区；续分割，否则还要把这个子区再分割成四个子区； 这样依次地分割，直到每个子块都只含有相同的这样依次地分割，直到每个子块都只含有相同的 属性值或灰度为止属性值或灰度为止 四叉树数据结构四叉树数据结构 0 0 1 1 4 4 4 4 0 0 1 1 4 4 4 4 0 0 2 2 4 4 4 4 0 0 2 2 4 4 4 4 2 2 2 2 4 4 4 4 0 0 0 0 4 4 4 4 0 0 0 0 4 4 4 4 0 0 0 0 4 4 4 4 生成四叉树生成四叉树

33、010 2 4 4 00 22002 20 0 结点结点 栅格数据的四叉树分割栅格数据的四叉树分割 四叉树数据结构四叉树数据结构 为了保证四叉树能不断的分解下去，要求栅格数为了保证四叉树能不断的分解下去，要求栅格数 据的栅格单元数必须满足据的栅格单元数必须满足2n2n，n为极限分割次为极限分割次 数，数，n+1是四叉树的最大高度或最大层数是四叉树的最大高度或最大层数 对于非标准尺寸的图像需首先通过增加背景的方对于非标准尺寸的图像需首先通过增加背景的方 法将栅格数据扩充为法将栅格数据扩充为2n2n个单元，对不足的部个单元，对不足的部 分以分以0补足（在建树时，对于补足部分生成的叶补足（在建树时，

34、对于补足部分生成的叶 结点不存储，存储量不会增加）结点不存储，存储量不会增加） 四叉树数据结构四叉树数据结构 按编码的方法不同分为按编码的方法不同分为 常规四叉树常规四叉树 除了记录叶结点之外，还要记录中间结点。结点之间借助指针除了记录叶结点之外，还要记录中间结点。结点之间借助指针 联系，每个结点用六个量表达：四个叶结点指针，一个父结点联系，每个结点用六个量表达：四个叶结点指针，一个父结点 指针和一个结点的属性或灰度值指针和一个结点的属性或灰度值 增加了数据贮存量，增加了操作的复杂性增加了数据贮存量，增加了操作的复杂性 常规四叉树主要在数据索引和图幅索引等方面应用常规四叉树主要在数据索引和图幅

35、索引等方面应用 线性四叉树线性四叉树 只存贮最后叶结点的信息，包括叶结点的位置、深度和本结点只存贮最后叶结点的信息，包括叶结点的位置、深度和本结点 的属性或灰度值的属性或灰度值 所谓深度是指处于四叉树的第几层上，由深度可推知子区的大所谓深度是指处于四叉树的第几层上，由深度可推知子区的大 小小 二维行程编码结构二维行程编码结构 生成线性四叉树之后，仍然存在前后叶结点的值相同的情生成线性四叉树之后，仍然存在前后叶结点的值相同的情 况，可以进一步压缩数据，将前后值相同的叶结点合并，况，可以进一步压缩数据，将前后值相同的叶结点合并， 形成一个新的线性表列形成一个新的线性表列 对线性四叉树的线性表进行行

36、程编码，得到的即为二维行对线性四叉树的线性表进行行程编码，得到的即为二维行 程编码程编码 二维行程编码所合并的不是栅格单元，而是合并了代表范二维行程编码所合并的不是栅格单元，而是合并了代表范 围大小不一的叶结点围大小不一的叶结点 二维行程编码采用了线性四叉树的地址码（二维行程编码采用了线性四叉树的地址码（Morton码），码）， 并按照码的顺序完成编码，但没有结构规律并按照码的顺序完成编码，但没有结构规律 二维行程编码比规则的四叉树更节省存贮空间，而且有利二维行程编码比规则的四叉树更节省存贮空间，而且有利 于以后的插入、删除和修改等操作于以后的插入、删除和修改等操作 与线性四叉树之间的相互转换

37、非常容易和快速与线性四叉树之间的相互转换非常容易和快速 链码结构链码结构 链码数据结构首先采用弗里曼（链码数据结构首先采用弗里曼（Freeman）码对栅格中的）码对栅格中的 线或多边形边界进行编码，再组织为链码结构的文件线或多边形边界进行编码，再组织为链码结构的文件 链式编码将线状地物或区域边界表示为：由某一起始点和链式编码将线状地物或区域边界表示为：由某一起始点和 在某些基本方向上的单位矢量链组成在某些基本方向上的单位矢量链组成 编码过程编码过程 起始点的寻找一般遵从从上到下、从左到右的原则。当发现没有起始点的寻找一般遵从从上到下、从左到右的原则。当发现没有 记录过的点，而且数值也不为零时，

38、就是一条线或边界线的起点。记录过的点，而且数值也不为零时，就是一条线或边界线的起点。 记下该地物的特征码及起点的行列数；然后按顺时针方向寻迹，记下该地物的特征码及起点的行列数；然后按顺时针方向寻迹， 找到相邻的等值点，并按八个方向编码。如遇不能闭合的线段，找到相邻的等值点，并按八个方向编码。如遇不能闭合的线段， 结束后可以返回到起始点再开始寻找下一个线段。已经记录过的结束后可以返回到起始点再开始寻找下一个线段。已经记录过的 栅格单元，可将属性代码置零，以免重复编码栅格单元，可将属性代码置零，以免重复编码 链码结构链码结构 321 40 567 Freeman方向码方向码 起始点起始点 起始点起

39、始点 6 5 6 5 6 7 7 4 5 5 6 7 0 1 2 2 2 线、面的链式编码线、面的链式编码 链码结构链码结构 链码结构文件链码结构文件 特征特征 码码 起点起点 行行 起点起点 列列 链码链码 2146,5,6,5,6,7,7 7284,5,5,6,7,0,1,2,2,2 链码结构链码结构 链码结构可以有效地压缩栅格数据，特别是对计链码结构可以有效地压缩栅格数据，特别是对计 算面积、长度、转折方向和凹凸度等运算十分方算面积、长度、转折方向和凹凸度等运算十分方 便便 缺点是对边界做合并和插入等修改比较困难，对缺点是对边界做合并和插入等修改比较困难，对 区域空间分析运算比较困难区域

40、空间分析运算比较困难 影像金字塔结构影像金字塔结构 影像金字塔是指在统一的空间影像金字塔是指在统一的空间 参照下，根据用户需要以不同参照下，根据用户需要以不同 分辨率进行存储与显示，形成分辨率进行存储与显示，形成 分辨率由粗到细、数据量由小分辨率由粗到细、数据量由小 到大的金字塔结构到大的金字塔结构 影像金字塔结构用于图像编码影像金字塔结构用于图像编码 和渐进式图像传输，是一种典和渐进式图像传输，是一种典 型的分层数据结构形式，适合型的分层数据结构形式，适合 于栅格数据和影像数据的多分于栅格数据和影像数据的多分 辨率组织，也是一种栅格数据辨率组织，也是一种栅格数据 或影像数据的有损压缩方式。或

41、影像数据的有损压缩方式。 金字塔数据结构金字塔数据结构 X0 X1 X2 Xn 矢栅一体化数据结构矢栅一体化数据结构 优点优点缺点缺点 矢矢 量量 数数 据据 结结 构构 数据结构严密，冗余度数据结构严密，冗余度 小，数据量小；小，数据量小； 空间拓扑关系清晰，易空间拓扑关系清晰，易 于网络分析；于网络分析； 面向对象目标的，不仅面向对象目标的，不仅 能表达属性编码，而且能表达属性编码，而且 能方便地记录每个目标能方便地记录每个目标 的具体的属性描述信息的具体的属性描述信息 ； 能够实现图形数据的恢能够实现图形数据的恢 复、更新和综合；复、更新和综合； 图形显示质量好、精度图形显示质量好、精度

42、 高。高。 数据结构处理算法数据结构处理算法 复杂复杂 叠置分析与栅格图叠置分析与栅格图 组合比较难；组合比较难； 数学模拟比较困难数学模拟比较困难 ； 空间分析技术上比空间分析技术上比 较复杂，需要更复较复杂，需要更复 杂的软、硬件条件杂的软、硬件条件 ； 显示与绘图成本比显示与绘图成本比 较高。较高。 栅栅 格格 数数 据据 结结 构构 数据结构简单，易数据结构简单，易 于算法实现；于算法实现； 空间数据的叠置和空间数据的叠置和 组合容易，有利于组合容易，有利于 与遥感数据的匹配与遥感数据的匹配 应用和分析；应用和分析； 各类空间分析，地各类空间分析，地 理现象模拟均较为理现象模拟均较为

43、容易；容易； 输出方法快速，成输出方法快速，成 本低廉。本低廉。 图形数据量大，用图形数据量大，用 大像元减小数据量大像元减小数据量 时，精度和信息量时，精度和信息量 受损失；受损失； 难以建立空间网络难以建立空间网络 连接关系；连接关系； 投影变化实现困难投影变化实现困难 ； 图形数据质量低，图形数据质量低， 地图输出不精美。地图输出不精美。 矢栅一体化数据结构数据结构矢栅一体化数据结构数据结构 为将矢量与栅格数据更加有效地结合与处理，龚为将矢量与栅格数据更加有效地结合与处理，龚 建雅提出了矢栅一体化结构。该数据结构同时具建雅提出了矢栅一体化结构。该数据结构同时具 有矢量实体的概念，又具有栅

44、格覆盖的思想有矢量实体的概念，又具有栅格覆盖的思想 理论基础理论基础 多级格网方法多级格网方法 三个基本约定三个基本约定 线性四叉树编码线性四叉树编码 矢栅一体化数据结构数据结构矢栅一体化数据结构数据结构 将栅格划分成多级格网将栅格划分成多级格网 粗格网粗格网 用于建立空间索引用于建立空间索引 基本格网基本格网 大小与通常栅格划分的原则基本一致，即基本栅格的大小大小与通常栅格划分的原则基本一致，即基本栅格的大小 细分格网细分格网 由于基本栅格的分辨率较低，难以满足精度要求，所以在基本由于基本栅格的分辨率较低，难以满足精度要求，所以在基本 格网的基础上又细分为格网的基础上又细分为256256或或

45、1616个格网，以增加栅个格网，以增加栅 格的空间分辨率，提高点、线的表达精度格的空间分辨率，提高点、线的表达精度 矢栅一体化数据结构数据结构矢栅一体化数据结构数据结构 对点状地物、线状地物、和面状地物作三个约定：对点状地物、线状地物、和面状地物作三个约定： 点状地物仅有空间位置而无形状和面积，在计算机中点状地物仅有空间位置而无形状和面积，在计算机中 仅有一个坐标数据仅有一个坐标数据 线状地物有形状但无面积，在计算机中需要组织一组线状地物有形状但无面积，在计算机中需要组织一组 元子（即栅格单元）填满的路径表达元子（即栅格单元）填满的路径表达 面状地物有形状和面积，在计算机中有一组元子表达面状地

46、物有形状和面积，在计算机中有一组元子表达 的填满路径的边界线和内部（空洞外均填满）的区域的填满路径的边界线和内部（空洞外均填满）的区域 组成组成 镶嵌数据结构镶嵌数据结构 Voronoi数据结构数据结构 以以Voronoi面块单元来组织面块单元来组织 Voronoi多边形数据多边形数据 节点节点p1p8将平面凸多边形将平面凸多边形 ABCDE区域划分为区域划分为8个个 Voronoi单元，定义相邻单元，定义相邻 Voronoi单元之间的垂直平单元之间的垂直平 分线的交点为顶点，且各顶分线的交点为顶点，且各顶 点分别赋予顶点点分别赋予顶点ID号号 Voronoi多边形多边形 A E D C B 5 4 3 2 8 7 6 1 样点样点ID样点坐标样点坐标样点属性值样点属性值 1x1,y1A1 2x2,y2A2 3x3,y3A3 4x4,y4A4 5x5,y5A5 6x6,y6A6 7x7,y7A7 8X8,y8A8 Voronoi单元单元ID相邻相邻Voronoi单元