地图数据结构1资料.ppt
地图数据结构,空间实体的分类,地图学中，把地理空间的实体分为点、线、面三种要素，分别用点状、线状、面状符号来表示。,点实体,有特定位置，维数为0的实体1 实体点：用来代表一个实体2 注记点：用来定位注记3 内点：用于记录多边形的属性，存在于多边形内4 节点：表示线的终点和起点5 拐点：表示线段和弧段的内部点,线实体,维数为1线段、线列、弧段、链、路径、多边线等特征：1 实体长度2 弯曲度3 方向性,面实体,面实体是维数为2的实体特征：1 周长2 面积3 独立或与其他地物的邻近性4 内岛或齿状外形5 重叠性与非重叠性,1、三条道路在不同的空间位置，称为定位信息,2、三条分别具有不同等级，称为属性信息,3、三条道路互相具有邻接关系。主干道与次干道在结点处相邻接，主干道的结点和相邻接，结点分别与三条路段、和相关联等，称为拓扑关系；C3在C6称的左边，称为方位关系；不同的道路之间有一定的距离，称为度量关系。,4、随着时间的推移，道路还将发生变化，称为时间特征。,地图数据的基本特征,空间特征属性特征时间特征,空间特征,1 空间位置空间位置用以描述事物或现象的地理位置，又称几何特征、定位特征。2 空间关系空间关系指地理空间实体之间存在的一些具有空间特性的关系，主要包含：拓扑关系方位关系度量关系,属性特征,属性特征用以描述事物或现象的特性，如事物或现象的类别、等级、数量、名称等。定性属性数据定量属性数据,时间特征,时间特征描述地理实体随着时间而变化的特征。,地图数据的基本类型,根据地图数据的特征，可以把地图数据分为空间数据、关系数据、属性数据。空间数据是描述地图要素中空间特征部分的数据，也叫几何数据。关系数据是描述空间数据之间的空间关系的数据。属性数据描述空间实体属性特征的数据。,空间数据,可分为点、线、面三种类型。点类型线类型面类型,关系数据,关系数据是描述空间数据之间的空间关系的数据，这儿说的是拓扑关系数据。最常见的空间实体关系有6种：点-点、点-线、点-面、线-线、线-面、面-面拓扑关系主要有邻接、关联、相交、相离、包含、重合等。,属性数据,描述空间实体属性特征的数据，描述地理现象或地理实体的定性或定量指标。,地图的数据结构,几何数据以什么形式在计算机中存储和处理。矢量数据结构栅格数据结构,矢量数据结构,矢量数据结构是表达地图空间数据的一种常见的数据结构，通过记录坐标值的方式尽可能精确的表示呈点、线或面状分布的地理实体。点：由一对x,y坐标表示线：由一串有序的x,y坐标对表示面：由一串有序的且首尾坐标相同的x,y坐标对表示。,矢量数据结构的表示,表示矢量数据的结构时，应考虑问题：1 矢量数据的存储和处理2 与属性数据的联系3 矢量数据之间的拓扑关系矢量数据结构表示一般有两类：1 简单矢量数据结构2 拓扑数据结构,简单矢量数据结构,简单矢量数据结构不考虑拓扑关系，可用于矢量数据的存储、处理、显示、输出及一般的查询检索。有点、线、面三种基本的矢量数据结构形式。点数据结构形式：标志码唯一，属性码可有多个，属性也可放于数据库中，通过标志码建立矢量数据和属性数据的联系,简单矢量数据结构,线（弧、链）数据结构形式,面（多边形）数据结构形式,简单矢量数据结构编码,由于简单数据结构中不考虑拓扑关系，其编码方法仅记录空间实体的位置、标志及属性信息，而不记录拓扑关系。编码方法有：1 独立实体法2 点位字典法,独立实体法Spaghetti方法,点实体：唯一标识码，实体编码，空间坐标(x,y)线实体：唯一标识码，实体编码，空间坐标(x1,y1,x2,y2,xn,yn)面实体：唯一标识码，实体编码，空间坐标(x1,y1,x2,y2,xn,yn,x1,y1)一般cad系统都采用这种方法,独立实体法,优点：编码容易，数字化操作简单，数据编码直观，显示速度快。缺点：相邻多边形的公共边界数字化两次，造成数据的冗余，可能出现重叠或裂缝，引起数据不一致，缺少拓扑关系，空间分析困难。,点位字典法,点位字典法中，点文件作为一个文件，点、线和面实体都由点号组成，点实体：唯一标识码，地物编码，点号线实体：唯一标识码，地物编码，点号1面实体：唯一标识码，地物编码，点号1,点位字典法,1,2,3,4,5,6,7,8,9,A,B,C,拓扑数据结构及编码,具有拓扑关系的矢量数据结构就是拓扑数据结构，拓扑数据结构的表示方式没有固定的格式，也没有形成标准，但基本原理相同。拓扑元素：点、线、面三种要素基本拓扑关系：邻接、关联、包含,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为弧段；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,为了表示出节点、弧段以及多边形之间的拓扑关系，可以使用如下几个关系表：,节点与弧段的拓扑关系,弧段与节点的拓扑关系,弧段与多边形的拓扑关系,0代表制图区域外部的多边形,多边形与弧段的拓扑关系,1 有的关系表中D多边形中没有-j，“-”代表的是逆时针方向的弧段；2 有的关系表中D多边形中含有-j，“-”表示面域中含有岛。,拓扑数据结构编码,双重独立地图编码链状双重独立式编码,双重独立地图编码,由两个主要表格组成：,节点表,线段表,链状双重独立式编码,由四个或三个文件组成节点文件：与双重独立地图编码类似弧段坐标文件：标识码，弧段中间点弧段文件：标识码，起始节点，终止节点，左多边形，右多边形，内点多边形文件：标识码，弧段号及面积、周长及中心点坐标等,栅格数据结构,栅格结构是以规则的像元阵列来表示空间地物或现象的分布的数据结构，其阵列中的每个数据表示地物或现象的属性特征。换句话说，栅格数据结构就是像元阵列，用每个像元的行列号确定位置，用每个像元的值表示实体的类型、等级等的属性编码。,栅格数据结构,点实体：表示为一个像元；线实体：表示为在一定方向上连接成串的相邻像元的集合；面实体：表示为聚集在一起的相邻像元的集合。,栅格数据结构的表示,1 简单数据结构的表示把栅格数据看做一个数据矩阵，逐行记录各像元代码。2 其他数据结构的表示,栅格数据的压缩编码,1 链码2 游程长度编码3 块状编码4 四叉树编码,链码,由某一起始点开始并按某些基本方向确定的单位矢量链。前两个数字表示起点的行列号，第三个数字开始的每个数字表示单位矢量的方向。,单位矢量方向,链码,优点：有很强的数据压缩能力，并具有一定的运算功能，如面积、周长等的计算，类似于矢量数据结构，比较适合于存储图形数据。缺点：叠置运算较难实施，对局部的改动会影响整体结构，而且相邻区域的边界重复存储。,游程长度编码方法(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,块状编码,块状编码,块状编码是将游程长度编码扩展到二维情况，采用方形区域作为记录单元，数据结构为：行号，列号，半径，单元代码，行号，列号，半径，单元代码，。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码四叉树编码再进行游程长度编码,游程长度编码方法,矢量数据的压缩方法,道格拉斯普克法,垂距法,间隔取点法,光栏法,道格拉斯普克法,道格拉斯普克法，又称分裂法。该算法实现的基本思路是：对每一条曲线的首末点虚连一条直线，求其它所有点与该直线的距离，并找出其中的最大距离值dmax，用dmax与限差相比：若dmax，这条曲线上的中间点全部舍去；若dmax，保留dmax对应的坐标点，并以该点为界，把曲线分为两部分，对这两部分曲线重复上述操作，直至整条曲线处理结束。,道格拉斯普克法示意图,垂距(限值)法,垂距法的基本思路是：每次顺序取曲线上的三个点，计算中间点与其它两点连线的垂线距离di，并与限差比较。若di，则中间点去掉；若di，则中间点保留。然后顺序取下三个点继续处理，直到这条线结束。,垂距法示意图,间隔取点法间隔取点法的基本思路是：每隔n个点取一点，或每隔一规定的距离取一点，但首末点一定要保留。例如对一曲线每隔一个点（n=1）取一点进行压缩，其过程和结果如下图所示。,从该压缩方式可看出，这种方法的优点是算法简单，可以大量压缩数字化时用连续方法获取的点和通过栅格数据矢量化得到的点，其缺点是不一定能恰当地保留方向上曲率显著变化的点。,光栏法,光栏法的基本思想：定义一个扇形区域，通过判断曲线上的点在扇形外还是在扇形内，确定保留还是舍去。,光栏边界点,扇边,新光栏口径,光栏法,光栏法的基本思想是：定义一个扇形区域，通过判断曲线上的点在扇形外还是在扇形内，确定保留还是舍去。设曲线上的点列为pi，i1，2，n，光栏口径为d，可根据压缩量的大小自己定义，则光栏法的实施步骤可描述为：1、连接p1和p2点，过p2点作一条垂直于p1p2的直线，在该垂线上取两点a1和a2，使a1p2a2p2d2，此时a1和a2为“光栏”边界点，p1与a1、p1与a2的连线为以p1为顶点的扇形的两条边，这就定义了一个扇形(这个扇形的口朝向曲线的前进方向，边长是任意的)。通过p1并在扇形内的所有直线都具有这种性质，即p1p2上各点到这些直线的垂距都不大于d/2。2、若p3点在扇形内，则舍去p2点。然后连接p1和p3，过p3作p1p3的垂线，该垂线与前面定义的扇形边交于c1和c2。在垂线上找到b1和b2点，使p3b1p3b2d2，若b1或b2点(图4-4-3中为b2点)落在原扇形外面，则用c1或c2取代(图4-4-3中由c2取代b2)。此时用p1b1和p1c2定义一个新的扇形，这当然是口径(b1c2)缩小了的“光栏”。3、检查下一节点，若该点在新扇形内，则重复第(2)步；直到发现有一个节点在最新定义的扇形外为止。4、当发现在扇形外的节点，如图中的p4，此时保留p3点，以p3作为新起点，重复13。如此继续下去，直到整个点列检测完为止。所有被保留的节点(含首、末点)，顺序地构成了简化后的新点列。,
