第2章 空间数据结构

1、第第2章章 空间数据结构空间数据结构 2.1 地理空间及其表达地理空间及其表达2.2 地理空间数据及其特征地理空间数据及其特征2.3 空间数据结构的类型空间数据结构的类型一、地理空间的概念一、地理空间的概念u地理空间地理空间(Geo-spatial)u一般指上至大气电离层，下至地壳与地幔交接的一般指上至大气电离层，下至地壳与地幔交接的莫霍面之间的空间莫霍面之间的空间 区域。其间是自然地理过程区域。其间是自然地理过程和生命及人类活动最和生命及人类活动最 活跃的场所。活跃的场所。u地理空间的定位地理空间的定位u平面控制网：地理经纬度坐标，大地坐标平面控制网：地理经纬度坐标，大地坐标u高程控制网：高

2、程控制网：1985国家高程基准面国家高程基准面二、空间实体的表达二、空间实体的表达u空间实体空间实体u具有形状、属性和时序特征的空间对象或地理实体。包括点、线、具有形状、属性和时序特征的空间对象或地理实体。包括点、线、面、曲面和体。面、曲面和体。u空间实体类别及实体内容的确定是从空间实体类别及实体内容的确定是从具体需要具体需要出发的。其可大可小出发的。其可大可小。GISGIS中的空间实体是一个概括，复杂，相对的概念。中的空间实体是一个概括，复杂，相对的概念。u空间实体的表达空间实体的表达u矢量表示法矢量表示法矢量数据矢量数据u栅格表示法栅格表示法栅格数据栅格数据湖泊河道居民地一、一、GIS空间

3、数据的分类空间数据的分类按数据来按数据来源源按数据结构按数据结构按数据特征按数据特征按几何特征按几何特征按数据发布形式按数据发布形式地图数据影像数据文本数据矢量数据栅格数据 空间数据非空间属性数据点线面、曲面体数字线画图(DLG)数字栅格图(DRG)数字高程模型(DEM)数字正摄影像图(DOM) 4 4）角点、节点）角点、节点VertexVertex：表示线段和弧段上的连接点。表示线段和弧段上的连接点。 1）实体点）实体点：用来代表一个实体。：用来代表一个实体。2）注记点）注记点：用于定位注记。：用于定位注记。3）内点：）内点：用于负载多边形的属性，用于负载多边形的属性，存在于多边形内。存在于

4、多边形内。返回返回1）实体长度）实体长度：从起点到终点的总长从起点到终点的总长2）弯曲度）弯曲度：用于表示像道路拐弯时弯曲的程度。用于表示像道路拐弯时弯曲的程度。3）方向性）方向性：如：水流方向，上游如：水流方向，上游下游，下游， 公路，单、双向之分。公路，单、双向之分。线状实体包括线状实体包括：线段，边界、链、弧段、网络等。线段，边界、链、弧段、网络等。返回返回面状实体的如下面状实体的如下特征特征：1 1）面积范围面积范围 2 2）周长周长3 3）独立性或与其它地物相邻独立性或与其它地物相邻如中国及其周边国家如中国及其周边国家4 4）内岛屿或锯齿状外形内岛屿或锯齿状外形：如岛屿的海岸线封闭所

5、围成的区域。如岛屿的海岸线封闭所围成的区域。5 5）重叠性与非重叠性）重叠性与非重叠性：如学校的分区，菜市场的服务范围等都如学校的分区，菜市场的服务范围等都有可能出现交叉重叠现象，而一个城市有可能出现交叉重叠现象，而一个城市的各个城区一般说来不会出现重叠。的各个城区一般说来不会出现重叠。 返回返回体积，如工程开控和填充的土方量。体积，如工程开控和填充的土方量。每个二维平面的面积。每个二维平面的面积。周长。周长。内岛。内岛。含有弧立块或相邻块。含有弧立块或相邻块。断面图与剖面图。断面图与剖面图。 二、空间数据的基本特征二、空间数据的基本特征三、空间数据的拓扑关系三、空间数据的拓扑关系u拓扑关系是

