地图数据结构1

1、地图数据结构 空间实体的分类 地图学中，把地理空间的实体分为点、线、 面三种要素，分别用点状、线状、面状符 号来表示。 点实体 有特定位置，维数为0的实体 1 实体点：用来代表一个实体 2 注记点：用来定位注记 3 内点：用于记录多边形的属性，存在于多 边形内 4 节点：表示线的终点和起点 5 拐点：表示线段和弧段的内部点 线实体 维数为1 线段、线列、弧段、链、路径、多边线等 特征： 1 实体长度 2 弯曲度 3 方向性 面实体 面实体是维数为2的实体 特征： 1 周长 2 面积 3 独立或与其他地物的邻近性 4 内岛或齿状外形 5 重叠性与非重叠性 1、三条道路在不同的空间位置，称为定位信

2、息 2、三条分别具有不同等级，称为属性信息 3、三条道路互相具有邻接关系。主干道与次干道在结点 处相邻接，主干道的结点和相邻接，结点分别 与三条路段、和相关联等，称为拓扑关系称为拓扑关系；C3 在C6称的左边，称为方位关系方位关系；不同的道路之间有一定的距 离，称为度量关系度量关系。 4、随着时间的推移，道路还将发生变化，称为时间特征。 地图数据的基本特征 空间特征 属性特征 时间特征 空间特征 1 空间位置 空间位置用以描述事物或现象的地理位置，又称 几何特征、定位特征。 2 空间关系 空间关系指地理空间实体之间存在的一些具有空 间特性的关系，主要包含： 拓扑关系 方位关系 度量关系 属性特

3、征 属性特征用以描述事物或现象的特性，如 事物或现象的类别、等级、数量、名称等。 定性属性数据 定量属性数据 时间特征 时间特征描述地理实体随着时间而变化的 特征。 地图数据的基本类型 根据地图数据的特征，可以把地图数据分 为空间数据、关系数据、属性数据。 空间数据是描述地图要素中空间特征部分 的数据，也叫几何数据。 关系数据是描述空间数据之间的空间关系 的数据。 属性数据描述空间实体属性特征的数据。 空间数据 可分为点、线、面三种类型。 点类型 线类型 面类型 关系数据 关系数据是描述空间数据之间的空间关系 的数据，这儿说的是拓扑关系数据。 最常见的空间实体关系有6种： 点-点、点-线、点-

4、面、线-线、线-面、面- 面 拓扑关系主要有邻接、关联、相交、相离、 包含、重合等。 属性数据 描述空间实体属性特征的数据，描述地理 现象或地理实体的定性或定量指标。 地图的数据结构 几何数据以什么形式在计算机中存储和处 理。 矢量数据结构 栅格数据结构 矢量数据结构 矢量数据结构是表达地图空间数据的一种 常见的数据结构，通过记录坐标值的方式 尽可能精确的表示呈点、线或面状分布的 地理实体。 点：由一对x,y坐标表示 线：由一串有序的x,y坐标对表示 面：由一串有序的且首尾坐标相同的x,y坐 标对表示。 矢量数据结构的表示 表示矢量数据的结构时，应考虑问题： 1 矢量数据的存储和处理 2 与属

5、性数据的联系 3 矢量数据之间的拓扑关系 矢量数据结构表示一般有两类： 1 简单矢量数据结构 2 拓扑数据结构 简单矢量数据结构 简单矢量数据结构不考虑拓扑关系，可用于 矢量数据的存储、处理、显示、输出及一般 的查询检索。有点、线、面三种基本的矢量 数据结构形式。 点数据结构形式： 标志码唯一，属性码可有多个，属性也可放 于数据库中，通过标志码建立矢量数据和属 性数据的联系 标识码属性码X,y坐标对 简单矢量数据结构 线（弧、链）数据结构形式 标识码属性码坐标对数n坐标串(x,y) 面（多边形）数据结构形式 标识码属性码弧段数n弧段标识码集 简单矢量数据结构编码 由于简单数据结构中不考虑拓扑关

6、系，其 编码方法仅记录空间实体的位置、标志及 属性信息，而不记录拓扑关系。 编码方法有： 1 独立实体法 2 点位字典法 独立实体法Spaghetti方法 点实体：唯一标识码，实体编码，空间坐标(x,y) 线实体：唯一标识码，实体编码，空间坐 标(x1,y1,x2,y2,xn,yn) 面实体：唯一标识码，实体编码，空间坐 标(x1,y1,x2,y2,xn,yn,x1,y1) 一般cad系统都采用这种方法 多边形坐标位置 1x1,y1;x2,y2;x3,y3;x4,y4;x5,y5;x6,y6;x7,y7;x8,y8;x9,y9;x10,y10;x1,y1 2x28,y28; x29,y29;

