第4章 空间数据结构

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

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

3、实体数据结构 拓扑数据结构拓扑数据结构实体数据结构实体数据结构 实体数据结构也称实体数据结构也称spaghetti数据结构，是指构成数据结构，是指构成多边形边界的各个线段，以多边形为单元进行组多边形边界的各个线段，以多边形为单元进行组织织 边界坐标数据和多边形单元实体一一对应，各个边界坐标数据和多边形单元实体一一对应，各个多边形边界点单独编码并记录坐标多边形边界点单独编码并记录坐标 实体数据结构实体数据结构1285431817161514131211109720D1925242221623CBAcfgabde多边形多边形ID坐标坐标类别码类别码A（x1，y1），（），（x2，y2），（），（x

4、3，y3），（），（x4，y4），（），（x5，y5），（），（x6，y6），（），（x7，y7），（），（x8，y8），（），（x1，y1）A102B（x1，y1），（），（x8，y8），（），（x7，y7），（），（x13，y13），（），（x12，y12），（），（x11，y11），（），（x10，y10），（），（x9，y9），（），（x1，y1）B203C（x20，y20），（），（x25，y25），（），（x24，y24），（），（x23，y23），（），（x22，y22），），（x21，y21），（），（x20，y20）A178D（x5，y5），（），（x19，y19），（），（

5、x18，y18），（），（x17，y17），（），（x16，y16），），（x15，y15），（），（x14，y14），（），（x7，y7），（），（x6，y6），（），（x5，y5）C523实体数据结构实体数据结构点号点号坐标坐标1x1，y12x2，y23x3，y34x4，y425x25，y25多边形多边形ID点号串点号串类别码类别码A1,2,3,4,5,6,7,8,1A102B7,8,1,9,10,11,12,13,7B203C20,21,22,23,24,25,20A178D7,13,15,16,17,18,19,5,6,7C523实体数据结构实体数据结构 实体数据结构具有编码容易、数字

6、化操作简单和实体数据结构具有编码容易、数字化操作简单和数据编排直观等优点；但这种方法有明显缺点：数据编排直观等优点；但这种方法有明显缺点： 相邻多边形的公共边界要数字化两遍，造成数据冗余相邻多边形的公共边界要数字化两遍，造成数据冗余存储，可能导致输出的公共边界出现间隙或重叠存储，可能导致输出的公共边界出现间隙或重叠 缺少多边形的邻域信息和图形的拓扑关系缺少多边形的邻域信息和图形的拓扑关系 岛只作为一个单个图形，没有建立与外界多边形的联岛只作为一个单个图形，没有建立与外界多边形的联系系拓扑数据结构拓扑数据结构 拓扑关系是一种对空间结构关系进行明确定义的拓扑关系是一种对空间结构关系进行明确定义的数

7、学方法数学方法 具有拓扑关系的矢量数据结构就是拓扑数据结构具有拓扑关系的矢量数据结构就是拓扑数据结构 拓扑数据结构的特点拓扑数据结构的特点 点是相互独立的，点连成线，线构成面点是相互独立的，点连成线，线构成面 每条线始于起始结点，止于终止结点，并与左右多边每条线始于起始结点，止于终止结点，并与左右多边形相邻接形相邻接拓扑数据结构拓扑数据结构 拓扑数据结构最重要的特征是具有拓扑编辑功能；拓扑数据结构最重要的特征是具有拓扑编辑功能；这种拓扑编辑功能可以保证数字化原始数据的自这种拓扑编辑功能可以保证数字化原始数据的自动差错编辑，可以自动形成封闭的多边形边界动差错编辑，可以自动形成封闭的多边形边界 拓