6、指网拓扑关系是指网结构元素结构元素（结点、弧段、面域（结点、弧段、面域）间的邻接、包含、关联等关系即要素（图元）间的邻接、包含、关联等关系即要素（图元）之间的）之间的连通性连通性或或相邻的相邻的关系。关系。u拓扑关系类型拓扑关系类型u拓扑邻接拓扑邻接u拓扑关联拓扑关联u拓扑包含拓扑包含C4N4C8C6C7N6C10N3C3N1C2N2C1C5N5C9N7特性：特性：图形保持连续状态下变形，图形保持连续状态下变形，但图形关但图形关系不变。系不变。如：将橡皮任意拉伸，压缩，但不能扭转或折如：将橡皮任意拉伸，压缩，但不能扭转或折叠。叠。 拓扑变换拓扑变换（橡皮变换）（橡皮变换） 非拓扑属性非拓扑属性

7、（几何）（几何）拓扑属性（拓扑属性（没发生变化的属性）没发生变化的属性）两点间距离两点间距离一点指向另一点的方向一点指向另一点的方向弧段长度、区域周长、弧段长度、区域周长、面积面积 等等一个点在一条弧段的端点一个点在一条弧段的端点 一条弧是一简单弧段（自身不相交）一条弧是一简单弧段（自身不相交） 一个点在一个区域的边界上一个点在一个区域的边界上一个点在一个区域的内部一个点在一个区域的内部/外部外部一个点在一个环的内一个点在一个环的内/外部外部一个面是一个简单面一个面是一个简单面一个面的连通性一个面的连通性 面内任两点从一点面内任两点从一点可在面的内部走向另一点可在面的内部走向另一点1）关联性）

8、关联性： （不同类不同类要素之要素之间）结点与弧段：如间）结点与弧段：如V9与与L5,L6,L3多边形与弧段：多边形与弧段：P2与与L3,L5,L22）邻接性）邻接性： (同类同类元素之间元素之间)多边形之间、结点之间。多边形之间、结点之间。邻接矩阵邻接矩阵 重叠：重叠：- 邻接：邻接：1 不邻接：不邻接：0P1P2P3P4P1-111P21-10P311-0P4100-3）连通性：）连通性：与邻接性相类似，指对弧段连接与邻接性相类似，指对弧段连接的判别，如用于网络分析中确定的判别，如用于网络分析中确定路径、街道是否相通。路径、街道是否相通。连通矩阵连通矩阵：重叠：重叠：- 连通：连通：1 不

9、连通：不连通：0 V1V2V3V1-10V21-1V301- 4）方向性：）方向性：一条弧段的起点、终点确定了弧段的方向。用一条弧段的起点、终点确定了弧段的方向。用于表达现实中的有向弧段，如城市道路单向，河流的流向等。于表达现实中的有向弧段，如城市道路单向，河流的流向等。5）包含性）包含性：指面状实体包含了哪些线、点或面状实体。：指面状实体包含了哪些线、点或面状实体。6）区域定义）区域定义：多边形由一组封闭的线来定义。：多边形由一组封闭的线来定义。7）层次关系）层次关系：相同元素之间的等级关系，武汉市有各个区组：相同元素之间的等级关系，武汉市有各个区组成。成。四、空间数据的计算机表示四、空间数

10、据的计算机表示u空间分幅空间分幅u属性分层属性分层u时间分段时间分段u一、矢量数据结构一、矢量数据结构(Vector Data)u二、栅格数据结构二、栅格数据结构(Raster Data)u1. 概念概念u基于适量模型的数据结构。是利用欧几里得几何学中的点线面基于适量模型的数据结构。是利用欧几里得几何学中的点线面及其组合体来表示地理实体空间分布的一种数据组织方式。及其组合体来表示地理实体空间分布的一种数据组织方式。u矢量：向量，具有大小和方向的量。矢量：向量，具有大小和方向的量。1) 由外业测量获得由外业测量获得 可利用测量仪器自动记录测量成果可利用测量仪器自动记录测量成果(常称为电子手薄常称

11、为电子手薄)，然后，然后转到地理数据库中。转到地理数据库中。2)由栅格数据转换获得由栅格数据转换获得利用栅格数据矢量化技术，把栅格数据转换为矢量数据。利用栅格数据矢量化技术，把栅格数据转换为矢量数据。3)跟踪数字化跟踪数字化用跟踪数字化的方法，把地图变成离散的矢量数据。用跟踪数字化的方法，把地图变成离散的矢量数据。一、矢量数据结构一、矢量数据结构点：坐标对（点：坐标对（x,y） +识别符识别符线：坐标对系列线：坐标对系列(x1,y1).(xn,yn) 及及有关属性、其它属性有关属性、其它属性面：首尾相同的坐标串面：首尾相同的坐标串关系表关系表几何位置坐标文件几何位置坐标文件连连接接矢量数据表示

