第一讲空间数据结构矢量数据结构.ppt
知识回顾,空间对象的三种关系如何理解拓扑关系空间数据的拓扑关系有哪几种形式,1,地理信息系统,空间数据结构,主要内容,1 矢量数据结构,2 栅格数据结构,3,1 矢量数据结构,1.1 概念,矢量 矢量也叫向量，数学上称“具有大小和方向的量”为向量。在计算机图形中，相邻两结点间的弧段长度表示大小，弧段两端点的顺序表示方向，因此弧段也是一个直观的矢量。,矢量数据结构是利用欧几里得几何学中的点、线、面及其组合体来表示地理实体空间分布的一种数据组织方式；矢量数据结构按其是否明确表示地理实体间的空间关系分为实体数据结构和拓扑数据结构两大类。,5,矢量数据结构,实体数据结构,只记录空间对象的位置坐标和属性信息，不记录拓扑关系。存储：独立存储：空间对象位置直接跟随空间对象；点位字典：点坐标独立存储，线、面由点号组成特征无拓扑关系，主要用于显示、输出及一般查询公共边重复存储，存在数据冗余，难以保证数据独立性和一致性多边形分解和合并不易进行，邻域处理较复杂；处理嵌套多边形比较麻烦适用范围：制图及一般查询，不适合复杂的空间分析,矢量数据结构,点：位置：（x，y）属性：符号,线：位置：(x1,y1),(x2,y2),(xn,yn)属性：符号形状、颜色、尺寸,思考练习：矢量数据编码,多边形 数据项 A(x1,y1),(x2,y2),(x3,y3),(x4,y4),(x5,y5),(x6,y6),(x7,y7),(x8,y8),(x9,y9),(x1,y1)B(x1,y1),(x9,y9),(x8,y8),(x17,y17),(x16,y16),(x15,y15),(x14,y14),(x13,y13),(x12,y12),(x11,y11),(x10,y10),(x1,y1)C(x24,y24),(x25,y25),(x26,y26),(x27,y27),(x28,y28),(x29,y29),(x30,y30),(x31,y31),(x24,y24)D(x19,y19),(x20,y20),(x21,y21),(x22,y22),(x23,y23),(x15,y15),(x16,y16),(x19,y19)E(x5,y5),(x18,y18),(x19,y19),(x16,y16),(x17,y17),(x8,y8),(x7,y7),(x6,y6),(x5,y5),（一）索引式结构,对所有点的坐标按顺序建坐标文件，再建点与边（线）、线与多边形的索引文件,形成树状索引结构。,Map,1、点文件：,索引文件举例：,3、面文件：,2、弧段文件:,与实体式相比：优点：用建索引的方法消除多边形数据的冗余和不一致，邻接信息、岛信息可在多边形文件中通过是否公共弧段号的方式查询。缺点：表达拓扑关系较繁琐，给相邻运算、消除无用边、处理岛信息、检索拓扑关系等带来困难，以人工方式建立编码表，工作量大，易出错。,（二）双重独立编码结构,1、点文件,2、线文件:线文件是以线段为记录单位,3、面文件,关联,邻接,关联,连通,拓扑关系明确,在DIME中做如下改进：将以线段为记录单位改为以弧段为单位,链状双重独立式编码,又称双重独立地图编码DIME(Dual lndependent Map Encoding)是美国人口调查系统所采用的编码方法。它通过有向编码建立了多边形、边界、节点之间的拓扑关系，DIME是一种拓扑编码结构，是其它拓扑编码结构的基础。,这种数据结构除了通过线文件生成面文件外，还需要点文件,（二）双重独立式编码,链状双重独立式编码是DIME编码的一种改进。在DIME中，一条边只能用直线两端点的序号及相邻的面域来表示，而在链状数据结构中，将若干直线段合为一个弧段（或链段），每个弧段可以有许多中间点。在链状双重独立式编码中，主要有四个文件：多边形文件、弧段文件、弧段坐标文件、结点文件。,（三）链状双重独立式编码-拓扑数据结构,注意：要彻底解决邻域和岛状信息处理问题必须建立一个完整的拓扑关系结构，这种结构应包括以下内容：唯一标识，多边形标识，外包多边形指针，邻接多边形指针，边界链接，范围（最大和最小x、y坐标值）。采用拓扑结构编码可以较好地解决空间关系查询等问题，但增加了算法的复杂性和数据库的大小。矢量编码最重要的是信息的完整性和运算的灵活性，这是由矢量结构自身的特点所决定的，目前并无统一的最好的结构编码方法，在具体工作中应根据数据的特点和任务的要求而灵活设计。,1、弧段坐标文件：,2、弧段文件：链面，链结点关系,3、面文件:,4、点拓扑文件：结点链关系,思考练习,如何利用拓扑数据结构的三种编码形式对空间实体进行编码？,弧段文件弧段号起始点终结点左多边形右多边形a51OAb85EAc168EBd195OEe1519ODf1516DBg115OBh81ABi1619DEj3131BC弧段坐标文件弧段号点 号a5,4,3,2,1b8,7,6,5c16,17,8d19,18,5e15,23,22,21,20,19f15,16,g1,10,11,12,13,14,15h8,9,1i16,19j31,30,29,28,27,26,25,24,31,多边形文件多边形号 弧段号 周长 面积 中心点坐标 Ah,b,a Bg,f,c,h,-j Cj De,i,f Ee,i,d,b,示例：链状双重独立编码,