8、扑数据结构拓扑数据结构 索引式索引式 双重独立编码结构双重独立编码结构 链状双重独立编码结构链状双重独立编码结构拓扑数据结构拓扑数据结构 索引式数据结构索引式数据结构 采用树状索引以减少数据冗余并间接增加邻域信息，采用树状索引以减少数据冗余并间接增加邻域信息，具体方法是对所有边界点进行数字化，将坐标对以顺具体方法是对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系与各多边形相联系fedgdcbebaDCBA多边形与线之间索引多边形与线之间索引20 21 22 23 24 2513 14 15 16 1

9、7 18 1956 71371 9 10 11 12 1312345abcdefg187点与线之间的树状索引点与线之间的树状索引点点ID坐标坐标1x1,y1边边ID组成的点组成的点IDa1,2,3,4,5多边形多边形ID组成的边组成的边IDAa,b,c点文件点文件边文件边文件多边形文件多边形文件拓扑数据结构拓扑数据结构 双重独立编码结构双重独立编码结构 最早由美国人口统计系统采用的一种编码方式，简称最早由美国人口统计系统采用的一种编码方式，简称DIME（DualIndependentMapEncoding）编码系统，）编码系统，以城市街道为编码主体，特点是采用了拓扑编码结构，以城市街道为编码主

10、体，特点是采用了拓扑编码结构，该结构适合于城市信息系统该结构适合于城市信息系统 双重独立编码结构是对图上网状或面状要素的任何一双重独立编码结构是对图上网状或面状要素的任何一条线段，用顺序的两点定义以及相邻多边形来予以定条线段，用顺序的两点定义以及相邻多边形来予以定义义 多边形原始数据多边形原始数据线号线号起点起点终点终点左多边形左多边形右多边形右多边形a16QAb21QAc32QAd43BAe54CAf65CAg67QCh78QCi89QCj94BCk910QBl103QBm1113ADn1312ADo1211AD拓扑数据结构拓扑数据结构 在双重独立式数据结构中，结点与结点或者多边在双重独立式

11、数据结构中，结点与结点或者多边形与多边形之间为邻接关系，结点与线段或者多形与多边形之间为邻接关系，结点与线段或者多边形与线段之间为关联关系边形与线段之间为关联关系 利用这种拓扑关系可以来组织数据，可以有效地利用这种拓扑关系可以来组织数据，可以有效地进行数据存储正确性检查（如多边形是否封闭），进行数据存储正确性检查（如多边形是否封闭），同时便于对数据进行更新和检索同时便于对数据进行更新和检索 除线段拓扑关系文件外，双重独立编码结构还需除线段拓扑关系文件外，双重独立编码结构还需要点文件和面文件要点文件和面文件 拓扑数据结构拓扑数据结构 链状双重独立编码结构链状双重独立编码结构 链状双重独立式数据结

12、构是链状双重独立式数据结构是DIME数据结构的一种改进数据结构的一种改进 在在DIME中，一条边只能用直线两端点的序号及相邻的多边形来表中，一条边只能用直线两端点的序号及相邻的多边形来表示，而在链状数据结构中，将若干直线段合为一个示，而在链状数据结构中，将若干直线段合为一个弧段弧段（或链（或链段），每个弧段可以有许多中间点段），每个弧段可以有许多中间点 ESRI公司的公司的ARCGIS产品中的产品中的COVERAGE数据模型就是采用链数据模型就是采用链状双重独立编码数据结构状双重独立编码数据结构 四个文件四个文件 多边形文件多边形文件 弧段文件弧段文件 弧段点文件弧段点文件 点坐标文件点坐标文

13、件拓扑数据结构拓扑数据结构 多边形文件多边形文件 多边形记录组成，包括多边形号、组成多边形的弧段多边形记录组成，包括多边形号、组成多边形的弧段号以及周长、面积、中心点坐标及有关号以及周长、面积、中心点坐标及有关“洞洞”的信息的信息等等 多边形文件也可以通过软件自动检索各有关弧段生成，多边形文件也可以通过软件自动检索各有关弧段生成，并同时计算出多边形的周长和面积以及中心点的坐标，并同时计算出多边形的周长和面积以及中心点的坐标，当多边形中含有当多边形中含有“洞洞”时则此时则此“洞洞”的面积为负，并的面积为负，并在总面积中减去，其组成的弧段号前也冠以负号在总面积中减去，其组成的弧段号前也冠以负号拓扑