12、时矢量数据表示时应考虑以下问题应考虑以下问题：矢量数据自身的存贮和处理。矢量数据自身的存贮和处理。与属性数据的联系。与属性数据的联系。矢量数据之间的空间关系矢量数据之间的空间关系(拓扑关系拓扑关系)。一、矢量数据结构一、矢量数据结构 若是简单点要素如独立树、电线竿、三角点，符号：比例尺、方向若是简单点要素如独立树、电线竿、三角点，符号：比例尺、方向 若是注记点，记录有关字符的大小、方向、字体、排列等若是注记点，记录有关字符的大小、方向、字体、排列等 若是结点若是结点Vertex：符号：指针、与线相交的角度。：符号：指针、与线相交的角度。其它属性其它属性 三角点设立年代、材料等三角点设立年代、材

13、料等坐标识坐标识别符有别符有关属性关属性一、矢量数据结构一、矢量数据结构5. 1) 实体式实体式（spaghetti）u面条模型，以实体为单位记录其坐标。面条模型，以实体为单位记录其坐标。u优点优点：结构简单、直观、易实现以实体为单位的运算和：结构简单、直观、易实现以实体为单位的运算和显示。显示。u缺点缺点：u相邻多边形的公共边界被数字化并存储两次，造成相邻多边形的公共边界被数字化并存储两次，造成数据冗余和碎屑多边形数据冗余和碎屑多边形数据不一致，浪费空间，导数据不一致，浪费空间，导致双重边界不能精确匹配。致双重边界不能精确匹配。u自成体系，自成体系，缺少多边形的邻接信息，无拓扑关系缺少多边形

14、的邻接信息，无拓扑关系，难以进行邻域处理，如消除多边形公共边界，合并多难以进行邻域处理，如消除多边形公共边界，合并多边形。边形。u岛作为一个单个图形，没有与外界多边形联系。不岛作为一个单个图形，没有与外界多边形联系。不易检查拓扑错误。易检查拓扑错误。u所以，这种结构只用于简单的制图系统中，显示图所以，这种结构只用于简单的制图系统中，显示图形。形。1234567891011 1213 1415P PP PP P多边形坐标串P1P2一、矢量数据结构一、矢量数据结构1234567891011 1213 1415P PP PP P1、点文件：、点文件：点号点号坐标坐标1x1,y1索引文件：索引文件：面

15、号面号弧段号弧段号P1A,B,C3、面文件：、面文件：2、弧段文件、弧段文件: 弧段号弧段号起点起点终点终点点号点号A527,8,9,10u对所有点的坐标按顺序建坐标文件，再建点与边（线）、线与多边形的索引文对所有点的坐标按顺序建坐标文件，再建点与边（线）、线与多边形的索引文件。件。u优点：优点：用建索引的方法消除多边形数据的冗余和不一致，邻接信息、岛信息可用建索引的方法消除多边形数据的冗余和不一致，邻接信息、岛信息可在多边形文件中通过是否公共弧段号的方式查询。在多边形文件中通过是否公共弧段号的方式查询。u缺点缺点：表达拓扑关系较繁琐，给相邻运算、消除无用边、处理岛信息、检索拓：表达拓扑关系较