7、x30,y30; x31,y31; x32,y32; x33,y33; x28,y28 3 x1,y1; x11,y11; x12,y12; x13,y13; x14,y14; x15,y15; x16,y16; x17,y17; x18,y18; x19,y19; x9,y9 x10,y10; x1,y1 4 x18,y18; x19,y19; x9,y9; x8,y8 ; x7,y7; x20,y20; x21,y21; x22,y22; x23,y23; x24,y24; x18,y18 5x16,y16; x17,y17; x18,y18; x24,y24; x23,y23; x27,

8、y27; x26,y26; x25,y25; x16,y16 独立实体法 优点：编码容易，数字化操作简单，数据 编码直观，显示速度快。 缺点：相邻多边形的公共边界数字化两次， 造成数据的冗余，可能出现重叠或裂缝， 引起数据不一致，缺少拓扑关系，空间分 析困难。 点位字典法 点位字典法中，点文件作为一个文件，点、线和 面实体都由点号组成， 点实体：唯一标识码，地物编码，点号 线实体：唯一标识码，地物编码，点号1 面实体：唯一标识码，地物编码，点号1 点位字典法 点号坐标 1X1,y1 2X2,y2 3X3,y3 1 2 3 4 5 6 7 8 9 AB C 目标序号 A1 B2，3，4，5 C6

9、，7，8，9 拓扑数据结构及编码 具有拓扑关系的矢量数据结构就是拓扑数 据结构，拓扑数据结构的表示方式没有固 定的格式，也没有形成标准，但基本原理 相同。 拓扑元素：点、线、面三种要素 基本拓扑关系：邻接、关联、包含 M N M N M N 点M与点N的邻接 线M与线N的邻接 面M与面N的邻接 邻接关系是相同拓扑元素之间的关系 M N p M N 面M、面N与线L的关联 L 线M、线N与点P的关联 关联是不同拓扑元素之间的关系 包含是面与其他拓扑元素之间的关 系，如果点、线、面在该面内，则 称为被该面包含 p1、p2、p3、p4、p5、p6和p7是节点；a,b,c,d,e,f,g,h,i和j为

10、弧段； A,B,C,D,E为多边形。 p1 p6 p2 p3 p4 p5 b h i j a g c p7 d e f A B C D E 为了表示出节点、弧段以及多边形之间的拓扑关系，可以使用如下几个关系表： 节点弧段 p1a,b,h P2a,d,f P3d,c,e P4e,g,f P5g,h,i P6b,i,c p7j 节点与弧段的拓扑关系 弧段节点(始节点，终节点) ap1,p2 bp1,p6 cp6,p3 dp3,p2 ep3,p4 fp2,p4 gp4,p5 hp5,p1 ip5,p6 jp7,p7 弧段与节点的拓扑关系 弧段多边形 左右 aAB b0A cDA dCA eDC fC

11、B gDB h0B iD0 jDE 弧段与多边形的拓扑关系 0代表制图区域外部的多边形 多边形弧段 Aa,b,c,d Ba,f,g,h C-d, e,-f D-c,-i,-g,-e,-j Ej 多边形与弧段的拓扑关系 1 有的关系表中D多边形中没有-j，“-”代表的 是逆时针方向的弧段； 2 有的关系表中D多边形中含有-j ，“-”表示面 域中含有岛。 拓扑数据结构编码 双重独立地图编码 链状双重独立式编码 双重独立地图编码 由两个主要表格组成： 节点表 节点号坐标 节点坐标 p1X1,y1 P2X2,y2 线段表 线段号起点终点左多边形右多边形 线段号起点终点左多边形 右多边形 ap1p2A

12、B bp1p60A 链状双重独立式编码 由四个或三个文件组成 节点文件：与双重独立地图编码类似 弧段坐标文件：标识码，弧段中间点 弧段文件：标识码，起始节点，终止节点， 左多边形，右多边形，内点 多边形文件：标识码，弧段号及面积、周 长及中心点坐标等 栅格数据结构 栅格结构栅格结构是以规则的像元阵列来表示空间 地物或现象的分布的数据结构，其阵列中 的每个数据表示地物或现象的属性特征。 换句话说，栅格数据结构就是像元阵列， 用每个像元的行列号确定位置，用每个像 元的值表示实体的类型、等级等的属性编 码 。 栅格数据结构 点实体点实体：表示为一个像元； 线实体线实体：表示为在一定方向上连接成串的

13、相邻像元的集合； 面实体面实体：表示为聚集在一起的相邻像元的 集合。 栅格数据结构的表示 1 简单数据结构的表示 把栅格数据看做一个数据矩阵，逐行记录 各像元代码。 2 其他数据结构的表示 栅格数据的压缩编码 1 链码 2 游程长度编码 3 块状编码 4 四叉树编码 链码 由某一起始点开始并按某些基本方向确定的单位矢量链。 前两个数字表示起点的行列号，第三个数字开始的每个 数字表示单位矢量的方向。 012 73 654 单位矢量方向 链码 优点：有很强的数据压缩能力，并具有一 定的运算功能，如面积、周长等的计算， 类似于矢量数据结构，比较适合于存储图 形数据。 缺点：叠置运算较难实施，对局部的