14、数据结构拓扑数据结构 弧段文件弧段文件 弧段记录组成，存储弧段的起止结点号和弧段左右多边形号弧段记录组成，存储弧段的起止结点号和弧段左右多边形号 弧段坐标文件弧段坐标文件 由一系列点的位置坐标组成，一般从数字化过程获取，数字化的由一系列点的位置坐标组成，一般从数字化过程获取，数字化的顺序确定了这条链段的方向顺序确定了这条链段的方向 结点文件结点文件 由结点记录组成，存储每个结点的结点号、结点坐标及与该结点由结点记录组成，存储每个结点的结点号、结点坐标及与该结点连接的弧段连接的弧段 结点文件一般通过软件自动生成，因为在数字化的过程中，由于结点文件一般通过软件自动生成，因为在数字化的过程中，由于数

15、字化操作的误差，各弧段在同一结点处的坐标不可能完全一致，数字化操作的误差，各弧段在同一结点处的坐标不可能完全一致，需要进行匹配处理。当其偏差在允许范围内时，可取同名结点的需要进行匹配处理。当其偏差在允许范围内时，可取同名结点的坐标平均值。如果偏差过大，则弧段需要重新数字化坐标平均值。如果偏差过大，则弧段需要重新数字化多边形多边形ID弧段号弧段号属性（如周长、面积等）属性（如周长、面积等）Aa,b,eBc,d,bCgDf,e,d,-g弧段弧段ID起始点起始点终结点终结点左多边形左多边形右多边形右多边形a51QAb71ABc113QBd137DBe75DAf135QDg2525DC弧段弧段ID点号

16、点号弧段弧段ID点号点号a5,4,3,2,1e7,6,5b7,8,1f13,14,15,16,17,18,19,5c1,9,10,11,12,13g25,20,21,22,23,24,25d13,7点号点号坐标坐标点号点号坐标坐标1（x1，y1）14（x14，y14）2（x2，y2）15（x15，y15）12（x12，y12）25（x25，y25）13（x13，y13） 以规则栅格阵列表示空间对象的数据结构称为栅以规则栅格阵列表示空间对象的数据结构称为栅格数据结构格数据结构 点点线线面面实体在栅格数据结构中的表示实体在栅格数据结构中的表示栅格数据结构栅格数据结构栅格数据结构栅格数据结构 栅格数

17、据结构的特点栅格数据结构的特点 属性明显，定位隐含，即数据直接记录属性的指针或属性明显，定位隐含，即数据直接记录属性的指针或属性本身，而所在位置则根据行列号转换为相应的坐属性本身，而所在位置则根据行列号转换为相应的坐标给出，也就是说定位是根据数据在数据集中的位置标给出，也就是说定位是根据数据在数据集中的位置得到的得到的 同时具有数据结构简单、数学模拟方便的优点同时具有数据结构简单、数学模拟方便的优点 缺点：数据量大、难以建立实体间的拓扑关系、通过缺点：数据量大、难以建立实体间的拓扑关系、通过改变分辨率而减少数据量时精度和信息量同时受损等改变分辨率而减少数据量时精度和信息量同时受损等栅格单元的确

18、定栅格单元的确定 栅格数据的参数栅格数据的参数 栅格形状栅格形状 栅格单元通常为矩形或正方形。特殊的情况下也可以按经纬网栅格单元通常为矩形或正方形。特殊的情况下也可以按经纬网划分栅格单元划分栅格单元 栅格单元大小栅格单元大小 也就是栅格单元的尺寸，即分辨率。栅格单元的合理尺寸应能也就是栅格单元的尺寸，即分辨率。栅格单元的合理尺寸应能有效地逼近空间对象的分布特征，以保证空间数据的精度。但有效地逼近空间对象的分布特征，以保证空间数据的精度。但是用栅格来逼近空间实体，不论采用多细小的栅格，与原实体是用栅格来逼近空间实体，不论采用多细小的栅格，与原实体比都会有误差。通常以保证最小图斑不丢失为原则来确定