16、繁琐，给相邻运算、消除无用边、处理岛信息、检索拓扑关系等带来困难，以人工方式建立编码表，工作量大，易出错。扑关系等带来困难，以人工方式建立编码表，工作量大，易出错。一、矢量数据结构一、矢量数据结构二、栅格数据结构二、栅格数据结构u1. 概念概念u基于栅格模型的数据结构。是指将空间分基于栅格模型的数据结构。是指将空间分割成有规则的网格，称为栅格单元。在各割成有规则的网格，称为栅格单元。在各个栅格单元上给出相应的属性值来表示地个栅格单元上给出相应的属性值来表示地理实体的一种数据组织形式。理实体的一种数据组织形式。u位置由行，列号定义，属性为栅格单元的位置由行，列号定义，属性为栅格单元的值。值。二、

17、栅格数据结构二、栅格数据结构2. 图形表示图形表示u点点：由：由单个栅格单个栅格表达。表达。u线线：由沿线走向有相同属性取值的：由沿线走向有相同属性取值的一组一组相邻栅格相邻栅格表达。表达。u面面：由沿线走向有相同属性取值的：由沿线走向有相同属性取值的一片一片栅格栅格表达。表达。 u栅格数据表示的是二维表面上的地理数据的离栅格数据表示的是二维表面上的地理数据的离散化数值。在栅格数据中，地表被分割为相互散化数值。在栅格数据中，地表被分割为相互邻接、规则排列的地块，每个地块与一个象元邻接、规则排列的地块，每个地块与一个象元相对应。因此，栅格数据的相对应。因此，栅格数据的比例尺比例尺就是就是栅格栅格

18、( (象象元元) )的大小与地表相应单元的大小之比的大小与地表相应单元的大小之比，当象元，当象元所表示的面积较大时，对长度、面积等的量测所表示的面积较大时，对长度、面积等的量测有较大影响。每个象元的属性是地表相应区域有较大影响。每个象元的属性是地表相应区域内地理数据的近似值，因而有可能产生内地理数据的近似值，因而有可能产生属性方属性方面的偏差面的偏差。22122332333233323332333空间数据库空间数据库u针对针对一个栅格单元对应多个属性一个栅格单元对应多个属性值的多层栅格文件值的多层栅格文件。2 222 2aaaaa2 2土壤土壤植被植被组织方法组织方法二、栅格数据结构二、栅格数

19、据结构u组织方法组织方法u方法方法a a：以象元为记录序列，不同层上同一象元位置上的各属性值表示：以象元为记录序列，不同层上同一象元位置上的各属性值表示为一个列数组。为一个列数组。N层中层中只记录一层的象元位置，节约大量存储空间，只记录一层的象元位置，节约大量存储空间，栅栅格个数很多。格个数很多。u方法方法b b：每层每个象元的位置、属性一一记录，：每层每个象元的位置、属性一一记录，结构最简单，但浪费存结构最简单，但浪费存储。储。u方法方法c c：以层为基础，每层内以多边形为序记录多边形的属性值和多边：以层为基础，每层内以多边形为序记录多边形的属性值和多边形内各象元的坐标。节约用于存储属性的空

20、间。将同一属性的制图单形内各象元的坐标。节约用于存储属性的空间。将同一属性的制图单元的元的n n个象元的属性只记录一次，便于地图分析和制图处理。个象元的属性只记录一次，便于地图分析和制图处理。二、栅格数据结构二、栅格数据结构二、栅格数据结构二、栅格数据结构u1) 建立途径建立途径u手工获取手工获取，专题图上划分均匀网格，逐个决定其网格代码。，专题图上划分均匀网格，逐个决定其网格代码。u扫描仪扫描扫描仪扫描专题图的图像数据专题图的图像数据行、列、颜色（灰度）行、列、颜色（灰度），定，定义颜色与属性对应表，用相应属性代替相应颜色，得到（行义颜色与属性对应表，用相应属性代替相应颜色，得到（行、列、属

