第一讲空间数据结构矢量数据结构.ppt

《第一讲空间数据结构矢量数据结构.ppt》由会员分享，可在线阅读，更多相关《第一讲空间数据结构矢量数据结构.ppt（18页珍藏版）》请在优知文库上搜索。

1、知识回顾知识回顾v空间对象的三种关系v如何理解拓扑关系v空间数据的拓扑关系有哪几种形式1空间数据结构空间数据结构主要内容主要内容1 矢量数据结构矢量数据结构 2 栅格数据结构栅格数据结构31 1 矢量数据结构矢量数据结构1.1 概念矢量 矢量也叫向量，数学上称“具有大小和方向的量”为向量。在计算机图形中，相邻两结点间的弧段长度表示大小，弧段两端点的顺序表示方向，因此弧段也是一个直观的矢量。 矢量数据结构是利用欧几里得几何学中的点、线、面及其组合体来表示地理实体空间分布的一种数据组织方式； 矢量数据结构按其是否明确表示地理实体间的空间关系分为实体数据结构实体数据结构和拓扑数据结拓扑数据结构构两大

2、类。5矢量数据结构实体数据结构0只记录空间对象的位置坐标和属性信息，不记录拓扑关系。0存储：q独立存储：空间对象位置直接跟随空间对象；q点位字典：点坐标独立存储，线、面由点号组成0特征l无拓扑关系，主要用于显示、输出及一般查询l公共边重复存储，存在数据冗余，难以保证数据独立性和一致性l多边形分解和合并不易进行，邻域处理较复杂；l处理嵌套多边形比较麻烦0适用范围：制图及一般查询，不适合复杂的空间分析矢量数据结构矢量数据结构点：位置：（点：位置：（x，y） 属性：符号属性：符号线：位置：线：位置： (x1,y1),(x2,y2),(xn,yn) 属性：符号属性：符号形状、颜色、尺寸形状、颜色、尺寸

3、思考练习：矢量数据编码思考练习：矢量数据编码12345678910111213141516171819202122232425262728293031多边形 数据项 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),(x2

4、5,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)（一）索引式结构（一）索引式结构 对所有点的坐标对所有点的坐标按顺序建坐标文件按顺序建坐标文件，再建点与边（线

5、）、，再建点与边（线）、线与多边形的线与多边形的索引文件索引文件, ,形成树状索引结构。形成树状索引结构。1234567891011 1213 1415P PP PP PMap1 1、点文件：、点文件：点号点号坐标坐标1x1,y1索引文件举例：索引文件举例：面号面号弧段号弧段号P1A,B,C3 3、面文件：、面文件：2 2、弧段文件、弧段文件: :弧段号弧段号起点起点终点终点点号点号A527,8,9,10与实体式相比：与实体式相比：v优点：用建索引的方法消除多边形数据的冗余和不一致，邻接信息、岛信息可在多边形文件中通过是否公共弧段号的方式查询。v缺点：表达拓扑关系较繁琐，给相邻运算、消除无用边

6、、处理岛信息、检索拓扑关系等带来困难，以人工方式建立编码表，工作量大，易出错。（二）双重独立编码结构（二）双重独立编码结构1 1、点文件、点文件点号点号坐标坐标1x1,y12 2、线文件、线文件: :线文件是以线文件是以线段线段为记录单位为记录单位 线号线号左多边形左多边形 右多边形右多边形 起点起点终点终点L210P1P22101234567891011 1213 1415P PP PP P3 3、面文件、面文件面号面号线号线号P1L210,L109关联关联邻接邻接关联关联连通连通拓扑关系明确拓扑关系明确在在DIMEDIME中做如下改进：中做如下改进： 将以将以线段线段为记录单位改为以为记录

7、单位改为以弧段弧段为单位为单位链状双重独立式编码链状双重独立式编码 又称双重独立地图编码又称双重独立地图编码DIME(Dual lndependent Map Encoding) DIME(Dual lndependent Map Encoding) 是美国人口调查系统所采用的编码方法。它通过是美国人口调查系统所采用的编码方法。它通过有向编码有向编码建立了多边建立了多边形、边界、节点之间的拓扑关系，形、边界、节点之间的拓扑关系，DIMEDIME是一种是一种拓扑拓扑编码结构，是编码结构，是其它其它拓扑编码结构的基础。拓扑编码结构的基础。ABCDOabcdefghijklmn12345678910

8、1112线号左多边形右多边形起点终点aOA18bOA21cOB32dOB43eOB54fOC65gOC76hOC87iCA89jCB95kCD1210lCD1112mCD1011nBA92这种数据结构除了通过线文件生成面文件外，还需要点文件 （二）双重独立式编码链状双重独立式编码是DIME编码的一种改进。在DIME中，一条边只能用直线两端点的序号及相邻的面域来表示，而在链状数据结构中，将若干直线段合为一个弧段（或链段），每个弧段可以有许多中间点。 在链状双重独立式编码中，主要有四个文件：多边形文件、弧段文件、弧段坐标文件、结点文件。（三）链状双重独立式编码-拓扑数据结构 注意：要彻底解决邻域和

9、岛状信息处理问题必须建注意：要彻底解决邻域和岛状信息处理问题必须建立一个完整的拓扑关系结构，这种结构应包括以下内容：立一个完整的拓扑关系结构，这种结构应包括以下内容：唯一标识唯一标识，多边形标识多边形标识，外包多边形指针外包多边形指针，邻接多边形邻接多边形指针指针，边界链接边界链接，范围范围（最大和最小（最大和最小x x、y y坐标值）。采坐标值）。采用拓扑结构编码可以较好地解决空间关系查询等问题，用拓扑结构编码可以较好地解决空间关系查询等问题，但增加了算法的复杂性和数据库的大小。矢量编码最重但增加了算法的复杂性和数据库的大小。矢量编码最重要的是信息的完整性和运算的灵活性，这是由矢量结构要的是

10、信息的完整性和运算的灵活性，这是由矢量结构自身的特点所决定的，目前并无统一的最好的结构编码自身的特点所决定的，目前并无统一的最好的结构编码方法，在具体工作中应根据数据的特点和任务的要求而方法，在具体工作中应根据数据的特点和任务的要求而灵活设计。灵活设计。1 1、弧段坐标文件：、弧段坐标文件：弧段号弧段号坐标系列（串坐标系列（串)Ax2,y2,X10,y102 2、弧段文件：链、弧段文件：链面，链面，链结点关系结点关系 弧段号弧段号 左多边形左多边形 右多边形右多边形 起点起点终点终点AP1P2251234567891011 1213 1415P PP PP P3 3、面文件、面文件: :面号面

11、号弧段号弧段号 P1A,B,-C4 4、点拓扑文件：、点拓扑文件： 结点结点链关系链关系 点号点号 弧段号弧段号 2A,B,D12345678910111213141516171819202122232425262728293031思考练习 如何利用拓扑数据如何利用拓扑数据结构的三种编码形结构的三种编码形式对空间实体进行式对空间实体进行编码？编码？弧段文件弧段号起始点终结点左多边形右多边形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示例：链状双重独立编码示例：链状双重独立编码