19、合理比都会有误差。通常以保证最小图斑不丢失为原则来确定合理的栅格尺寸的栅格尺寸 设研究区域某要素的最小图斑面积为设研究区域某要素的最小图斑面积为S，栅格单元的边长，栅格单元的边长L用用如下公式计算：如下公式计算：SL21栅格单元的确定栅格单元的确定 栅格原点栅格原点 栅格系统的起始坐标应和国家基本比例尺地形图公里栅格系统的起始坐标应和国家基本比例尺地形图公里网的交点相一致，或者和已有的栅格系统数据相一致。网的交点相一致，或者和已有的栅格系统数据相一致。并同时使用公里网的纵横坐标轴作为栅格系统的坐标并同时使用公里网的纵横坐标轴作为栅格系统的坐标轴。这样在使用栅格数据时，就容易和矢量数据或已轴。这

20、样在使用栅格数据时，就容易和矢量数据或已有的栅格数据相配准有的栅格数据相配准 栅格的倾角栅格的倾角 栅格的坐标系统与国家坐标系统平行。特殊情况根据栅格的坐标系统与国家坐标系统平行。特殊情况根据应用的需要，可以将栅格系统倾斜某一个角度应用的需要，可以将栅格系统倾斜某一个角度列列行行西南角格网坐标西南角格网坐标（XWS，YWS）格网分辨率格网分辨率格网方向格网方向栅格数据的坐标系及描述参数栅格数据的坐标系及描述参数栅格形状栅格形状栅格单元值的选取栅格单元值的选取 栅格单元取值是惟一的，但由于受到栅格大小的栅格单元取值是惟一的，但由于受到栅格大小的限制，栅格单元中可能会出现多个地物，在决定限制，栅格

21、单元中可能会出现多个地物，在决定栅格单元值时应尽量保持其真实性栅格单元值时应尽量保持其真实性 方法方法 中心点法中心点法 面积占优法面积占优法 重要性法重要性法 百分比法百分比法 栅格单元值的选取栅格单元值的选取 中心点法中心点法 用位于栅格中心处的地物类用位于栅格中心处的地物类型决定其取值。由于中心点型决定其取值。由于中心点位于代码为位于代码为C的地物范围内，的地物范围内，故其取值为故其取值为C。这种方法常。这种方法常用于有连续分布特性的地理用于有连续分布特性的地理现象现象 面积占优法面积占优法 以占矩形区域面积最大的地以占矩形区域面积最大的地物类型作为栅格单元的代码。物类型作为栅格单元的代

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

23、栅格代码中应尽要素。如城镇、交通线、水系等。在栅格代码中应尽量表示这些重要地物。量表示这些重要地物。 百分比法百分比法 根据矩形区域内各地理要素所占面积的百分比数确定根据矩形区域内各地理要素所占面积的百分比数确定栅格单元的取值，如可记面积最大的两类栅格单元的取值，如可记面积最大的两类BA，也可根，也可根据据B类和类和A类所占面积百分比数在代码中加入数字类所占面积百分比数在代码中加入数字栅格单元值的选取栅格单元值的选取 第二种方法第二种方法 缩小单个栅格单元的面积，即增加栅格单元的总数，缩小单个栅格单元的面积，即增加栅格单元的总数，行列数也相应地增加。这样，每个栅格单元可代表更行列数也相应地增加

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