21、性）再进行栅格编码、存贮，即得该专题图的栅格、列、属性）再进行栅格编码、存贮，即得该专题图的栅格数据。数据。u由矢量数据转换而来由矢量数据转换而来。u遥感影像数据，遥感影像数据，对地面景象的辐射和反射能量的扫描抽样，对地面景象的辐射和反射能量的扫描抽样，并按不同的光谱段量化后，以数字形式记录下来的象素值序并按不同的光谱段量化后，以数字形式记录下来的象素值序列。列。u格网格网DEM数据数据，当属性值为地面高程，则为格网，当属性值为地面高程，则为格网DEM，通过，通过DEM内插得到。内插得到。u由于栅格编码一般用于区域性由于栅格编码一般用于区域性GIS，原点的选择常具有，原点的选择常具有局部性质，

22、但为了便于区域的拼接，栅格系统的局部性质，但为了便于区域的拼接，栅格系统的起始坐起始坐标应与国家基本比例尺地形图公里网的交点相一致标应与国家基本比例尺地形图公里网的交点相一致，并，并分别采用分别采用公里网的纵横坐标轴作为栅格系统的坐标轴公里网的纵横坐标轴作为栅格系统的坐标轴。u栅格大小栅格大小u原则原则：应能：应能有效地逼近空间对象的分布特征，又减少数有效地逼近空间对象的分布特征，又减少数据的冗余度据的冗余度。u格网太大，忽略较小图斑，信息丢失。格网太大，忽略较小图斑，信息丢失。u一般讲实体特征愈复杂，栅格尺寸越小，分辨率愈高，一般讲实体特征愈复杂，栅格尺寸越小，分辨率愈高，然而栅格数据量愈大

23、（按分辨率的平方指数增加）计算然而栅格数据量愈大（按分辨率的平方指数增加）计算机成本就越高，处理速度越慢。机成本就越高，处理速度越慢。u方法方法：用保证最小多边形的精度标准来确定尺寸经验公：用保证最小多边形的精度标准来确定尺寸经验公式：式： 其中：其中：h h为栅格单元边长为栅格单元边长，AiAi为区域所有多边形的面积。为区域所有多边形的面积。22122332333233323332 u当一个栅格单元内有多个可选属性值时，按一当一个栅格单元内有多个可选属性值时，按一定方法来确定栅格属性值。定方法来确定栅格属性值。u1、中心点法、中心点法：取位于栅格中心的属性值为该栅格：取位于栅格中心的属性值为

24、该栅格的属性值。的属性值。 u2、面积占优法、面积占优法：栅格单元属性值为面积最大者，：栅格单元属性值为面积最大者，常用于分类较细，地理类别图斑较小时。常用于分类较细，地理类别图斑较小时。u 3、 重要性法重要性法：定义属性类型的重要级别，取重：定义属性类型的重要级别，取重要的属性值为栅格属性值，常用于有重要意义而要的属性值为栅格属性值，常用于有重要意义而面积较小的要素，特别是点、线地理要素。面积较小的要素，特别是点、线地理要素。 u 4、长度占优法长度占优法每个栅格单元的值由该栅格每个栅格单元的值由该栅格中线段最长的实体的属性来确定。中线段最长的实体的属性来确定。AB ba2 2 1 1二、

25、栅格数据结构二、栅格数据结构5. 栅格数据的类型栅格数据的类型u栅格矩阵结构栅格矩阵结构(直接栅格编码直接栅格编码)u游程游程(行程行程)编码结构编码结构u四叉树结构四叉树结构1) 栅格矩阵结构栅格矩阵结构(直接栅格编码直接栅格编码)u将栅格数据看作一个数据矩阵，将栅格数据看作一个数据矩阵，逐行记录代码数据。逐行记录代码数据。u1）每行都从左到右记录；）每行都从左到右记录； AAAAABBBAABBAABBu2）奇数行从左到右，偶数行从右到左；）奇数行从左到右，偶数行从右到左；u特点特点：最直观、最基本的网格存贮结构，没有进行任何压缩数据处最直观、最基本的网格存贮结构，没有进行任何压缩数据处理

