第二章-2-空间数据结构的类型课件

2.3 空间数据结构的类型2.3.1空间数据结构的概念和类型空间数据结构的概念和类型空空间间数数据据结结构构也也称称为为图图形形数数据据格格式式，是是指指适适用用于于计计算算机机系系统统存存贮贮、管管理理和和处处理理的的地地理理图图形形数数据据的的逻逻辑辑结结构构，是是地地理理实实体体的的空空间间排排列列方方式式和和相相互互关关系系的的抽抽象象描描述述。换换句句话话说说，是是指指空空间间数数据据以以什什么么形形式式在计算机中存储和管理。在计算机中存储和管理。在地理信息系统中，常用的空间数据结构有两种，即矢量数据结构和栅格数据结构矢量数据结构和栅格数据结构。常用的空间数据结构常用的空间数据结构XYijx1 y1x2 y2xi yixn yn同一条曲线的矢量矢量与栅格表示法栅格表示法2.3.2矢量数据结构（1）定义基于矢量模型的数据结构简称为矢量数据结构。矢量也叫向量，数学上称“具有大小和方向的量”为向量。在计算机图形中，相邻两结点间的弧段长度表示大小，弧段两端点的顺序表示方向，因此弧段也是一个直观的矢量。2.3.2矢量数据结构 矢量数据结构是利用欧几里得几何学中的点、线、面及其组合体来表示地理实体空间分布的一种数据组织方式；即通过记录坐标的方式尽可能精确地表示点、线、多边形等地理实体.注意：由于坐标空间设为连续，所以允许任意位置、长度和面积的精确定义。但是，其精度仅受数字化设备的精度和数值记录字长的限制，在一般情况下，比栅格结构精度高得多。矢量数据模型对于对于点实体（点实体（0维对象），没有长度和宽度维对象），没有长度和宽度只只记录其在特定坐标系下的坐标和属性记录其在特定坐标系下的坐标和属性代码代码；线实体（线实体（1维对象），只有长度没有宽度：维对象），只有长度没有宽度：用一系列足够短的直线首尾相接表示一条用一系列足够短的直线首尾相接表示一条曲线。曲线。矢量结构中矢量结构中只记录这些小线段的端点坐标，只记录这些小线段的端点坐标，将曲线表示为一个坐标序列，坐标之间认将曲线表示为一个坐标序列，坐标之间认为是以直线段相连，为是以直线段相连，在一定精度范围内可在一定精度范围内可以逼真地表示各种形状的线状地物以逼真地表示各种形状的线状地物。“多边形多边形”在地理信息系统中是在地理信息系统中是指一个任指一个任意形状、边界完全闭合的空间区域意形状、边界完全闭合的空间区域。其边界将整个空间划分为两个部分：包含其边界将整个空间划分为两个部分：包含无穷远点的部分称为外部，另一部分称为无穷远点的部分称为外部，另一部分称为多边形内部多边形内部。多边形的边界线同线实体一样，可以被看多边形的边界线同线实体一样，可以被看作是由一系列多而短的直线段组成。作是由一系列多而短的直线段组成。（2）特点：定位明显，属性隐含定位明显，属性隐含。（3）获取方法：手工数字化法；手扶跟踪数字化法；数据结构转换法。2.3.2矢量数据结构矢量数据结构矢量数据结构分为以下几种矢量数据结构分为以下几种主要类型主要类型简单数据结构简单数据结构拓扑数据结构拓扑数据结构曲面数据结构曲面数据结构1）简单数据结构）简单数据结构a.面条（面条（Spaghetti方式）方式）在简单数据结构中，空间数据按在简单数据结构中，空间数据按照以基本的空间对象（点、线、多边形）为单位进行单独照以基本的空间对象（点、线、多边形）为单位进行单独组织，不含有拓扑关系数据，最典型的是面条（组织，不含有拓扑关系数据，最典型的是面条（Spaghetti方式）方式）由多边形边界的由多边形边界的x、y坐标对集合及说明信息组成，是最坐标对集合及说明信息组成，是最简单的一种多边形矢量编码，如上图记为以下坐标文件：简单的一种多边形矢量编码，如上图记为以下坐标文件：10：x1,y1；x2,y2；x3,y3；x4,y4；x5,y5；x6,y6；x7,y7；x8,y8；x9,y9；x10,y10；x11,y11；x1,y1；20：x1,y1；x12,y12；x13,y13；x14,y14；x15,y15；x16,y16；x17,y17；x18,y18；x19,y19；x20,y20；x21,y21；x22,y22；x23,y23；x8,y8；x9,y9；x10,y10；x11,y11；x1,y1；30：x33,y33；x34,y34；x35,y35；x36,y36；x37,y37；x38,y38；x39,y39；x40,y40；x33,y33；40：x19,y19；x20,y20；x21,y21；x28,y28；x29,y29；x30,y30；x31,y31；x32,y32；x19,y19；50：x21,y21；x22,y22；x23,y23；x8,y8；x7,y7；x6,y6；x24,y24；x25,y25；x26,y26；x27,y27；x28,y28；x21,y21；特点特点：1.数据按点、线或多边形为单元组织，数据编排直观，数据按点、线或多边形为单元组织，数据编排直观，数字化操作简单；数字化操作简单；2每个多边形都以闭合线段存储，多边形之间的公共每个多边形都以闭合线段存储，多边形之间的公共边界被数字化和存储两次，造成数据冗余和不一致；边界被数字化和存储两次，造成数据冗余和不一致；3点、线和多边形有各自的坐标数据，但没有拓扑数点、线和多边形有各自的坐标数据，但没有拓扑数据，互相之间不关联。据，互相之间不关联。4.岛只作为一个单个的图形建造，没有与外包多边形岛只作为一个单个的图形建造，没有与外包多边形的联系；的联系；5不易检查拓扑错误。这种方法可用于简单的粗精度不易检查拓扑错误。这种方法可用于简单的粗精度制图系统中制图系统中2）拓扑数据结构）拓扑数据结构拓扑型数据结构由拓扑型数据结构由弧段坐标文件、结点文弧段坐标文件、结点文件和多边形文件等一系列含拓扑关系的数件和多边形文件等一系列含拓扑关系的数据文件组成据文件组成。结点文件由结点记录组成，存贮每个结点的结点号、结点坐标及与该结点连接的弧段等弧段坐标文件存贮组成弧段的点的坐标弧段文件由弧记录组成，存贮弧段的起止结点号和左右多边形号；多边形文件由多边形记录组成，存贮多边形号、组成多边形的弧段号以及多边形的周长、面积、中心点坐标。DIME(双重独立坐标地图编码，双重独立坐标地图编码，DualIndependentMapEncoding)编码系统编码系统DIME是美国人口调查局在人口调查的基础上发展起来的，它通过有向编码建立了多边形、边界、节点之间的拓扑关系，DIME编码成为其它拓扑编码结构的基础拓扑整合的地理编码和参考系统（拓扑整合的地理编码和参考系统（TIGER)多边形转换器（多边形转换器（POLYVRT）特点：点是相互独立的，点连成线，线构成面。每条线始于起始结点（FN），止于终止结点（TN）并与左右多边形（LP和RP）相邻接。构成多边形的线又称为链段或弧段，两条以上的弧段相交的点成为结点，由一条弧段组成的多边形成为岛，多边形图中不含岛的多边形称为简单多边形，表示单连通区域；含岛区的多边形成为复合多边形，表示复连通区域。在这种数据结构中，弧段或链段是数据组织的基本对象。拓扑数据结构最重要的技术特征和贡献是拓扑数据结构最重要的技术特征和贡献是具有拓扑编辑功能。具有拓扑编辑功能。拓扑编辑功能拓扑编辑功能包括包括多边形连接编辑多边形连接编辑和和结点结点连接编辑连接编辑a.多边形连接编辑多边形连接编辑弧段号起点 终点左多边形右多边形a2N2N40p4a7N3N4p4p3a8N2N3p4p2弧段号起点 终点左多边形 右多边形a2N2N40p4a7N4N3p3p4a8N3N2p2p4弧段号起点 终点左多边形右多边形a2N2N40p4a8N4N3p3p4a7N3N2p2p4N1N3N5N2N4P2P1P4P3如果依照上述顺序连接的结点不能自行闭合，或者出现记录缺损或记录多余等情况，则表示弧段文件有错，必须改正出错的记录。直到所有多边形都经过编辑和改正，再转入结点连接编辑。b.结点连接编辑结点连接编辑N1N3N5N2N4P2P1P4P3弧段号起点终点左多边形右多边形a8N2N3p4p2a6N3N5p3p1a7N3N4p4p3a5N1N3p2p1弧段号起点终点左多边形右多边形a8N2N3p4p2a6N5N3p1p3a7N4N3p3p4a5N1N3p2p1弧段号起点终点左多边形右多边形a5N1N3p2p1a6N5N3p1p3a7N4N3p3p4a8N2N3p4p2如果依照上述顺序连接的多边形不能首尾呼应，或者出现记录缺损或记录多余等情况，同样也表示弧段文件有错，必须改正出错的记录。直到结点都经过编辑和改正，才能将该弧段文件和多边形文件的自动生成以及数据库的建立。3）曲面数据结构）曲面数据结构曲面是指连续分布现象的覆盖表面，具有曲面是指连续分布现象的覆盖表面，具有这种覆盖表面的要素有地形、降水量、温这种覆盖表面的要素有地形、降水量、温度、磁场等。表示和存储这些要素的基本度、磁场等。表示和存储这些要素的基本要求是必须便于连续现象在任一点的内插要求是必须便于连续现象在任一点的内插计算。通常有两种表达曲面的方法，一种计算。通常有两种表达曲面的方法，一种是不规则三角网（是不规则三角网（TriangulatedIrregularNetwork，TIN），另一种是规则格网），另一种是规则格网（Grid）。）。34271865（一）TIN的曲面数据结构这种基于这种基于TIN的曲面数据结构，通常用于数的曲面数据结构，通常用于数字地形的表示，或者按照曲面要素的实测字地形的表示，或者按照曲面要素的实测点分布，将它们连成三角网，三角网中每点分布，将它们连成三角网，三角网中每个三角形要求尽量接近等边形状，并保证个三角形要求尽量接近等边形状，并保证由最邻近的点构成的三角形，即三角形的由最邻近的点构成的三角形，即三角形的边长之和最小。边长之和最小。在所有可能的三角网中，在所有可能的三角网中，狄洛尼（狄洛尼（Delaunay）三角网在地形拟合方）三角网在地形拟合方面表现最为出色。面表现最为出色。狄洛尼（狄洛尼（Delaunay）三角网）三角网：为相互邻接：为相互邻接且互相不重叠的三角形的集合，每一个三且互相不重叠的三角形的集合，每一个三角形的外接圆内不含其他的点。角形的外接圆内不含其他的点。狄洛尼三角形外接圆不包含其他点的特性狄洛尼三角形外接圆不包含其他点的特性被用作从一系列不重合的平面点建立狄洛被用作从一系列不重合的平面点建立狄洛尼三角网的基本法则，可以称为尼三角网的基本法则，可以称为狄洛尼法狄洛尼法则则狄狄洛洛尼尼三三角角网网的的构构建建：（三三角角网网生生长长法法）Delaunay三角网的特性其Delaunay三角网是唯一的；三角网的外边界构成了点集P的凸多边形“外壳”；没有任何点在三角形的外接圆内部，反之，如果一个三角网满足此条件，那么它就是Delaunay三角网；如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大，从这个意义上说，Delaunay三角网是“最接近于规则化”的三角网。（等边三角形）34271865三角形的标识码相邻三角形三角形顶点顶点坐标和特征值1231st2st3stX1，y1，z1X2，y2，z2X3，y3，z3ABCD127ABCDTIN模型的表现模型的表现（二）泰森多边形（ThiessenPolygon）弗若洛依图（弗若洛依图（VoronoiDiagram）在二维空间中）在二维空间中也称泰森多边形（也称泰森多边形（ThiessenPolygon）。）。区域D上有n个离散点Pi(Xi,Yi)(i=1,2,n),若将D用一组直线段分成n个互相邻接的多边形,满足:1)每个多边形内含且仅含一个离散点2)D中任意一点P(X,Y)若位于Pi所在的多边形内,则满足由以上定义可知,泰森多边形泰森多边形的分法是唯一的;每个泰森多边形泰森多边形均是凸多边形;任意两个泰森多边形泰森多边形不存在公共区域。从左图中可以看出来，将泰森多边形中各已知点(参考点)相连形成的一个三角形网，该三角形网是泰森多边形的对偶图，它被称为狄洛尼三角网（D-TIN）。用狄洛尼三角网构建泰森多边形用狄洛尼三角网构建泰森多边形给定一个给定一个D-TIN，对于它的所有内边，连接共，对于它的所有内边，连接共有每条内边的两个三角形的外接圆的圆心，即构有每条内边的两个三角形的外接圆的圆心，即构成该成该TIN的平面点集的平面点集Voronoi图。图。（1）首先构建离散平面点集的）首先构建离散平面点集的D-TIN；（2）然后求取各三角形的外接圆心；）然后求取各三角形的外接圆心；（3）对每一个离散点，按顺时针或逆时针方）对每一个离散点，按顺时针或逆时针方向连接与其关联的三角形的外接圆心，即得到该向连接与其关联的三角形的外接圆心，即得到该离散点的泰森多边形；离散点的泰森多边形；（4）将各离散点的泰森多边形形成集合，即）将各离散点的泰森多边形形成集合，即得到本平面点集的泰森多边形。得到本平面点集的泰森多边形。（三）规则格网的曲面数据结构规则格网的曲面数据结构类似于矩阵形式的栅格数据，只是其属性值为地面的高程或其他连续分布的数值。2.3.3矢量数据结构编码矢量数据结构编码一、编码的概念和意义一、编码的概念和意义 地理数据编码，是根据GIS的目的和任务，把地图、图像等资料按一定数据结构转换为适于计算机存贮和处理的数据过程。地理内容的编码要反映出地理实体的几何特征，以及地理实体的属性特征，空间数据的编码是地理信息系统设计中最重要的技术步骤，它表现由现实世界到数据世界之间的界面，是联结从现实世界到数据世界的纽带。二、矢量数据结构编码方法二、矢量数据结构编码方法1）点实体矢量编码方法2）线实体矢量编码方法3）多边形矢量编码方法1）点实体编码点实体编码比例朝向线指针线交汇编比例朝向字体文句x,y 坐标其它非几何属性建立和显示数据库联系的属性简单点符号文本点字符结 点符号统一标识类别或系列号点类型简单点文本点结 点二、矢量数据编码方法二、矢量数据编码方法二、矢量数据编码方法二、矢量数据编码方法2）线实体编码线实体编码唯一标示码唯一标示码线标示码线标示码起始点起始点终止点终止点坐标对序列坐标对序列显示信息显示信息非几何属性非几何属性唯一标识码是系统排列序号；线标识码可以标识线的类型；起始点和终止点号可直接用坐标表示；显示信息是显示时的文本或符号等；与线相联系的非几何属性可以直接存储于线文件中，也可单独存储，而由标识码联接查找。3）多边形矢量编码多边形矢量编码多边形环路（坐标序列法）法多边形环路（坐标序列法）法树状（层次）索引编码法树状（层次）索引编码法拓扑结构编码法拓扑结构编码法由多边形边界的x,y坐标队集合及说明信息组成对所有边界点数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系形成完整的拓扑结构（1）多边形环路法）多边形环路法123456789101112131415P1P2P3P1 x1，y1；x2，y2；x3，y3；x4，y4；x5，y5；x6，y6；P2 x7，y7；x8，y8；x9，y9；x10，y10；x11，y11；x5，y5；x6，y6P3 x12，y12；x13，y13；x14，y14；x15，y15坐标序列法文件结构简单，易于实现以多边形为单位的运算和显示。这种方法的缺点是：多边形之间的公共边界被数字化和存储两次，由此产生冗余和碎屑多边形；每个多边形自成体系而缺少邻域信息，难以进行邻域处理，如消除某两个多边形之间的共同边界；岛只作为一个单个的图形建造，没有与外包多边形的联系；不易检查拓扑错误。这种方法可用于简单的粗精度制图系统中。多边形环路法的多边形环路法的优缺点优缺点(2)树状索引法树状索引法123456789101112131415P1P2P3 P1P3P2 1 2 3 4 5 6 5 6 5 6 7 8 9 1012 13 14 15 123456789101112131415P1P2P3点文件 点号 坐标 1 x1，y1 2 x2，y2 15 x15，y15(2)树状索引法树状索引法123456789101112131415P1P2P31 2 3 4 5 6 5 6 5 6 7 8 9 1012 13 14 15 线文件线号 起点 终点 点号 6 5 6,1,2,3,4,5 5 6 5,6 6 5 6,7,8,9,10,11,5 12 13 12,15,14,13(2)树状索引法树状索引法123456789101112131415P1P2P3多边形文件多边形号 边界线号 1 ，2 ，3 P1P3P2 (2)树状索引法树状索引法树状索引编码法的优势和不足树状索引编码法的优势和不足树状索引编码消除了相邻多边形边界的数据冗余和不一致的问题，在简化过于复杂的边界线或合并相邻多边形时可不必改造索引表，邻域信息和岛状信息可以通过对多边形文件的线索引处理得到，但是比较繁琐，因而给相邻函数运算，消除无用边，处理岛状信息以及检查拓扑关系带来一定的困难，而且两个编码表都需要以人工方式建立，工作量大且容易出错。(3)拓扑结构编码法拓扑结构编码法唯一标识唯一标识多边形标识多边形标识外包多边形指针外包多边形指针邻接多边形指针邻接多边形指针边界链接边界链接范围范围较好的解决了空间关系查询等问题，但增加了算法的复杂度拓扑结构的表达拓扑结构的表达1256473P1P3P2P4N4N3N5N2N1结 点弧 段N1N3N21361253241 1、结点与弧段的拓扑关系、结点与弧段的拓扑关系P01256473P1P3P2P4N4N3N5N2N1弧段结 点始结点终结点123N2N3N1N1 N2N32、弧段与结点的拓扑关系、弧段与结点的拓扑关系P01256473P1P3P2P4N4N3N5N2N1弧段多 边 形左多边形多边形右多边形多边形123P1 P2P33、弧段与多边形的拓扑关系、弧段与多边形的拓扑关系P0P0P0P01256473P1P3P2P4N4N3N5N2多边形多边形弧 段1564253644 4、多边形多边形与弧段的拓扑关系与弧段的拓扑关系P0P1 P2P37N1矢量数据结构编码总结矢量数据结构编码总结矢量编码保证了信息的完整性和运算的灵活性，这是由矢量结构自身的特点所决定的。目前并没有统一的最佳的矢量结构编码方法，在具体工作中应根据数据的特点和任务的要求而灵活设计。