25、从左到右而偶数行从右到左 完全栅格数据结构不采用任何压缩数据的处理，完全栅格数据结构不采用任何压缩数据的处理，是最直观最基本的栅格数据组织方式是最直观最基本的栅格数据组织方式 完全栅格数据的组织完全栅格数据的组织 基于象元基于象元 基于层基于层 基于面域基于面域 完全栅格数据结构完全栅格数据结构 基于像元基于像元 以像元为独立存储单元，每一个象元对应一条记录，每条记录中以像元为独立存储单元，每一个象元对应一条记录，每条记录中的记录内容包括象元坐标及其各层属性值的编码；节省了许多存的记录内容包括象元坐标及其各层属性值的编码；节省了许多存储坐标的空间，各层对应象元的坐标只需存储一次储坐标的空间，各

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

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

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

29、04444880044488822448888222488882222888822228888(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)游程长度编码结构游程长度编码结构 压缩比的大小与图的复杂程度成反比，原始栅格压缩比的大小与图的复杂程度成反比，原始栅格类型越简单，压缩效率就越高类型越简单，压缩效率就越高 适于类型面积较大的专题要素、遥感图像的分类适于类型面积较大的专题要素、遥感图像的分类结构，而不适合于类型连续变

30、化或类型分散的分结构，而不适合于类型连续变化或类型分散的分类图类图 游程长度编码在栅格加密时，数据量没有明显增游程长度编码在栅格加密时，数据量没有明显增加，压缩效率较高，易于检索、叠加合并等操作加，压缩效率较高，易于检索、叠加合并等操作四叉树数据结构四叉树数据结构 将一幅栅格数据层或图像等分为四部分，逐块检将一幅栅格数据层或图像等分为四部分，逐块检查其格网属性值（或灰度）；如果某个子区的所查其格网属性值（或灰度）；如果某个子区的所有格网值都具有相同的值，则这个子区就不再继有格网值都具有相同的值，则这个子区就不再继续分割，否则还要把这个子区再分割成四个子区；续分割，否则还要把这个子区再分割成四个

31、子区；这样依次地分割，直到每个子块都只含有相同的这样依次地分割，直到每个子块都只含有相同的属性值或灰度为止属性值或灰度为止 四叉树数据结构四叉树数据结构0011444400114444002244440022444422224444000044440000444400004444生成四叉树生成四叉树0102440022002 200结点结点栅格数据的四叉树分割栅格数据的四叉树分割四叉树数据结构四叉树数据结构 为了保证四叉树能不断的分解下去，要求栅格数为了保证四叉树能不断的分解下去，要求栅格数据的栅格单元数必须满足据的栅格单元数必须满足2n2n，n为极限分割次为极限分割次数，数，n+1是四叉树的

32、最大高度或最大层数是四叉树的最大高度或最大层数 对于非标准尺寸的图像需首先通过增加背景的方对于非标准尺寸的图像需首先通过增加背景的方法将栅格数据扩充为法将栅格数据扩充为2n2n个单元，对不足的部个单元，对不足的部分以分以0补足（在建树时，对于补足部分生成的叶补足（在建树时，对于补足部分生成的叶结点不存储，存储量不会增加）结点不存储，存储量不会增加）四叉树数据结构四叉树数据结构 按编码的方法不同分为按编码的方法不同分为 常规四叉树常规四叉树 除了记录叶结点之外，还要记录中间结点。结点之间借助指针除了记录叶结点之外，还要记录中间结点。结点之间借助指针联系，每个结点用六个量表达：四个叶结点指针，一个

33、父结点联系，每个结点用六个量表达：四个叶结点指针，一个父结点指针和一个结点的属性或灰度值指针和一个结点的属性或灰度值 增加了数据贮存量，增加了操作的复杂性增加了数据贮存量，增加了操作的复杂性 常规四叉树主要在数据索引和图幅索引等方面应用常规四叉树主要在数据索引和图幅索引等方面应用 线性四叉树线性四叉树 只存贮最后叶结点的信息，包括叶结点的位置、深度和本结点只存贮最后叶结点的信息，包括叶结点的位置、深度和本结点的属性或灰度值的属性或灰度值 所谓深度是指处于四叉树的第几层上，由深度可推知子区的大所谓深度是指处于四叉树的第几层上，由深度可推知子区的大小小 二维行程编码结构二维行程编码结构 生成线性四