26、理。u栅格数据量大，格网数多，由于地理数据往往有较强的相关性，即栅格数据量大，格网数多，由于地理数据往往有较强的相关性，即相邻象元的值往往是相同的。所以，出现了各种栅格数据压缩方法相邻象元的值往往是相同的。所以，出现了各种栅格数据压缩方法。数据压缩是将数据表示成更紧凑的格式以减少存储空间的一项技数据压缩是将数据表示成更紧凑的格式以减少存储空间的一项技术术。分为：。分为：u无损压缩无损压缩：在编码过程中信息没有丢失，经过解码可恢复原有的信息：在编码过程中信息没有丢失，经过解码可恢复原有的信息-信信息息 保持编码保持编码。u有损压缩有损压缩：为最大限度压缩数据，在编码中损失一些认为不太重要的信息：

27、为最大限度压缩数据，在编码中损失一些认为不太重要的信息，解码后，这部分信息无法恢复。，解码后，这部分信息无法恢复。-信息不保持编码信息不保持编码。 A A A A A B B B A A B B A A B B 2)游程游程(行程行程)编码结构编码结构u将原图表示的数据矩阵变为将原图表示的数据矩阵变为数据对数据对：u1）属性码，长度，行号（可不要）属性码，长度，行号（可不要）u长度：连续相同码值的栅格个数。长度：连续相同码值的栅格个数。u2）属性码，点位）属性码，点位u特点：特点：u对于游程长度编码，区域越大，数据的相关性越强，则压缩越大，对于游程长度编码，区域越大，数据的相关性越强，则压缩越

28、大，适适用于类型区域面积较大的专题图用于类型区域面积较大的专题图，而不适合于类型连续变化或类别区，而不适合于类型连续变化或类别区域分散的分类图（压缩比与图的复杂程度成反比）。域分散的分类图（压缩比与图的复杂程度成反比）。u这种编码在这种编码在栅格加密时，数据量不会明显增加栅格加密时，数据量不会明显增加，压缩率高，并最大限压缩率高，并最大限度地保留原始栅格结构，编码解码运算简单，且易于检索，叠加，合度地保留原始栅格结构，编码解码运算简单，且易于检索，叠加，合并等操作并等操作，这种编码应用广泛。，这种编码应用广泛。 A A A A A B B B A A B B A A B B 3) 四叉树结构四

29、叉树结构一种一种可变分率可变分率的的非均匀网格非均匀网格系统。系统。u基本思想基本思想：u将将2 2n n2 2n n象元组成的图像象元组成的图像( (不足的用背景补上不足的用背景补上) ) 按按四个象限进行递归分割，四个象限进行递归分割，并判断属性是否单一，并判断属性是否单一， 单一：不分。不单一：递归分割。单一：不分。不单一：递归分割。u用一倒立树表示这种分割和分割结果。用一倒立树表示这种分割和分割结果。u根根：整个区域：整个区域u高高：深度、分几级，几次分割：深度、分几级，几次分割u叶叶：不能再分割的块：不能再分割的块u树叉树叉：还需分割的块：还需分割的块u每个树叉均有每个树叉均有4 4

30、个分叉，叫四叉树。个分叉，叫四叉树。u编码方法：编码方法：常规四叉树，线性四叉树常规四叉树，线性四叉树AAAAABBBAABBAABB0123(1) (1) 常规四叉树常规四叉树u 记录这棵树的叶结点外，中间结点，结点之间的联系用记录这棵树的叶结点外，中间结点，结点之间的联系用指针联系，每个结点需要指针联系，每个结点需要6 6个变量：个变量：父结点指针、四个子父结点指针、四个子结点的指针和本结点的属性值结点的指针和本结点的属性值。u指针不仅指针不仅增加了数据的存储量增加了数据的存储量，还增加了操作的，还增加了操作的复杂性复杂性：如层次数（分割次数）由从父结点移到根结点的次数来确如层次数（分割次

