《空间数据结构2ppt课件》由会员分享，可在线阅读，更多相关《空间数据结构2ppt课件（137页珍藏版）》请在金锄头文库上搜索。
1、第三章第三章空间数据构造与编码空间数据构造与编码p栅格数据构造及编码栅格数据构造及编码p矢量数据构造及编码矢量数据构造及编码p矢栅数据构造转换矢栅数据构造转换p矢栅一体化数据构造矢栅一体化数据构造 空空间数据构造与数据数据构造与数据编码1.1.概念概念 空空间数据构造：指适宜于数据构造：指适宜于计算机系算机系统存存储、管理、管理和和处置的地学置的地学图形的形的逻辑构造，是地理构造，是地理实体的空体的空间陈列方式和相互关系的列方式和相互关系的笼统描画。描画。 空空间数据数据编码：为实现空空间数据的数据的计算机存算机存储、处置和管理，将空置和管理，将空间实体的一定的数据构造体的一定的数据构造转换为
2、适宜适宜计算机操作的算机操作的过程。程。 图形数据图形数据属性数据属性数据编码编码(数据构数据构造造)空间空间实体实体数据存入数据存入计算机计算机栅格数据构造：运用与图像处置系统和栅格数据构造：运用与图像处置系统和GISGIS中。中。矢量数据构造：主导了矢量数据构造：主导了CADCAD系统和有着强大制图功能的系统和有着强大制图功能的GISGIS。一、基于规那么格网空间数据模型的数据一、基于规那么格网空间数据模型的数据构造构造(栅格数据构造栅格数据构造)一概念一概念栅格数据构造是最格数据构造是最简单最直最直观的空的空间数数据构造，又称网格构造或像元构造。据构造，又称网格构造或像元构造。将地球外表
3、划分将地球外表划分为大小均匀大小均匀严密相密相邻的的网格网格阵列，每个网格作列，每个网格作为一个像元或者像素，一个像元或者像素，有行、列号定有行、列号定义，并包含一个代，并包含一个代码，表示，表示该网格的属性网格的属性值或者量或者量值，或者，或者仅仅包含指向包含指向其它属性其它属性记录的指的指针。一概念一概念栅格数据构造格数据构造实践就是像元践就是像元阵列，每个列，每个像元由行列确定它的位置。像元由行列确定它的位置。由于由于栅格构造是按照一定的格构造是按照一定的规那么那么陈列列的，所表示的的，所表示的实体的位置很容易体的位置很容易隐含在文件含在文件的存的存储构造中，且行列坐构造中，且行列坐标可
4、以很容易的可以很容易的转为其他坐其他坐标系下的坐系下的坐标。在文件中每个代。在文件中每个代码本身明确代表本身明确代表实体的属性或属性体的属性或属性编码。点用一个点用一个栅格格单元表示；元表示；线状地物沿状地物沿线走向的一走向的一组相相邻栅格格单元表示，元表示，每个每个栅格格单元最多只需元最多只需两个相两个相邻单元在元在线上；上；面或区域用面或区域用记有区域属有区域属性的相性的相邻栅格格单元的集元的集合表示，每个合表示，每个栅格格单元元可有多于两个的相可有多于两个的相邻单元同属一个区域。元同属一个区域。点点线线面面一概念一概念二根本特征二根本特征l点有大小、地理空点有大小、地理空间离散。离散。l
5、大小由行列号决大小由行列号决议，划分程度决，划分程度决议点大小、点点大小、点数多少、数多少、l表达内容的复表达内容的复杂程度及精度高低。程度及精度高低。l属性特征属性特征显性表示。性表示。l可以直接看到属性，并多以可以直接看到属性，并多以颜色、代色、代码或灰度或灰度表示。表示。l面向位置、面向位置、觉得微得微观l位置由行列号决位置由行列号决议，每个位置都有相，每个位置都有相应的数据。的数据。三栅格数据的组织三栅格数据的组织l不同不同类型的地理型的地理实体分体分层编排，排，l每每层只需只需单一的一的类型。型。l一个一个栅格格单元只需一个属性代元只需一个属性代码。空间数据库空间数据库2 222 2
6、aaaaa22土壤土壤植被植被组织方法方法三三栅格数据的格数据的组织数据文件像元1X坐标Y坐标层1属性层2属性.层n属性像元2像元n数据文件层1X坐标Y坐标属性值像元2 .像元n层2层n像元1数据文件层1属性值像元1坐标像元2坐标多边形2 .多边形n层2层n多边形1像元n坐标四栅格构造的建立四栅格构造的建立1、手工手工获取，取，专题图上划分均匀网格，逐个决上划分均匀网格，逐个决议其网格代其网格代码。2、扫描描仪扫描描专题图的的图像数据像数据行、列、行、列、颜色灰度色灰度，定，定义颜色与属性色与属性对应表，用相表，用相应属性替代相属性替代相应颜色，得到行、列、属性色，得到行、列、属性再再进展展栅
7、格格编码、存、存贮，即得，即得该专题图的的栅格数据。格数据。3、由矢量数据由矢量数据转换而来。而来。4、遥感影像数据，遥感影像数据，对地面景象的地面景象的辐射和反射能量的射和反射能量的扫描抽描抽样，并，并按不同的光按不同的光谱段量化后，以数字方式段量化后，以数字方式记录下来的象素下来的象素值序列。序列。5、格网格网DEM数据，当属性数据，当属性值为地面高程，那么地面高程，那么为格网格网DEM，经过DEM内插得到。内插得到。一建立途径一建立途径四栅格构造的建立四栅格构造的建立二栅格系统的建立二栅格系统的建立1 1、 栅格坐格坐标系确系确实定定表表示示具具有有空空间分分布布特特征征的的地地理理要要
8、素素，不不论采采用用什什么么编码系系统，什什么么数数据据构构造造都都应在在一一致致的的坐坐标系系统下下，而而坐坐标系确系确实定本定本质是坐是坐标系原点和坐系原点和坐标轴确确实定。定。 由由于于栅格格编码普普通通用用于于区区域域性性GISGIS，原原点点的的选择常常具具有有部部分分性性质，但但为了了便便于于区区域域的的拼拼接接，栅格格系系统的的起起始始坐坐标应与与国国家家根根本本比比例例尺尺地地形形图公公里里网网的的交交点点相相一一致致，并并分分别采采用用公公里里网网的的纵横横坐坐标轴作作为栅格格系系统的的坐坐标轴。四栅格构造的建立四栅格构造的建立二栅格系统的建立二栅格系统的建立2、栅格格单元的
9、尺寸元的尺寸1原原那那么么：应应能能有有效效地地逼逼近近空空间间对对象象的的分分布布特特征征，又又减减少少数数据据的的冗余度。格网太大，忽略较小图斑，信息丧失。冗余度。格网太大，忽略较小图斑，信息丧失。2方法：用保证最小多边形的精度规范来确定尺寸阅历公式：方法：用保证最小多边形的精度规范来确定尺寸阅历公式：h为栅格单元边长为栅格单元边长Ai为区域一切多边形的面积。为区域一切多边形的面积。每个每个栅格元素只能取一格元素只能取一个个值，实践上一个践上一个栅格格能能够对应于于实体中几种体中几种不同属性不同属性值，存在，存在栅格格数据取数据取值问题A BC D四栅格构造的建立四栅格构造的建立三栅格属性
10、值确实定三栅格属性值确实定1、中心点法、中心点法用途于用途于栅格中心格中心处的地物的地物类型或景象特性决型或景象特性决议栅格代格代码。中心点法常用于具有延中心点法常用于具有延续分布特性的地理要分布特性的地理要素，如降雨量分布、人口密度素，如降雨量分布、人口密度图等等 。BDDDBBDCBBCCBBAAA BC D三栅格属性值确实定三栅格属性值确实定2、面、面积占占优法法以占矩形区域面以占矩形区域面积最大的地物最大的地物类型或景象特性决型或景象特性决议栅格格单元的代元的代码 。用于分用于分类较细，地物，地物类别斑斑块较小的情况。小的情况。 BDDDBBDCBBCCBBAAA BC D三栅格属性值
11、确实定三栅格属性值确实定3、长度占度占优法法将网格中心画一横将网格中心画一横线，用横，用横线所占最所占最长部分属部分属性性值作作为栅格属性格属性BDDDBBDCBBCCBBAAA BC D三栅格属性值确实定三栅格属性值确实定4、重要性法、重要性法突出某些主要属性，只需在突出某些主要属性，只需在栅格中出格中出现就把就把该属性作属性作为栅格属性格属性DDDDBDDCBBAABBAAA BC D三栅格属性值确实定三栅格属性值确实定5、百分比法、百分比法根据矩形区域内各地理要素所占面根据矩形区域内各地理要素所占面积的百分比的百分比数确定数确定单元的取元的取值。DDDDBDDCBBAABBAAA BC
12、D三栅格属性值确实定三栅格属性值确实定五栅格数据编码方式五栅格数据编码方式n直接栅格编码直接栅格编码n紧缩编码方法紧缩编码方法n链码链码ChainEncodingn游程编码游程编码Run-lengthEncodingn块状编码块状编码BlockEncodingn四叉树编码四叉树编码QuandtreeEncodingn五栅格数据构造类型五栅格数据构造类型1直接直接栅格格编码最最简单最直最直观而又非常重要的一种而又非常重要的一种栅格构造格构造编码方法。方法。把把规那么格网平面作那么格网平面作为一个二一个二维矩矩阵进展展数学表达，每个数学表达，每个栅格是具有行、列位置的矩格是具有行、列位置的矩阵元素
13、，元素，该空空间实体属性体属性编码值赋予矩予矩阵元元素。素。逐行或逐列逐行或逐列记录代代码。2 2 2 1 1 7 7 72 2 2 2 1 7 7 72 2 2 2 2 2 2 22 2 2 7 7 7 7 74 4 4 4 7 7 7 71直接栅格编码直接栅格编码(1,1,2),(1,2,2),(1,3,2),(1,4,1),(1,5,1),(1,6,7),(1,7,7),(1,8,7),(2,1,2),(2,2,2),(2,3,2),假假设行列号行列号记录在在专门文件中，那么只文件中，那么只记录属性属性值：2,2,2,1,1,7,7,7,2,2,2,2,1,7,7,72,2,2,1,1,
14、7,7,7,2,2,2,2,1,7,7,7优点：点：1 1易于易于实现用循用循环语句句编程，程，实现快速运算快速运算2 2易于易于实现空空间属性的分解与分属性的分解与分类，易于，易于实现空空间分分析中叠加等操作析中叠加等操作缺陷：缺陷：数据存数据存储量大量大 根本要素包括：行，列，属性根本要素包括：行，列，属性值N N，M M，XijXij 其中行、列其中行、列值隐性，属性性，属性值显性。性。1直接栅格编码直接栅格编码2费尔曼链码费尔曼链码边境编码边境编码n 将将线状地物或区域状地物或区域边境表示境表示为：由某一同始点和某些：由某一同始点和某些根本方向上的根本方向上的单位矢量位矢量链组成。成。
15、n 前两个字母表示起点的行列号，从第三个数字开前两个字母表示起点的行列号，从第三个数字开场每个数字表示每个数字表示单位矢量的方向。位矢量的方向。70162543n 单位矢量的位矢量的长度度为一个一个栅格格单元，元，后后续点能点能够位于前位于前继点点8 8个根本方向上。个根本方向上。2费尔曼链码费尔曼链码边境编码边境编码n 详细编码过程：程：n起始点的起始点的寻觅普通遵守从上到下、从左到右的原那么。普通遵守从上到下、从左到右的原那么。n当当发现没有没有记录过的点且数的点且数值也不也不为零零时，就是，就是这一条一条线或或边境的起点，境的起点，记下下该地物的特征地物的特征码和行列号；然后和行列号；然
16、后按按顺时针方向方向寻觅，找到相，找到相邻的等的等值点，并按八个方向点，并按八个方向编码。n如遇到不能如遇到不能闭合的合的线段，段，终了后可前往到起始点再开了后可前往到起始点再开场寻觅下一个下一个线段。段。n已已记录过的的栅格格单元，可将属性代元，可将属性代码置零，以免反复置零，以免反复编码。28500020000080200000020000000200055020555550205555520005500200000002费尔曼链码费尔曼链码边境编码边境编码特征码特征码高程高程起止行列起止行列链链码码2100m1，44,5,4,5,5,45200m4，72,4,4,6,5,6,7,0,2,
17、2,1701625434545454244656702212费尔曼链码费尔曼链码边境编码边境编码n 优缺陷：优缺陷：n数据紧缩率强，便于计算长度，面积，数据紧缩率强，便于计算长度，面积，转机方向的凸凹度，易于储存。转机方向的凸凹度，易于储存。n但难于实现叠置运算，不便于合并插入但难于实现叠置运算，不便于合并插入操作。对部分改动涉及到整体构造。操作。对部分改动涉及到整体构造。适于对曲线和边境进展编码。适于对曲线和边境进展编码。2费尔曼链码费尔曼链码边境编码边境编码3游程行程编码游程行程编码根本思绪：对一个栅格图形，经常有行根本思绪：对一个栅格图形，经常有行列方向上相邻的假设干栅格单元具有一列方向
18、上相邻的假设干栅格单元具有一样的属性代码，因此可采用某种方法紧缩样的属性代码，因此可采用某种方法紧缩那些反复代码内容。那些反复代码内容。编码方案：只是在各行列栅格单元的编码方案：只是在各行列栅格单元的代码发生变化时依次记录该代码以及一样代码发生变化时依次记录该代码以及一样代码反复的个数或者记录代码发生变化的代码反复的个数或者记录代码发生变化的位置。位置。3游程行程编码游程行程编码游程：游程：栅格数据矩格数据矩阵中相中相邻并属性一并属性一样的的栅格格视为一游程，以游程一游程，以游程为单位位记录数据。数据。2228800058888770第一行：第一行：4个游程个游程第二行：第二行：3个游程个游程
19、适于适于对块状地物的状地物的栅格数据格数据进展展紧缩编码编码方式：方式：(gk，lk) gk栅格属性格属性值lk 游程游程终止列号或止列号或长度度 K=1,2,3,4.m(mn)分为游程终止编码和游程长度编码分为游程终止编码和游程长度编码 3游程行程编码游程行程编码(0,1)(4,3)(7,8)(4,5)(7,8)(4,4)(8,6)(7,8)(0,2)(4,3)(8,6)(7,8)(0,2)(8,6)(7,7)(8,8)(0,3)(8,8)(0,4)(8,8)(0,5)(8,8)游程游程终止止编码3游程行程编码游程行程编码0,1)(4,2)(7,5)(4,5)(7,3)(4,4)(8,2)(
20、7,2)(0,2)(4,1)(8,3)(7,2)(0,2)(8,4)(7,1)(8,1)(0,3)(8,5)(0,4)(8,4)(0,5)(8,3)游程游程长度度编码：3游程行程编码游程行程编码n 特点：属性的特点：属性的变化愈少，游程愈化愈少，游程愈长，即，即紧缩比的大小与比的大小与图的复的复杂程度成反比。程度成反比。 n 优点：数据点：数据紧缩率高，易于率高，易于实现叠加，叠加，检索和合并运算。索和合并运算。n 缺陷：适宜缺陷：适宜类型区面型区面积较大的大的专题图、遥、遥感影像分感影像分类集中的分集中的分类图，不适宜，不适宜类型延型延续变化或化或类型区分散的分型区分散的分类图。3游程行程编
21、码游程行程编码4块状编码块状编码是将游程是将游程长度度编码扩展到二展到二维的情况，采用正的情况，采用正方形区域方形区域为单元元对块状地物的状地物的栅格数据格数据进展展编码，本本质是把是把栅格格阵列中同一属性方形区域各元素映射列中同一属性方形区域各元素映射成一个元素系列。每个成一个元素系列。每个记录单元包含相元包含相邻假假设干干栅格，数据构造由初始位置和半径，在加上格，数据构造由初始位置和半径，在加上记录单元元的代的代码组成。成。编码方式：行号，列号，半径，代方式：行号，列号，半径，代码0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3
22、3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 31 1，1 1，1 1，0 0，1 1，2 2，2 2，2 2，1 1，4 4，1 1，5 5，1 1，5 5，1 1，5 5，1 1，6 6，2 2，5 5，1 1，8 8，1 1，5 5；2 2，1 1，1 1，2 2，2 2，4 4，1 1，2 2，2 2，5 5，1 1，2 2，2 2，8 8，1 1，5 5；3 3，3 3，1 1，2 2，3 3，4 4，1 1，2 2，3 3，5 5，2 2，3 3，3 3，7 7，2 2，5 5；4 4，1 1，2 2
23、，0 0，4 4，3 3，1 1，2 2，4 4，4 4，1 1，3 3；5 5，3 3，1 1，3 3，5 5，4 4，2 2，3 3，5 5，6 6，1 1，3 3，5 5，7 7，1 1，5 5，5 5，8 8，1 1，3 3；6 6，1 1，3 3，0 0，6 6，6 6，3 3，3 3；7 7，4 4，1 1，0 0，7 7，5 5，1 1，3 3；8 8，4 4，1 1，0 0，8 8，5 5，1 1，0 0。4块状编码块状编码特点：特点：1、面状地物所能包含的正方形越大，多、面状地物所能包含的正方形越大，多边形形边境越境越简单，块码编码效率超高；效率超高；2、图形比形比较碎，多碎
24、，多边形形边境复境复杂的的图形，形，数据数据紧缩率低；率低；3、利于、利于计算面算面积、合并插入等操作。、合并插入等操作。4块状编码块状编码5四叉树编码四叉树编码QuadtreeCode四叉四叉树概述：概述：四叉四叉树又称又称为四元四元树或四分或四分树，是最有效，是最有效的的栅格数据格数据紧缩编码方法之一，方法之一，绝大部分大部分图形操作和运算都可以直接在四叉形操作和运算都可以直接在四叉树构造上构造上实现，四叉，四叉树编码即即紧缩了数据量，又可大大了数据量，又可大大提高提高图形操作的效率。形操作的效率。1、根本思想：将、根本思想：将2n2n象元象元组成的成的图像像(缺乏的用缺乏的用背景背景补上
25、上)按四个象限按四个象限进展展递归分割，并判分割，并判别属性属性能否能否单一，一，单一：不分。一：不分。不不单一：一：递归分割。分割。最后得到一最后得到一颗四分叉的倒向四分叉的倒向树。5四叉树编码四叉树编码QuadtreeCode2、四叉树的树形表示：、四叉树的树形表示：用一倒立树表示分割和分割结果。用一倒立树表示分割和分割结果。根：整个区域根：整个区域高：深度、分几级，几次分割高：深度、分几级，几次分割叶：不能再分割的块叶：不能再分割的块树叉：还需分割的块。树叉：还需分割的块。0123AAAAABBBAABBAABB00000444000444440044448800444888224488
26、8822248888222288882222888800004404440444848244824221常规四叉树及编码常规四叉树及编码原始栅格原始栅格四叉树图四叉树图1常规四叉树及编码常规四叉树及编码四叉树编码的树状表示四叉树编码的树状表示NWNESWSE004482220000444 4 4 4484442(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14) (15) (16)(17)(18)(19) (20)(21)(22)(23)(24)0层1层2层3层记录这棵树的叶结点外，中间结点，结点之间的联络用指针联络，记录这棵树的叶结点外，中间结点，结
27、点之间的联络用指针联络，每个结点需求每个结点需求6个变量：父结点指针、四个子结点的指针和本结点的属性值。个变量：父结点指针、四个子结点的指针和本结点的属性值。对一幅一幅2N 2N的的栅格格阵列，最大深度列，最大深度为N，能能够有的有的层次次为0，1，2，N，最大，最大层数数为N+1.那么，每那么，每层的的栅格格宽度度为： 2最大深度最大深度-当前当前层次次反映了所在叶反映了所在叶结点表示的正方形集合的大小。点表示的正方形集合的大小。1常规四叉树常规四叉树及编码及编码缺陷：缺陷：所占空间比较大，不仅要记录每个结点，还所占空间比较大，不仅要记录每个结点，还要记录一个前趋结点和四个后继点，以及反要记
28、录一个前趋结点和四个后继点，以及反映结点之间联络，对栅格数据进展运算时，映结点之间联络，对栅格数据进展运算时，还要作遍历树结点的运算，添加操作复杂性。还要作遍历树结点的运算，添加操作复杂性。1常规四叉树及编码常规四叉树及编码指针不仅添加了数据的存储量，还添加了操作的复杂性：指针不仅添加了数据的存储量，还添加了操作的复杂性：如层次数分割次数由从父结点移到根结点的次数来如层次数分割次数由从父结点移到根结点的次数来确定，结点所代表的图像块的位置需求从根节点开场逐确定，结点所代表的图像块的位置需求从根节点开场逐渐推算下来。所以，常规四叉树并不广泛用于存储数据，渐推算下来。所以，常规四叉树并不广泛用于存
29、储数据，其价值在于建立索引文件，进展数据检索。其价值在于建立索引文件，进展数据检索。2)线性四叉树及编码线性四叉树及编码以四叉以四叉树的方式的方式组织数据，但不以四叉数据，但不以四叉树方方式存式存储数据。数据。经过编码四叉四叉树的叶的叶结点表示数据的点表示数据的层次和次和空空间关系。叶关系。叶结点具有一个反映位置的关点具有一个反映位置的关键字，亦称位置字，亦称位置码。本。本质是把原来大小相等的是把原来大小相等的栅格集合格集合转换成大小不等的正方形集合，成大小不等的正方形集合，对不同尺寸和位置的正方形集合不同尺寸和位置的正方形集合赋予一个位置予一个位置码。2)线性四叉树及编码线性四叉树及编码 只
30、存贮最后叶结点信息。只存贮最后叶结点信息。 包括：结点号、结点位置、深度、本节点的包括：结点号、结点位置、深度、本节点的 属性或灰度值属性或灰度值 象限划分：象限划分： 0 1 2 3(19)0(18)0(12)0(11)0(16)(15)(17)0(14)(13)(10)191(7)(6)(5)(4)318020100 0 0 0 0 0 0 00 0 0 0 0 0 0 01 1 0 0 0 0 0 01 1 1 1 0 0 0 0 1 1 1 1 1 0 0 01 1 1 1 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 02)线性四叉树及编码线性四叉树及编码
31、2线性四叉树及编码线性四叉树及编码1基于深度和基于深度和层次次码的的线性四叉性四叉树编码它它经过记录叶叶结点的深度点的深度码和和层次次码来描画叶来描画叶结点的位置，点的位置，2N为层次次码。如如图中叶中叶结点点7的的编码为：层次码层次码深度码深度码4位位第一层第一层第二层第二层第三层第三层0011110011置置码十十进制制值=243+相相应的属性代的属性代码值8980010111000189620010111100198340010110100178190011110011168030011110010157870011110001147710011110000137060010101100
32、12642001010100011578001010010010514001010000092570001100000824300110011117227001100111062110011001101519500110011004130001000100036600100001002200100000001十进制码十进制码二进制码二进制码叶结点号叶结点号2基于四进制的线性四叉树编码基于四进制的线性四叉树编码对每个每个栅格格进展展编码得表得表a。检查相相邻4个个m码的属性的属性值，如一，如一样进展合并，除去最低展合并，除去最低值，。，。经过一次一次检测后，再后，再检测上上层相相邻四个四个块编码
33、的属性的属性值，如一，如一样再再合并。循合并。循环到没有能合并的子到没有能合并的子块为止，得表止，得表b。首先将首先将栅格格阵列的行列列的行列值分分别转换成二成二进制制码，得，得二二进制行号制行号Ib,列号列号Jb，然后求出四，然后求出四进制四叉制四叉树码MQ=2*Ib+Jb2线性四叉树及编码线性四叉树及编码3333323233222332322232221113313303213202312302212201103133123033022132122032021013113103013002112102012001001331321231220330320230220111311301211
34、20031030021020010113112103102013012003002001111110101100011010001000000111110101100011010001000 列号行号表表a333223223033023130130021200330320310300210100表表b000000100属性值属性值1101100100属性值属性值21201033032031030020100四进制码四进制码191817161514131211叶结叶结点号点号103393283173036302530143003232221四进制码四进制码叶结叶结点号点号四四进制的制的线性四叉性
35、四叉树编码四四进制制线性四叉性四叉树编码的特点：的特点：优点是便于点是便于实现行列行列值及其及其编码之之间的的转换；缺陷是存缺陷是存储开开销大，且普通大，且普通软件都不支持四件都不支持四进制。制。2基于四进制的线性四叉树编码基于四进制的线性四叉树编码2线性四叉树及编码线性四叉树及编码3基于十进制的线性四叉树编码基于十进制的线性四叉树编码编码：将二：将二进制的行列号按位交制的行列号按位交错陈列，可得到四叉列，可得到四叉树叶叶结点的二点的二进制地址制地址码，进而将二而将二进制制码转成十成十进制制码，得到四叉，得到四叉树编码。0 0 1 1 1 0行号行号=011010=列号列号MD=142线性四叉
36、树及编码线性四叉树及编码表表a经自下而上自下而上归并得表并得表b。依次。依次检查表表a中四个中四个相相邻叶叶结点的属性代点的属性代码能否一能否一样。假。假设一一样那么那么归并成一个父并成一个父结点，点，记下地址及代下地址及代码。否那么不。否那么不予予归并。然后再并。然后再归并更高一并更高一层父父结点，如此循点，如此循环，直到不能直到不能归并并为止。止。3)基于十进制的线性四叉树编码基于十进制的线性四叉树编码2线性四叉树及编码线性四叉树及编码636259584746434211161605756454441401105554515039383534101535249483736333210031
37、302726151411100112928252413129801023221918763200121201716541000011111010110001101000100060564440515052494836321514131281640表表a表表b060056052051050049148044040136132016115114013012180400属性值属性值MD码值码值属性值属性值MD码值码值0491480401320161140121800四叉四叉树游程游程编码特点：比四特点：比四进制制节省省储存空存空间，且前后两个，且前后两个MD码之之间差代表了叶差代表了叶结点的大小，点
38、的大小，还可可进一步利用一步利用游程游程编码对数据数据进展展紧缩。优点：具有可点：具有可变分辨率，能准确表示分辨率，能准确表示图形的形的细节部分，部分，编码效率高；具有区域性效率高；具有区域性质，适宜于，适宜于图形形图像的分析运算；便于像的分析运算；便于岛的分析。的分析。(3)基于十进制的线性四叉树编码基于十进制的线性四叉树编码2线性四叉树及编码线性四叉树及编码三四叉树优缺陷三四叉树优缺陷优点：优点：1对对于于团团块块图图像像，四四叉叉树树表表示示法法占占用用空空间间比比网网络络法法要要少少得得多多，四四叉叉树树表表示示法法根根本上是一种非冗余表示法。本上是一种非冗余表示法。2四四叉叉树树具具
39、有有可可变变率率或或多多重重分分辩辩率率的的特特点点使使得得它它有有很很好好的的运运用用前前景景，适适用用于于处处置置凝凝聚聚性性或或呈呈块块状状分分布布的的空空间间数数据据，特特别别适适用用于于处处置置分分布布不不均均匀匀的的块块状状空空间间数数据，但不适用于延续外表如地形或线状地物。据，但不适用于延续外表如地形或线状地物。此外，目前运用四叉树还存以下问题：此外，目前运用四叉树还存以下问题：1)矢矢/栅正反变换还不理想。栅正反变换还不理想。2)建立四叉树耗费机时很多。建立四叉树耗费机时很多。3)四叉树虽可修正，但很费事详细的数据构造中会提到四叉树虽可修正，但很费事详细的数据构造中会提到三四叉
40、树优缺陷三四叉树优缺陷4) 4) 四叉树未能直接表示物体间的拓扑关系。四叉树未能直接表示物体间的拓扑关系。5) 5) 与与非非树表表示示法法比比较，四四叉叉树表表示示法法的的缺缺陷陷在在于于转换的不的不稳定性或叫滑定性或叫滑动变异异例例如如，两两个个图像像的的差差别仅由由于于平平移移，就就会会构构成成极极为不不同同的的四四叉叉树，因因此此很很难根根据据四四叉叉树来来判判别这两两个个图像能否全同，故不利于做外形分析和方式像能否全同，故不利于做外形分析和方式识别， A 0A 1A 4A 5A 2 B 3B 6B 7A 8A 9B 12B 13A 10A 11B 14B 15AAAAABBBAABB
41、AABB6) 6) 一个物体的一个物体的图像在像在构成四叉构成四叉树时会被分割会被分割到假到假设干个象限中，使干个象限中，使它失去了内在的相关性。它失去了内在的相关性。AAAAABBBAABBAABB二、矢量数据构造二、矢量数据构造-概念概念一概念一概念矢量构造是表达空间数据的另一种常见矢量构造是表达空间数据的另一种常见数据构造，经过记录坐标的方式尽能够精数据构造，经过记录坐标的方式尽能够精确地表示点、线、多边形等地理实体确地表示点、线、多边形等地理实体。二、矢量数据构造二、矢量数据构造-二根本特征二根本特征点无大小、地理空点无大小、地理空间延延续。属性特征属性特征隐性表示。性表示。几何位置、
42、属性数据、拓扑关系分几何位置、属性数据、拓扑关系分别存存储。指向地物、指向地物、觉得宏得宏观几何几何实体无体无论大小，每个大小，每个实体均匀一条数体均匀一条数据据记录存存储，一条一条记录指向一个地物。指向一个地物。二、矢量数据构造二、矢量数据构造-三编码内容三编码内容独一独一标识符符空空间位置：位置：x,y坐坐标对拓扑关系拓扑关系属性特征属性特征时间特征特征二、矢量数据构造二、矢量数据构造-三编码内容三编码内容3.1点点实体体编码内容内容点点实体包括体包括单独一独一对x,y坐坐标定位的一定位的一切地切地理或制理或制图实体。体。点是空点是空间上不能再分的地理上不能再分的地理实体，可以是体，可以是
43、详细的或的或笼统的的。二、矢量数据构造二、矢量数据构造-三编码内容三编码内容3.1点点实体体二、矢量数据构造二、矢量数据构造-三编码内容三编码内容3.2线实体体由直由直线元素构成的各种元素构成的各种线性要素。性要素。线实体主要用来表示体主要用来表示线状地物符号状地物符号线和多和多边形形边境，有境，有时也称也称为“弧、弧、“链、“串等串等。线实体编码根本内容线实体编码根本内容二、矢量数据构造二、矢量数据构造-三编码内容三编码内容3.3多多边形形区域区域实体中，具有称号属性和分体中，具有称号属性和分类属性，多用多属性，多用多边形表示形表示。多多边形矢量形矢量编码不但要表示位置和属性，更不但要表示位
44、置和属性，更为重要的是要能表达区域的拓扑性重要的是要能表达区域的拓扑性质。二、矢量数据构造二、矢量数据构造-四矢量数据构造四矢量数据构造编码编码编码方法：编码方法：n无拓扑关系的编码方法：仅记录空间目的的无拓扑关系的编码方法：仅记录空间目的的位置和属性信息，而不记录拓扑关系。位置和属性信息，而不记录拓扑关系。n拓扑关系的编码方法：不仅记录空间目的的拓扑关系的编码方法：不仅记录空间目的的位置和属性信息，位置和属性信息，而且记录拓扑关系。而且记录拓扑关系。二、矢量数据构造二、矢量数据构造-四矢量数据构造四矢量数据构造编码编码4.1坐标序列法坐标序列法以多边形为单元进展组织。由多边形边境的以多边形为
45、单元进展组织。由多边形边境的x,y坐标对集合组成。坐标对集合组成。边境坐标数据与多边形单元实体一一对应，各个边境坐标数据与多边形单元实体一一对应，各个多边形的边境都有单独编码和数字化。多边形的边境都有单独编码和数字化。二、矢量数据构造二、矢量数据构造-四矢量数据构造四矢量数据构造编码编码4.1坐标序列法坐标序列法10：x1,y1；x2,y2；x3,y3；x4,y4；x5,y5；x6,y6；x7,y7；x8,y8；x9,y9；x10,y10；x11,y11；20：x1,y1；x12,y12；x13,y13；x14,y14；x15,y15； x16,y16；x17,y17；x18,y18；x19,
46、y19；x20,y20；x21,y21；x22,y22；x23,y23；x8,y8；x9,y9；x10,y10；x11,y11；30：x33,y33；x34,y34；x35,y35；x36,y36；x37,y37；x38,y38；x39,y39；x40,y40；40：x19,y19；x20,y20；x21,y21；x28,y28；x29,y29；x30,y30；x31,y31；x32,y32；50：x21,y21；x22,y22；x23,y23；x8,y8；x7,y7；x6,y6；x24,y24；x25,y25；x26,y26；x27,y27；x28,y28；二、矢量数据构造二、矢量数据构造-
47、四矢量数据构造四矢量数据构造编码编码4.1坐标序列法坐标序列法n优点：编码容易、数字化操作简单、数据编排直观。优点：编码容易、数字化操作简单、数据编排直观。n缺陷：缺陷：n多边形之间公共边境数字化两遍，数据冗余存储，多多边形之间公共边境数字化两遍，数据冗余存储，多边形边境容易出现间隙或重叠。边形边境容易出现间隙或重叠。n短少的多边形的邻域信息和图形的拓扑关系。短少的多边形的邻域信息和图形的拓扑关系。n岛作为一个单独的图形，没有建立与外界多边形的联岛作为一个单独的图形，没有建立与外界多边形的联络。络。二、矢量数据构造二、矢量数据构造-四矢量数据构造四矢量数据构造编码编码4.2树状索引构造编码树状
48、索引构造编码采用树状索引，以减少数据冗余并间接添加邻域采用树状索引，以减少数据冗余并间接添加邻域信息。信息。详细方法：对一切边境点进展数字化，将坐标对详细方法：对一切边境点进展数字化，将坐标对以顺序方式存储，由点索引与边境号相联络，以以顺序方式存储，由点索引与边境号相联络，以线索引与各多边形相联络，构成树状索引构造。线索引与各多边形相联络，构成树状索引构造。二、矢量数据构造二、矢量数据构造-四矢量数据构造四矢量数据构造编码编码4.2树状索引构造编码树状索引构造编码数据记录方式：数据记录方式：多边形文件多边形文件多边形与线索引文件多边形与线索引文件线文件线文件边境限与点索引文件边境限与点索引文件
49、点文件点文件点文件：点号点文件：点号x,y坐坐标线文件：文件：线号号起点起点终点点点号序列点号序列多多边形文件：多形文件：多边形号形号边境限号序列境限号序列例：例：P148-P149索索索索引引引引式式式式 B BC CD DE Ea ab bc cf fg gh he ef fi ib bc ci ij j1 12 23 34 45 56 67 78 89 91010111112121313141415151616171718181919202021212222232324242525262627272828292930303131线线线与多与多与多与多与多与多边边边形之形之形之形之形之形之
50、间间间的的的的的的树树树状索引状索引状索引状索引状索引状索引 点与点与点与点与点与点与边边边境限之境限之境限之境限之境限之境限之间间间的的的的的的树树树状索引状索引状索引状索引状索引状索引 二、矢量数据构造二、矢量数据构造-四矢量数据构造四矢量数据构造编码编码4.2树状索引构造编码树状索引构造编码n优点：数据冗余小、编排直观、邻域信息和岛状信息优点：数据冗余小、编排直观、邻域信息和岛状信息n可以得到一定处置。可以得到一定处置。n缺陷：缺陷：n运算繁琐。运算繁琐。n邻接与包含关系处置困难。邻接与包含关系处置困难。n编码表要人工建立，任务量大、易出错。编码表要人工建立，任务量大、易出错。二、矢量数
51、据构造二、矢量数据构造-四矢量数据构造四矢量数据构造编码编码4.3双重独立构造编码双重独立构造编码DIME采用拓扑编码构造，以线文件为编码主体。采用拓扑编码构造，以线文件为编码主体。数据记录方式：数据记录方式：点文件：点号点文件：点号x,y坐坐标线文件：文件：线号号起点起点终点点左多左多边形号形号右多右多边形号形号特点：特点：数据冗余进一步减少，数据检核、更新和检数据冗余进一步减少，数据检核、更新和检索方便，能自动消费多边形文件。索方便，能自动消费多边形文件。二、矢量数据构造二、矢量数据构造-四矢量数据构造四矢量数据构造编码编码4.3双重独立构造编码双重独立构造编码11k12345678910
52、abcdefhijlg线号线号左多边形左多边形右多边形右多边形起点起点终点终点a12b23c34.k01011l0114线文件线文件二、矢量数据构造二、矢量数据构造-四矢量数据构造四矢量数据构造编码编码4.4链状双重独立构造链状双重独立构造是对是对DIMEDIME方法的一种改良。方法的一种改良。DIME DIME 中一条边只能由直线两端点及相邻面域中一条边只能由直线两端点及相邻面域表示，而这种方法可以将假设干线段合为一个表示，而这种方法可以将假设干线段合为一个弧段，每个弧段有许多中间点，其端点那么为弧段，每个弧段有许多中间点，其端点那么为弧段的交点或起始点。弧段的交点或起始点。二、矢量数据构造
53、二、矢量数据构造-四矢量数据构造四矢量数据构造编码编码4.4链状双重独立构造链状双重独立构造弧段坐标文件：一系列点的位置坐标组成。弧段坐标文件：一系列点的位置坐标组成。弧段文件：弧记录组成记录弧的起止点号和弧段文件：弧记录组成记录弧的起止点号和左右多边形号。左右多边形号。多边形文件：多边形记录组成多边形号、有多边形文件：多边形记录组成多边形号、有关弧段号，周长、面积、中心点坐标、岛状区关弧段号，周长、面积、中心点坐标、岛状区域信息。域信息。二、矢量数据构造二、矢量数据构造-四矢量数据构造四矢量数据构造编码编码线号线号坐标坐标AX1,y1;X2,y2;X3,y3;X4,y4BX1,y1;X10,
54、y10;X11,y11;X4,y4CX4,y4;X8,y8;X9,y9;X1,y1DX5,y5;X6,y6;X7,y7;X5,y5线号线号起点起点终点终点左多边形左多边形右多边形右多边形A14B140C410D55C11k12345678910abcdefhijlgABD多边形号多边形号弧段号弧段号起始结点起始结点周长周长面积面积中心点坐标中心点坐标A，B1A，C，D1D5弧弧段段坐坐标标文文件件弧弧段段文文件件多多边边形形文文件件三、栅格三、栅格-矢量数据一体化构造矢量数据一体化构造-比较比较矢量矢量栅格栅格基基本本特特征征点的认识点的认识点无大小点无大小点有大小点有大小地图空间地图空间延续
55、延续离散离散数据指向数据指向地物地物位置位置属性显示属性显示隐式隐式显式显式使使用用效效果果数据构造数据构造复杂复杂简单简单数据量数据量小小大大数据精度数据精度高高低低输出效果输出效果优优劣劣3.1两种数据构造的比较两种数据构造的比较三、栅格三、栅格-矢量数据一体化构造矢量数据一体化构造-比较比较矢量矢量栅格栅格数数据据操操作作几何变形几何变形易易难难投影变换投影变换易易难难网络分析网络分析易易难难数据交融数据交融难难易易数学分析数学分析难难易易叠加分析叠加分析难难易易运用范围运用范围数据采集、数据采集、存储存储数据运算、数据运算、分析分析三、栅格三、栅格-矢量数据一体化构造矢量数据一体化构造
56、-互换互换3.2两种数据构造的互换两种数据构造的互换一、点的转换一、点的转换矢量构造：矢量构造：X,Y坐标精度的变化坐标精度的变化栅格构栅格构造：行，列造：行，列二、线的转换二、线的转换矢量构造矢量构造点的内插点的内插栅格构造栅格构造：数据精：数据精度降低度降低栅格构造栅格构造点的紧缩点的紧缩矢量构造矢量构造：坐标精：坐标精度提高度提高三、面的转换三、面的转换矢量构造矢量构造栅格构造栅格构造：多边形填充：多边形填充栅格构造栅格构造矢量构造矢量构造：矢量化：矢量化3.2两种数据构造的互换两种数据构造的互换-矢量向栅格转矢量向栅格转换换矢量数据的坐标是直角坐标，原点为图的左下方；矢量数据的坐标是直
57、角坐标，原点为图的左下方；栅格数据的坐标是行列坐标，原点在图的左上方。栅格数据的坐标是行列坐标，原点在图的左上方。在进展两种坐标数据转换时，通常使直角坐标的在进展两种坐标数据转换时，通常使直角坐标的x x，y y轴分别同栅格数据的行、列平行。轴分别同栅格数据的行、列平行。 3.2两种数据构造的互换两种数据构造的互换-矢量向栅格转矢量向栅格转换换 确定确定栅格格单元的大小元的大小矢量数据向栅格数据转换时，首先必需确定栅格矢量数据向栅格数据转换时，首先必需确定栅格元素的大小，即分辨率。元素的大小，即分辨率。根据原矢量图的大小，精度要求、所研讨问题的根据原矢量图的大小，精度要求、所研讨问题的性质和存
58、储空间，确定栅格的分辨率。性质和存储空间，确定栅格的分辨率。 3.2两种数据构造的互换两种数据构造的互换-矢量向栅格转矢量向栅格转换换3.2两种数据构造的互换两种数据构造的互换-矢量向栅格转矢量向栅格转换换 点的点的转换点的点的转换本本质上是将点的矢量坐上是将点的矢量坐标转换成成栅格数据中行列格数据中行列值i和和j，从而得，从而得到点所在到点所在栅格元素的位置。格元素的位置。坐标精度的变化坐标精度的变化3.2两种数据构造的互换两种数据构造的互换-矢量向栅格转矢量向栅格转换换 线的的转换曲曲线可用折可用折线来表示的，也就是当折来表示的，也就是当折线上取点足上取点足够多多时，所画的折，所画的折线在
59、在视觉上成上成为曲曲线。因此，。因此，线的的变换本本质上是完成相上是完成相邻两点之两点之间直直线的的转换。 其转换过程不仅包括坐标点其转换过程不仅包括坐标点A A，B B分别从点矢量分别从点矢量数据转换成栅格数据，还包括求出直线数据转换成栅格数据，还包括求出直线ABAB所经过所经过的中间栅格数据。的中间栅格数据。3.2两种数据构造的互换两种数据构造的互换-矢量向栅格转矢量向栅格转换换 线的的转换详细转换过程：详细转换过程： 利用上述点转换法，将点利用上述点转换法，将点A(x1A(x1，y1)y1)，B(x2B(x2，y2)y2)分分别转换成栅格数据，求出别转换成栅格数据，求出相应的栅格的行、列
60、值。相应的栅格的行、列值。 由上述行列值求出直线所由上述行列值求出直线所在行列值的范围。在行列值的范围。 确定直线经过的中间栅格确定直线经过的中间栅格列值。列值。 3.2两种数据构造的互换两种数据构造的互换-矢量向栅格转矢量向栅格转换换 线的的转换1)1)求出相求出相应i i行中心行中心处同直同直线相交的相交的y y值 。2)2)用直用直线方程求出方程求出对应y y值的点的的点的x x值 。3)3)从从x x，y y值按公式求出相按公式求出相应i i行的列行的列值j j。 YX0,03.2两种数据构造的互换两种数据构造的互换-矢量向栅格转矢量向栅格转换换 线的的转换根据上述根据上述过程，依次求
61、出直程，依次求出直线经过的每个网格的每个网格单元，并用直元，并用直线的属性的属性值去去填充填充这些网格，就完成了些网格，就完成了线的的转换。整个曲。整个曲线或多或多边形形边境境经分段延分段延续运算运算即可以完成即可以完成转换。 于此类似，可以先计算出两个端点的列值，知于此类似，可以先计算出两个端点的列值，知道直线要经过的列，然后计算各列中心线的道直线要经过的列，然后计算各列中心线的Y Y值，值，再求出相应的行数再求出相应的行数I I。3.2两种数据构造的互换两种数据构造的互换-矢量向栅格转矢量向栅格转换换 面的填充面的填充矢量数据构造中面域用边境限表示，面域内部矢量数据构造中面域用边境限表示，
62、面域内部是空心的；栅格数据构造中整个面域都要用属是空心的；栅格数据构造中整个面域都要用属性值填充，因此，边境限转换完以后，必需进性值填充，因此，边境限转换完以后，必需进展面域属性值的填充。展面域属性值的填充。常用算法：常用算法：1.内部点分散算法内部点分散算法2.复数积分算复数积分算法法3.射线法射线法4.扫描算法扫描算法5.边境代数算法边境代数算法3.2两种数据构造的互换两种数据构造的互换-矢量向栅格转矢量向栅格转换换 面的填充面的填充内部点分散算法内部点分散算法 该该算算法法由由每每个个多多边边形形一一个个内内部部点点种种子子点点开开场场，向向其其八八个个方方向向的的邻邻点点分分散散，判判
63、别别各各个个新新参参与与点点能能否否在在多多边边形形边边境境上上，假假设设是是边边境境上上，那那么么该该新新参参与与点点不不作作为为种种子子点点，否否那那么么把把非非边边境境点点的的邻邻点点作作为为新新的的种种子子点点与与原原有有种种子子点点一一同同进进展展新新的的分分散散运运算算，并并将将该该种种子子点点赋赋以以该该多多边边形的编号。形的编号。 3.2两种数据构造的互换两种数据构造的互换-矢量向栅格转矢量向栅格转换换 面的填充面的填充复数复数积分算法分算法 对对全全部部栅栅格格阵阵列列逐逐个个栅栅格格单单元元地地判判别别该该栅栅格格归归属属的的多多边边形形编编码码，判判别别方方法法是是由由待
64、待判判点点对对每每个个多多边边形形的的封封锁锁边边境境计计算算复复数数积积分分，对对某某个个多多边边形形，假假设设积积分分值值为为2 2 i i，那那么么该该待待判判点点属属于于此此多多边边形形，赋赋以以多多边边形形编编号号，否否那那么么在在此此多多边形外部，不属于该多边形。边形外部，不属于该多边形。 3.2两种数据构造的互换两种数据构造的互换-矢量向栅格转矢量向栅格转换换 面的填充面的填充射射线算法算法 射射线线算算法法可可逐逐点点判判别别数数据据栅栅格格点点在在某某多多边边形形之之外外或或在在多多边边形形内内，由由待待判判点点向向图图外外某某点点引引射射线线，判判别别该该射射线线与与某某多
65、多边边形形一一切切边边境境相相交交的的总总次次数数，如如相相交交偶偶数数次次，那那么么待待判判点点在在该该多多边边形形外外部部，如如为为奇奇数数次次，那那么么待待判判点点在在该该多多边边形形内部内部 采采用用射射线线算算法法，要要留留意意的的是是：射射线线与与多多边边形形边边境境相相交交时时，有有一一些些特特殊殊情情况况会会影影响响交交点点的的个数，必需予以排除。个数，必需予以排除。 射线算法射线算法 射线算法的特殊情况射线算法的特殊情况 3.2两种数据构造的互换两种数据构造的互换-矢量向栅格转矢量向栅格转换换 面的填充面的填充扫描算法描算法扫扫描描算算法法是是射射线线算算法法的的改改良良，将
66、将射射线线改改为为沿沿栅栅格格阵阵列列,列列或或行行方方向向扫扫描描线线，常常用用的的方方法法有有：平行线扫描法和铅垂线跌落法。平行线扫描法和铅垂线跌落法。3.2两种数据构造的互换两种数据构造的互换-矢量向栅格转矢量向栅格转换换 面的填充面的填充扫描算法描算法n 平平行行线线扫扫描描法法：从从待待检检验验的的栅栅格格单单元元作作一一平平行行于于x x 轴轴的的扫扫描描线线，当当与与多多边边形形相相交交的的点点数数为为偶偶数数时时，那那么么该该栅栅格格在在多多边边形形之之外外，当当交交点点为为奇奇数数时时，该该栅栅格格在多边形之内。在多边形之内。n有有时时也也会会出出现现极极值值点点的的情情况，
67、就会出现错误判别。况，就会出现错误判别。PQRabcdgfeY X3.2两种数据构造的互换两种数据构造的互换-矢量向栅格转矢量向栅格转换换 面的填充面的填充扫描算法描算法n 铅铅垂垂线线跌跌落落法法：从从待待检检验验的的栅栅格格单单元元作作一一垂垂直直于于x x 轴轴的的直直线线，检检查查它它与与多多边边形形边边境境交交点点的的点点数数，偶偶数数时时在在多多边边形形之之外外，奇奇数数时时在多边形之内。在多边形之内。n为为了了防防止止错错误误可可同同时时采采用用这这两两种种算算法法，只只需需一一种种方方法法交交点点为为奇奇数数，该该点点就就在在多边形之内。多边形之内。PQRabcdgfeY X3
68、.2两种数据构造的互换两种数据构造的互换-矢量向栅格转矢量向栅格转换换 面的填充面的填充边境代数算法境代数算法 任伏虎任伏虎 单个多个多边形形n初始化栅格阵列，一切单元赋值为初始化栅格阵列，一切单元赋值为0。n欲填充多边形值为欲填充多边形值为a。n以栅格行列为参考坐标轴，以多边形边境上某一点为起以栅格行列为参考坐标轴，以多边形边境上某一点为起始点顺时针方向搜索边境。始点顺时针方向搜索边境。n边境上行时，左侧同行栅格单元值边境上行时，左侧同行栅格单元值-a。n边境下行时，左侧同行栅格单元值边境下行时，左侧同行栅格单元值+a。n回到起点，构成栅格多边形。回到起点，构成栅格多边形。3.2两种数据构造
69、的互换两种数据构造的互换-矢量向栅格转矢量向栅格转换换3.2两种数据构造的互换两种数据构造的互换-矢量向栅格转矢量向栅格转换换 面的填充面的填充边境代数算法境代数算法多个多多个多边边形形对对每每幅幅地地图图的的全全部部具具有有左左右右多多边边形形编编号号的的边边境境弧弧段段, ,沿沿其其前前进进的的方方向向逐逐个个搜搜索索, ,当当边边境境上上行行时时, ,将将边边境境限限位位置置与与左左图图框框之之间间的的网网格格点点加加上上一一个个值值=(=(左左多多边边形形编编号号- -右右多多边边形形编编号号););当当边边境境下下行行时时, ,将将边边境境限限位位置置与与左左图图框框之之间间的的网网
70、格格点点加加上上一一个个值值=(=(右右多多边边形形编编号号- -左左多多边边形形编编号号););当边境平行栅格行行走时当边境平行栅格行行走时, ,不做运算。不做运算。3.2两种数据构造的互换两种数据构造的互换-矢量向栅格转矢量向栅格转换换3.2两种数据构造的互换两种数据构造的互换-栅格向矢量转栅格向矢量转换换 从栅格单元转换到几何图形的过程称为矢量化。从栅格单元转换到几何图形的过程称为矢量化。 矢矢量量化化过过程程中中，到到达达某某个个单单元元值值与与周周围围均均不不同同，那那么么该该单单元元代代表表一一个个点点。假假设设具具有有某某一一属属性性值值的的单单元元是是延延续续的的可可将将它它们
71、们搜搜索索出出来来，并并细细化化处处置置, ,取取中中间间的的单单元元衔衔接接成成的的位位置置作作为为一一条条线线。对对面面状状图图形形的的处处置置要要复杂一些。复杂一些。 o基于图像处置的矢量化基于图像处置的矢量化o基于窗口匹配的矢量化基于窗口匹配的矢量化 3.2两种数据构造的互换两种数据构造的互换-栅格向矢量转栅格向矢量转换换分类图分类图影像图影像图扫描图扫描图边境值提取边境值提取二值化二值化二值化二值化细化细化编辑编辑矢量化矢量化n 一种是本身为遥感影像图或栅格化的分类图，矢量化之前必需进展边境提取，再将其处置成近似线划图的二值图像，才干转换成矢量数据。n 一种是线划图扫描得到的栅格图，
72、二值化后的线划宽度往往占据多个栅格，此时需求细化处置后才干矢量化。o基于图像处置的矢量化基于图像处置的矢量化o二值化二值化o将图像中的灰度取一个阈值，凡高于阈值将图像中的灰度取一个阈值，凡高于阈值的灰度取的灰度取1 1，低于阈值的灰度取，低于阈值的灰度取0 0。设阈值。设阈值为为 ，那么二值化后的像元灰度值为：，那么二值化后的像元灰度值为：o式中式中f(i,j)f(i,j)为原像元灰度。为原像元灰度。o二值图像中的图形用二值图像中的图形用1 1表示，背景用表示，背景用0 0表示。表示。3.2两种数据构造的互换两种数据构造的互换-栅格向矢量转栅格向矢量转换换o细化细化o 也称为栅格数据的轴化，就
73、是将占也称为栅格数据的轴化，就是将占用多个栅格宽度的用多个栅格宽度的o图形要素缩减为只需单个栅格宽度的图形图形要素缩减为只需单个栅格宽度的图形要素的过程。要素的过程。o剥皮法剥皮法o骨架法骨架法 3.2两种数据构造的互换两种数据构造的互换-栅格向矢量转栅格向矢量转换换1 1剥剥 皮皮 法法n概念：剥皮法就是每次删掉外层的一些栅格，直到最后概念：剥皮法就是每次删掉外层的一些栅格，直到最后n 留下彼此连通的由单个栅格组成的图形。留下彼此连通的由单个栅格组成的图形。n详细做法：用一个详细做法：用一个3*33*3的栅格窗口，在栅格图上逐个检查的栅格窗口，在栅格图上逐个检查每个栅格元。被查栅格能否删去，
74、由以该栅格为中心的每个栅格元。被查栅格能否删去，由以该栅格为中心的组合图来决议。组合图来决议。n原那么：不允许剥去会导致图形不连通的栅格，也不能原那么：不允许剥去会导致图形不连通的栅格，也不能在图形中构成孔。在图形中构成孔。n栅格组合图栅格组合图2、3、4、5、10、11、12、16、21、24、28、33、34、35、38、42、43、46、50可将中心点剥去的组合格式有19种：n详细做法详细做法n扫描全图，凡是像元值为扫描全图，凡是像元值为1 1的栅格都用的栅格都用V V值取值取代。代。V V值是该栅格与北、东和北东三个相邻值是该栅格与北、东和北东三个相邻栅格像元值之和，即栅格像元值之和，
75、即 n在在V V值图上保管最大值图上保管最大V V值的栅格，删去其他栅值的栅格，删去其他栅格，但必需保证连通。由于最大格，但必需保证连通。由于最大V V值的栅格值的栅格只能分布在图形的中心线上骨架上，因只能分布在图形的中心线上骨架上，因此选取最大值栅格的过程就是细化的过程。此选取最大值栅格的过程就是细化的过程。 2 2骨骨 架架 法法110000111000011100001100011100001100241031000000040334412200000000004200110000000000010001100000000000001000p 跟跟 踪踪n细化后的二值图像构成了骨架图，跟
76、踪就细化后的二值图像构成了骨架图，跟踪就n 是把骨架转换为矢量图形的坐标序列。是把骨架转换为矢量图形的坐标序列。l 类似于栅格采用链码的栅格跟踪过程，找出线类似于栅格采用链码的栅格跟踪过程，找出线段经过的栅格。段经过的栅格。l 将栅格将栅格i i，j j坐标转换成直角坐标坐标转换成直角坐标X,YX,Y格网中心点坐标：格网中心点坐标：p 跟跟 踪踪其根本步其根本步骤为：1.1.从左向右，从上向下搜索从左向右，从上向下搜索线划起始点，并划起始点，并记下坐下坐标。2.2.朝朝该点的点的8 8个方向追踪点，假个方向追踪点，假设没有，那么没有，那么本条本条线的追踪的追踪终了，了，转(1)(1)进展下条展
77、下条线的追踪；否那么的追踪；否那么记下坐下坐标。3.3.把搜索点移到新取的点上，把搜索点移到新取的点上，转22。3.2两种数据构造的互换两种数据构造的互换-栅格向矢量转栅格向矢量转换换 根本步根本步骤： 多多边形形( (面面实体体) )的的栅格格数数据据向向矢矢量量数数据据的的转换本本质上上就就是是将将空空间具具有有一一样属属性性代代码的的栅格格象象元元集集合合表表示示为以以边境境弧弧段段以以及及边境境的的拓拓扑扑信信息息所所确定的多确定的多边形区域。形区域。多多边形形边境提取境提取边境限追踪境限追踪拓扑关系生成拓扑关系生成去除多余点及曲去除多余点及曲线圆滑滑o基于窗口匹配的矢量化基于窗口匹配
78、的矢量化 3.2两种数据构造的互换两种数据构造的互换-栅格向矢量转栅格向矢量转换换 双双边境搜索算法境搜索算法 根本思想根本思想: :经过边境提取境提取, ,将左右多将左右多边形信息保管形信息保管在在边境点上境点上, ,每条每条边境弧段由两个并行的境弧段由两个并行的边境境链组成成, ,以分以分别记录该边境弧段的左右多境弧段的左右多边形形编号。号。详细步步骤： 边境点和境点和结点的提取。点的提取。 边境限搜索与左右多境限搜索与左右多边形信息形信息记录。 多余点去除。多余点去除。3.2两种数据构造的互换两种数据构造的互换-栅格向矢量转栅格向矢量转换换 边境点和境点和结点的提取：点的提取：以以2*2
79、2*2栅格阵列作为活动窗口，沿行、列方向扫描全栅格阵列作为活动窗口，沿行、列方向扫描全图，由此区域内的四个栅格数据的组合方式断定。图，由此区域内的四个栅格数据的组合方式断定。 1) 1)假设四个栅格仅有两个不同编号且对角线上编号假设四个栅格仅有两个不同编号且对角线上编号不完全一样，那么为边境点，并保管各栅格一切多不完全一样，那么为边境点，并保管各栅格一切多边形编号。边形编号。 2) 2)假设四个栅格有三个或四个不同的编号为结点。假设四个栅格有三个或四个不同的编号为结点。 3) 3)假设四个栅格有二个不同的编号且对角线上编号假设四个栅格有二个不同的编号且对角线上编号完全一样为结点。完全一样为结点
80、。3.2两种数据构造的互换两种数据构造的互换-栅格向矢量转栅格向矢量转换换 边境点和境点和结点的提取：点的提取：abcdaabcabacaabbababaaabaabaabbbbabbabcbabcaabccabbcabba边境点的6种情况结点的8种情况3.2两种数据构造的互换两种数据构造的互换-栅格向矢量转栅格向矢量转换换 边境限的搜索与左右多境限的搜索与左右多边形信息形信息记录：以某一个结点为起始点，向任一相邻单位搜索，搜以某一个结点为起始点，向任一相邻单位搜索，搜索方向由进入方向和本单位构造决议，到达另一结点索方向由进入方向和本单位构造决议，到达另一结点构成一条弧段，结点坐标由组成结点的
81、四个栅格单元构成一条弧段，结点坐标由组成结点的四个栅格单元的行列号决议，弧段左右多边形信息由边境点决议。的行列号决议，弧段左右多边形信息由边境点决议。 多余点的去除：多余点的去除：某一弧段上延续三点，假设满足直线方程，那么中某一弧段上延续三点，假设满足直线方程，那么中间一点予以去除。间一点予以去除。aabbababaaabaabaabbbabaa3.2两种数据构造的互换两种数据构造的互换-栅格向矢量转栅格向矢量转换换3.2两种数据构造的互换两种数据构造的互换-栅格向矢量转栅格向矢量转换换00000ba000a0000000000ba000a00000栅格多边形边境点和结点多余点去除边境搜索00
82、000ba000a0000000000ba000a000003.3栅格栅格-矢量数据一体化构造矢量数据一体化构造 矢量与栅格数据，按照传统的观念，以为是两类完矢量与栅格数据，按照传统的观念，以为是两类完全不同性质的数据构造，当利用它们来表达空间目的时，全不同性质的数据构造，当利用它们来表达空间目的时，对于线状实体，人们习惯运用矢量数据构造。对于面状对于线状实体，人们习惯运用矢量数据构造。对于面状实体，在基于矢量的实体，在基于矢量的GISGIS中，主要运用边境表达法，而中，主要运用边境表达法，而在基于栅格的在基于栅格的GISGIS中，普通用元子空间填充表达法。中，普通用元子空间填充表达法。 由此
83、，人们联想到对用矢量方法表示的线状实体，由此，人们联想到对用矢量方法表示的线状实体，是不是也可以采用元子空间填充法来表示，即在数字化是不是也可以采用元子空间填充法来表示，即在数字化一个线状实体时，除记录原始取样点外，还记录所经过一个线状实体时，除记录原始取样点外，还记录所经过的栅格。同样，每个面状地物除记录它的多边形边境外，的栅格。同样，每个面状地物除记录它的多边形边境外，还记录中间包含的栅格。还记录中间包含的栅格。 为了建立矢量与栅格一体化数据构造，要对点、线、面目的数据构造的存储要求作如下的一致商定: (1)(1)对点状目的，由于没有外形和面积，在计算机内部只需求表示该对点状目的，由于没有
84、外形和面积，在计算机内部只需求表示该点的一个位置数据及与结点关联的弧段信息。点的一个位置数据及与结点关联的弧段信息。(2)(2)对线状目的，它有外形，但没有面积，在计算机内部需用一组元对线状目的，它有外形，但没有面积，在计算机内部需用一组元子来填满整个途径，并表示该弧段相关的拓扑信息。子来填满整个途径，并表示该弧段相关的拓扑信息。(3)(3)对面状目的，它既有外形，又有面积，在计算机内部需表示由元对面状目的，它既有外形，又有面积，在计算机内部需表示由元子填满途径的组边境和由边境组成的紧凑空间子填满途径的组边境和由边境组成的紧凑空间 。3.3栅格栅格-矢量数据一体化构造矢量数据一体化构造 由于由
85、于栅格数据构造的格数据构造的精度精度较低，需利用低，需利用细分格分格网的方法，来提高点、网的方法，来提高点、线和面状目的和面状目的边境限的数据境限的数据表达精度。在有点、表达精度。在有点、线目目的的经过的根本格网内，再的根本格网内，再细分成分成256256256256个个细格网。格网。当精度要求当精度要求较低低时，也可，也可以以细分成分成16l616l6个个细格网格网 。3.3栅格栅格-矢量数据一体化构造矢量数据一体化构造 为使数据格式一致，根本为使数据格式一致，根本格网和细分格网都采用线性四格网和细分格网都采用线性四叉树的编码方法，将采样点和叉树的编码方法，将采样点和线性目的与根本格网的交点
86、用线性目的与根本格网的交点用两个两个MortonMorton码表示码表示( (均用十进均用十进制制MortonMorton码，简称码，简称M M码码) )。其中，其中，M1M1表示该点表示该点( (取样点或取样点或附加的交叉点附加的交叉点) )所在的根本格所在的根本格网地址码，网地址码，M2M2表示该点对应的表示该点对应的细分格网的细分格网的MortonMorton码，即码，即M1M1和和M2M2是将同一对是将同一对X X、Y Y坐标转换成坐标转换成的两个的两个MortonMorton码。码。 3.3栅格栅格-矢量数据一体化构造矢量数据一体化构造1 1、点状地物和结点的数据构造、点状地物和结点
87、的数据构造 3.3栅格格-矢量数据一体化构造矢量数据一体化构造设计点状地物仅有位置、没有外形和面积，不用将点状地物点状地物仅有位置、没有外形和面积，不用将点状地物作为一个覆盖层分解为四叉树，只需将点的坐标转化为作为一个覆盖层分解为四叉树，只需将点的坐标转化为地址码地址码M1 M1 和和M2 ,M2 ,而不论整个构形能否为四叉树。而不论整个构形能否为四叉树。 这种构造简单灵敏，便于点的插入和删除，还能处置这种构造简单灵敏，便于点的插入和删除，还能处置一个栅格内包含多个点状目的的情况。一切点状地物一个栅格内包含多个点状目的的情况。一切点状地物以及弧段之间的结点可以用一个文件表示。以及弧段之间的结点
88、可以用一个文件表示。 1 1、点状地物和结点的数据构造、点状地物和结点的数据构造 3.3栅格格-矢量数据一体化构造矢量数据一体化构造设计点标识号点标识号M1M2高程高程Z 10025434082432100261057725463 2 2、线状地物的数据构造、线状地物的数据构造 3.3栅格格-矢量数据一体化构造矢量数据一体化构造设计 线状地物有外形没有线状地物有外形没有面积，和点状地物一样不面积，和点状地物一样不用用一个完全的覆盖层分用用一个完全的覆盖层分解四叉树，而只需用一串解四叉树，而只需用一串数据表达每个线状地物的数据表达每个线状地物的途径即可。途径即可。2 2、线状地物的数据构造、线状
89、地物的数据构造 3.3栅格格-矢量数据一体化构造矢量数据一体化构造设计 一个线状地物能够有几条弧段组成，所以应先建立一个线状地物能够有几条弧段组成，所以应先建立一个弧段数据文件一个弧段数据文件 。 一条弧段的中间点不仅包含原始取样点，而且要将一条弧段的中间点不仅包含原始取样点，而且要将该线状地物经过的一切栅格的地址全部记录下来。该线状地物经过的一切栅格的地址全部记录下来。2 2、线状地物的数据构造、线状地物的数据构造 3.3栅格格-矢量数据一体化构造矢量数据一体化构造设计弧标识号弧标识号起始点号起始点号终止点号终止点号中间点串中间点串M1,M2，Z 20078100251002658,749,
90、435,92,4377,43920079100261003290,432,502,112,4412,496 线标识号线标识号弧段标识号弧段标识号 3003120078,200793003220212,20218,20219 2 2、线状地物的数据构造、线状地物的数据构造 3.3栅格格-矢量数据一体化构造矢量数据一体化构造设计 这种数据构造比单纯的矢量构造添加了一定的存储这种数据构造比单纯的矢量构造添加了一定的存储量，但它处理了线状地物的四叉树表达问题，使它与点量，但它处理了线状地物的四叉树表达问题，使它与点状、面状地物一同建立一致的基于线性四叉树编码的数状、面状地物一同建立一致的基于线性四叉树
91、编码的数据构造体系。这对于点状地物与线状地物相交，线状地据构造体系。这对于点状地物与线状地物相交，线状地物之间的相交，以及线状地物与面状地物相交的查讯问物之间的相交，以及线状地物与面状地物相交的查讯问题变得相当简便和快速。题变得相当简便和快速。 3 3、面状地物的数据构造、面状地物的数据构造 3.3栅格格-矢量数据一体化构造矢量数据一体化构造设计 根据对面状地物的商定，一个面状地物应记录边境根据对面状地物的商定，一个面状地物应记录边境和边境所包围的整个面域。其中边境由弧段组成，它同和边境所包围的整个面域。其中边境由弧段组成，它同样援用弧段构造表的弧段信息。面域信息那么由线性四样援用弧段构造表的
92、弧段信息。面域信息那么由线性四叉叉树或二维行程编码表示。树或二维行程编码表示。 3.3栅格格-矢量数据一体化构造矢量数据一体化构造设计3.3栅格格-矢量数据一体化构造矢量数据一体化构造设计3.3栅格格-矢量数据一体化构造矢量数据一体化构造设计带指针的二维行程表带指针的二维行程表弧段文件弧段文件面文件面文件3.3栅格格-矢量数据一体化构造矢量数据一体化构造设计这种数据构造是面向地物的，具有矢量的特点。这种数据构造是面向地物的，具有矢量的特点。经过面状地物的标识号可以找到它的边境弧段经过面状地物的标识号可以找到它的边境弧段并顺着指针提取一切的中间面块。同时它又具并顺着指针提取一切的中间面块。同时它
93、又具有栅格的全部特性，二维行程本身就是面向位有栅格的全部特性，二维行程本身就是面向位置的构造，置的构造，MortonMorton码表达了位置的相互关系，码表达了位置的相互关系，前后前后M M码之差隐含了该子块的大小。给出恣意码之差隐含了该子块的大小。给出恣意一点的位置都可在带指针的二维行程表中顺着一点的位置都可在带指针的二维行程表中顺着指针找到面状地物的标识号确定是哪一个地物。指针找到面状地物的标识号确定是哪一个地物。 4 4、复杂地物的数据构造、复杂地物的数据构造 3.3栅格格-矢量数据一体化构造矢量数据一体化构造设计由几个或几种点、线、面状简单地物组成的地物称为复由几个或几种点、线、面状简单地物组成的地物称为复杂地物。杂地物。例如将一条公路上的中心线、交通灯、立交桥等组合为例如将一条公路上的中心线、交通灯、立交桥等组合为一个复杂地物，用一个标识号表示。一个复杂地物，用一个标识号表示。