34、叉树之后，仍然存在前后叶结点的值相同的情生成线性四叉树之后，仍然存在前后叶结点的值相同的情况，可以进一步压缩数据，将前后值相同的叶结点合并，况，可以进一步压缩数据，将前后值相同的叶结点合并，形成一个新的线性表列形成一个新的线性表列 对线性四叉树的线性表进行行程编码，得到的即为二维行对线性四叉树的线性表进行行程编码，得到的即为二维行程编码程编码 二维行程编码所合并的不是栅格单元，而是合并了代表范二维行程编码所合并的不是栅格单元，而是合并了代表范围大小不一的叶结点围大小不一的叶结点 二维行程编码采用了线性四叉树的地址码（二维行程编码采用了线性四叉树的地址码（Morton码），码），并按照码的顺序完

35、成编码，但没有结构规律并按照码的顺序完成编码，但没有结构规律 二维行程编码比规则的四叉树更节省存贮空间，而且有利二维行程编码比规则的四叉树更节省存贮空间，而且有利于以后的插入、删除和修改等操作于以后的插入、删除和修改等操作 与线性四叉树之间的相互转换非常容易和快速与线性四叉树之间的相互转换非常容易和快速链码结构链码结构 链码数据结构首先采用弗里曼（链码数据结构首先采用弗里曼（Freeman）码对栅格中的）码对栅格中的线或多边形边界进行编码，再组织为链码结构的文件线或多边形边界进行编码，再组织为链码结构的文件 链式编码将线状地物或区域边界表示为：由某一起始点和链式编码将线状地物或区域边界表示为：

36、由某一起始点和在某些基本方向上的单位矢量链组成在某些基本方向上的单位矢量链组成 编码过程编码过程 起始点的寻找一般遵从从上到下、从左到右的原则。当发现没有起始点的寻找一般遵从从上到下、从左到右的原则。当发现没有记录过的点，而且数值也不为零时，就是一条线或边界线的起点。记录过的点，而且数值也不为零时，就是一条线或边界线的起点。记下该地物的特征码及起点的行列数；然后按顺时针方向寻迹，记下该地物的特征码及起点的行列数；然后按顺时针方向寻迹，找到相邻的等值点，并按八个方向编码。如遇不能闭合的线段，找到相邻的等值点，并按八个方向编码。如遇不能闭合的线段，结束后可以返回到起始点再开始寻找下一个线段。已经记

37、录过的结束后可以返回到起始点再开始寻找下一个线段。已经记录过的栅格单元，可将属性代码置零，以免重复编码栅格单元，可将属性代码置零，以免重复编码 链码结构链码结构32140567 Freeman方向码方向码 起始点起始点起始点起始点65656774556701222线、面的链式编码线、面的链式编码链码结构链码结构链码结构文件链码结构文件特征码特征码起点行起点行起点列起点列链码链码2146,5,6,5,6,7,77284,5,5,6,7,0,1,2,2,2链码结构链码结构 链码结构可以有效地压缩栅格数据，特别是对计链码结构可以有效地压缩栅格数据，特别是对计算面积、长度、转折方向和凹凸度等运算十分方