31、数）由从父结点移到根结点的次数来确定，结点所代表的图像块的位置需要从根节点开始逐步推定，结点所代表的图像块的位置需要从根节点开始逐步推算下来。所以，算下来。所以，常规四叉树并不广泛用于存储数据常规四叉树并不广泛用于存储数据，其价，其价值在于建立索引文件，进行数据检索。值在于建立索引文件，进行数据检索。(2)(2)线性四叉树线性四叉树u只记录三个量：莫顿码，深度（或节点大小），节点值只记录三个量：莫顿码，深度（或节点大小），节点值 。u不需记录中间结点、不需记录中间结点、0 0值节点，也不使用指针，仅记录非值节点，也不使用指针，仅记录非0 0值叶节点。值叶节点。u莫顿莫顿(Morton)(Mor

32、ton)码码: : 扫描栅格单元的顺序代码。也叫扫描栅格单元的顺序代码。也叫PeanoPeano键。键。u优点优点：u存贮量小，只对叶结点编码，节省了大量中间结点的存储，地址码隐含着结存贮量小，只对叶结点编码，节省了大量中间结点的存储，地址码隐含着结点的分割路径和分割次数。点的分割路径和分割次数。u线性四叉树可直接寻址，通过其坐标值直接计算其线性四叉树可直接寻址，通过其坐标值直接计算其MortonMorton码，而不用建立四码，而不用建立四叉树。叉树。u压缩和解压缩比较方便，各部分的分辨率可不同，既可精确地表示图形结构压缩和解压缩比较方便，各部分的分辨率可不同，既可精确地表示图形结构，又可减少

33、存储量，易于进行大部分图形操作和运算。，又可减少存储量，易于进行大部分图形操作和运算。四叉树四叉树u按按MortonMorton码把图象读入一维数组。码把图象读入一维数组。u相邻的四个象元比较，一致的合并，只记录第一个象元的相邻的四个象元比较，一致的合并，只记录第一个象元的MortonMorton码。循环比较所形成的大块，相同的再合并，直到不能合并为止码。循环比较所形成的大块，相同的再合并，直到不能合并为止。u进一步用游程长度编码压缩。压缩时只记录第一个象元的进一步用游程长度编码压缩。压缩时只记录第一个象元的Morton码。码。u右图的编码过程：右图的编码过程：u按按Morton码读入一维数组

34、：码读入一维数组：w 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15(Morton)w A A A B A A B B A A A A B B B B (像元值）像元值）u四相邻象元合并，只记录第一个象元的四相邻象元合并，只记录第一个象元的Morton码。码。w 0 1 2 3 4 5 6 7 8 12w A A A B A A B B A Bu由于不能进一步合并，则用游程长度编码压缩。由于不能进一步合并，则用游程长度编码压缩。w 0 3 4 6 8 12w A B A B A BA 0A 1A 4A 5A 2 B 3B 6B 7A 8A 9B 12B 13A 10

35、A 11B 14B 15u优点优点：u对于团块图像，四叉树表示法占用空间比网络法要对于团块图像，四叉树表示法占用空间比网络法要少得多，四叉树表示法基本上是一种少得多，四叉树表示法基本上是一种非冗余表示法非冗余表示法。u四叉树具有可变率或多重分辩率的特点使得它有很四叉树具有可变率或多重分辩率的特点使得它有很好的应用前景，适用于处理凝聚性或呈块状分布的好的应用前景，适用于处理凝聚性或呈块状分布的空间数据，特别适用于处理分布不均匀的块状空间空间数据，特别适用于处理分布不均匀的块状空间数据，但不适用于连续表面（如地形）或线状地物数据，但不适用于连续表面（如地形）或线状地物。栅格数据的类型栅格数据的类型

36、u四叉树的缺点四叉树的缺点u矢矢/ /栅正反变换还不理想。栅正反变换还不理想。u建立四叉树耗费机时很多。四叉树虽可修改，但很费事建立四叉树耗费机时很多。四叉树虽可修改，但很费事u与非树表示法比较，四叉树表示法的缺点在于转换的不稳定性或叫与非树表示法比较，四叉树表示法的缺点在于转换的不稳定性或叫滑动变异滑动变异( (左下图左下图) )。u一个物体的图像在构成四叉树时会被分割到若干个象限中，使它一个物体的图像在构成四叉树时会被分割到若干个象限中，使它失去了内在的相关性（右失去了内在的相关性（右下图）下图）栅格数据的类型栅格数据的类型AAAAABBBAABBAABBAAAAABBBAABBAABBA 0A 1A 4A 5