14、改动 会影响整体结构，而且相邻区域的边界重 复存储。 游程长度编码方法(1) 0,7,2,1,0,2 0,1,1,1,0,4,2,1,0,1,3,2 0,5,2,1,0,1,3,3 2 1 3 0 游程长度编码方法(2) 0,7,2,8,0,10 0,1,1,2,0,6,2,7,0,8,3,10 0,5,2,6,0,7,3,10 2 1 3 0 块状编码 44477777 04444777 44448877 00488877 00888878 00088000 00008000 00000000 44477777 04444777 44448877 00488877 00888878 0008

15、8000 00008000 00000000 块状编码 块状编码是将游程长度编码扩展到二维情 况，采用方形区域作为记录单元，数据结 构为：行号，列号，半径，单元代码，行 号，列号，半径，单元代码，。 1,1,1,4, 1,2,2,4 ,1,4,1,7, 1,5,1,7, 1,6,2,7, 1,8,1,7, 2,1,1,0, 2,4,1,4, 2,5,1,4, 2,8,1,7, 3,1,1,4, 3,2,1,4, 3,3,1,4, 3,4,1,4, 3,5,2,8, 3,7,2,7, 四叉树编码 Morton码 四叉树编码 再进行游程长度编码 游程长度编码方法 矢量数据的压缩方法矢量数据的压缩方

16、法 道格拉斯道格拉斯普克法普克法 垂距法垂距法 间隔取点法间隔取点法 光栏法光栏法 道格拉斯道格拉斯普克法普克法 道格拉斯道格拉斯普克法，又称分裂法。普克法，又称分裂法。 该算法实现的基本思路是：对每一条曲线的首末点虚连一该算法实现的基本思路是：对每一条曲线的首末点虚连一 条直线，求其它所有点与该直线的距离，并找出其中的最条直线，求其它所有点与该直线的距离，并找出其中的最 大距离值大距离值dmaxdmax，用，用dmaxdmax与限差与限差相比：相比： 若若dmaxdmax，这条曲线上的中间点全部舍去；，这条曲线上的中间点全部舍去； 若若dmaxdmax，保留，保留dmaxdmax对应的坐标点

17、，并以该点为界，对应的坐标点，并以该点为界， 把曲线分为两部分，对这两部分曲线重复上述操作，直至把曲线分为两部分，对这两部分曲线重复上述操作，直至 整条曲线处理结束。整条曲线处理结束。 表示被舍弃的结点偏离特征点连表示被舍弃的结点偏离特征点连 线之间的垂直距离，一般取值为线之间的垂直距离，一般取值为 0.2mm(若比例尺为若比例尺为1：10000，则，则 实际距离为实际距离为2m) 道格拉斯普克法示意图道格拉斯普克法示意图 垂距垂距( (限值限值) )法法 垂距法的基本思路是：每次顺序取曲线上的三个点，垂距法的基本思路是：每次顺序取曲线上的三个点， 计算中间点与其它两点连线的垂线距离计算中间点

18、与其它两点连线的垂线距离di，并与限差，并与限差比比 较。若较。若d di i，则中间点去掉；若，则中间点去掉；若di，则中间点保留。，则中间点保留。 然后顺序取下三个点继续处理，直到这条线结束。然后顺序取下三个点继续处理，直到这条线结束。 垂距法示意图垂距法示意图 间隔取点法间隔取点法 间隔取点法的基本思路是：每隔间隔取点法的基本思路是：每隔n n个点个点 取一点，或每隔一规定的距离取一点，但取一点，或每隔一规定的距离取一点，但 首末点一定要保留。例如对一曲线每隔一首末点一定要保留。例如对一曲线每隔一 个点（个点（n n=1=1）取一点进行压缩，其过程和结）取一点进行压缩，其过程和结 果如下

19、图所示。果如下图所示。 (1)(2)(3) 间隔取点压缩法示意图间隔取点压缩法示意图 从该压缩方式可看出，这种方法的优点是算法简单，可以从该压缩方式可看出，这种方法的优点是算法简单，可以 大量压缩数字化时用连续方法获取的点和通过栅格数据矢大量压缩数字化时用连续方法获取的点和通过栅格数据矢 量化得到的点，其缺点是不一定能恰当地保留方向上曲率量化得到的点，其缺点是不一定能恰当地保留方向上曲率 显著变化的点。显著变化的点。 光栏法光栏法 光栏法的基本思想：定义一个扇形区域，通过判断曲线上的点在扇形光栏法的基本思想：定义一个扇形区域，通过判断曲线上的点在扇形 外还是在扇形内，确定保留还是舍去。外还是在扇形内，确定保留还是舍去。 光栏边界点光栏边界点 扇