38、算面积、长度、转折方向和凹凸度等运算十分方便便 缺点是对边界做合并和插入等修改比较困难，对缺点是对边界做合并和插入等修改比较困难，对区域空间分析运算比较困难区域空间分析运算比较困难影像金字塔结构影像金字塔结构影像金字塔是指在统一的空间影像金字塔是指在统一的空间参照下，根据用户需要以不同参照下，根据用户需要以不同分辨率进行存储与显示，形成分辨率进行存储与显示，形成分辨率由粗到细、数据量由小分辨率由粗到细、数据量由小到大的金字塔结构到大的金字塔结构 影像金字塔结构用于图像编码影像金字塔结构用于图像编码和渐进式图像传输，是一种典和渐进式图像传输，是一种典型的分层数据结构形式，适合型的分层数据结构形式

39、，适合于栅格数据和影像数据的多分于栅格数据和影像数据的多分辨率组织，也是一种栅格数据辨率组织，也是一种栅格数据或影像数据的有损压缩方式。或影像数据的有损压缩方式。 金字塔数据结构金字塔数据结构X0X1X2Xn矢栅一体化数据结构矢栅一体化数据结构优点优点缺点缺点矢量矢量数据数据结构结构1.数据结构严密，冗余度小，数据量小；数据结构严密，冗余度小，数据量小；2.空间拓扑关系清晰，易于网络分析；空间拓扑关系清晰，易于网络分析；3.面向对象目标的，不仅能表达属性编码，而面向对象目标的，不仅能表达属性编码，而且能方便地记录每个目标的具体的属性描述且能方便地记录每个目标的具体的属性描述信息；信息；4.能够

40、实现图形数据的恢复、更新和综合；能够实现图形数据的恢复、更新和综合；图形显示质量好、精度高。图形显示质量好、精度高。1.数据结构处理算法复杂数据结构处理算法复杂2.叠置分析与栅格图组合比较难；叠置分析与栅格图组合比较难；3.数学模拟比较困难；数学模拟比较困难；4.空间分析技术上比较复杂，需要更复空间分析技术上比较复杂，需要更复杂的软、硬件条件；杂的软、硬件条件；5.显示与绘图成本比较高。显示与绘图成本比较高。栅格栅格数据数据结构结构1.数据结构简单，易于算法实现；数据结构简单，易于算法实现；2.空间数据的叠置和组合容易，有利于空间数据的叠置和组合容易，有利于与遥感数据的匹配应用和分析；与遥感数

41、据的匹配应用和分析；3.各类空间分析，地理现象模拟均较为各类空间分析，地理现象模拟均较为容易；容易；4.输出方法快速，成本低廉。输出方法快速，成本低廉。1.图形数据量大，用大像元减小数据量图形数据量大，用大像元减小数据量时，精度和信息量受损失；时，精度和信息量受损失；2.难以建立空间网络连接关系；难以建立空间网络连接关系；3.投影变化实现困难；投影变化实现困难；4.图形数据质量低，地图输出不精美。图形数据质量低，地图输出不精美。矢栅一体化数据结构数据结构矢栅一体化数据结构数据结构 为将矢量与栅格数据更加有效地结合与处理，龚为将矢量与栅格数据更加有效地结合与处理，龚建雅提出了矢栅一体化结构。该数

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

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

44、元）填满的路径表达 面状地物有形状和面积，在计算机中有一组元子表达面状地物有形状和面积，在计算机中有一组元子表达的填满路径的边界线和内部（空洞外均填满）的区域的填满路径的边界线和内部（空洞外均填满）的区域组成组成镶嵌数据结构镶嵌数据结构 Voronoi数据结构数据结构 以以Voronoi面块单元来组织面块单元来组织Voronoi多边形数据多边形数据 节点节点p1p8将平面凸多边形将平面凸多边形ABCDE区域划分为区域划分为8个个Voronoi单元，定义相邻单元，定义相邻Voronoi单元之间的垂直平单元之间的垂直平分线的交点为顶点，且各顶分线的交点为顶点，且各顶点分别赋予顶点点分别赋予顶点ID号号 Voronoi多边形多边形AEDCB54328761样点样点ID样点坐标样点坐标样点属性值样点属性值1x1,y1A12x2,y2A23x3,y3A34x4,y4A4