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

1、2.3 空间数据结构的类型 2.3.1 空间数据结构的概念和类型空间数据结构的概念和类型 空间数据结构空间数据结构 也称为图形数据格式，是指适用于也称为图形数据格式，是指适用于 计算机系统存贮、管理和处理的地理图形数据的逻计算机系统存贮、管理和处理的地理图形数据的逻 辑结构，是地理实体的空间排列方式和相互关系的辑结构，是地理实体的空间排列方式和相互关系的 抽象描述抽象描述。换句话说，是指空间数据以什么形式在换句话说，是指空间数据以什么形式在 计算机中存储和管理。计算机中存储和管理。 在地理信息系统中，常用的空间数据结构有两种， 即矢量数据结构和栅格数据结构矢量数据结构和栅格数据结构。 常用的空

2、间数据结构常用的空间数据结构 X Y i j x1 y1 x2 y2 xi yi xn yn 同一条曲线的矢量矢量与栅格表示法栅格表示法 （1） 定义 基于矢量模型的数据结构简称为矢量数据 结构。 矢量也叫向量，数学上称“具有大小和方 向的量”为向量。 在计算机图形中，相邻两结点间的弧段长 度表示大小，弧段两端点的顺序表示方向， 因此弧段也是一个直观的矢量。 注意：由于坐标空间设为连续，所以允许任 意位置、长度和面积的精确定义。 但是，其精度仅受数字化设备的精度和数 值记录字长的限制，在一般情况下，比栅格 结构精度高得多 。 矢量数据模型 对于对于点实体（点实体（0维对象），没有长度和宽度维对

3、象），没有长度和宽度 只只记录其在特定坐标系下的坐标和属性记录其在特定坐标系下的坐标和属性 代码代码； 线实体（线实体（1维对象），只有长度没有宽度：维对象），只有长度没有宽度： 用一系列足够短的直线首尾相接表示一条用一系列足够短的直线首尾相接表示一条 曲线。曲线。 矢量结构中矢量结构中只记录这些小线段的端点坐标，只记录这些小线段的端点坐标， 将曲线表示为一个坐标序列，坐标之间认将曲线表示为一个坐标序列，坐标之间认 为是以直线段相连，为是以直线段相连，在一定精度范围内可在一定精度范围内可 以逼真地表示各种形状的线状地物以逼真地表示各种形状的线状地物 。 “多边形多边形”在地理信息系统中是在地理

4、信息系统中是指一个任指一个任 意形状、边界完全闭合的空间区域意形状、边界完全闭合的空间区域。 其边界将整个空间划分为两个部分：包含其边界将整个空间划分为两个部分：包含 无穷远点的部分称为外部，另一部分称为无穷远点的部分称为外部，另一部分称为 多边形内部多边形内部。 多边形的边界线同线实体一样，可以被看多边形的边界线同线实体一样，可以被看 作是由一系列多而短的直线段组成。作是由一系列多而短的直线段组成。 （2） 特点：定位明显，属性隐含定位明显，属性隐含。 （3） 获取方法： 手工数字化法； 手扶跟踪数字化法； 数据结构转换法。 矢量数据结构矢量数据结构 矢量数据结构分为以下几种矢量数据结构分为

5、以下几种主要类型主要类型 简单数据结构简单数据结构 拓扑数据结构拓扑数据结构 曲面数据结构曲面数据结构 1）简单数据结构）简单数据结构 a.面条（面条（Spaghetti方式）方式）在简单数据结构中，空间数据按在简单数据结构中，空间数据按 照以基本的空间对象（点、线、多边形）为单位进行单独照以基本的空间对象（点、线、多边形）为单位进行单独 组织，不含有拓扑关系数据，最典型的是面条（组织，不含有拓扑关系数据，最典型的是面条（Spaghetti 方式）方式） 由多边形边界的由多边形边界的x、y坐标对集合及说明信息组成，是坐标对集合及说明信息组成，是 最简单的一种多边形矢量编码，如上图记为以下坐标文

6、件：最简单的一种多边形矢量编码，如上图记为以下坐标文件： 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

7、,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每个多边形都以闭合线段存储，多边形之间的公

8、共每个多边形都以闭合线段存储，多边形之间的公共 边界被数字化和存储两次，造成数据冗余和不一致；边界被数字化和存储两次，造成数据冗余和不一致； 3点、线和多边形有各自的坐标数据，但没有拓扑数点、线和多边形有各自的坐标数据，但没有拓扑数 据，互相之间不关联。据，互相之间不关联。 4. 岛只作为一个单个的图形建造，没有与外包多边形岛只作为一个单个的图形建造，没有与外包多边形 的联系；的联系； 5不易检查拓扑错误。这种方法可用于简单的粗精度不易检查拓扑错误。这种方法可用于简单的粗精度 制图系统中制图系统中 2）拓扑数据结构）拓扑数据结构 拓扑型数据结构由拓扑型数据结构由弧段坐标文件、结点文弧段坐标文件

9、、结点文 件和多边形文件等一系列含拓扑关系的数件和多边形文件等一系列含拓扑关系的数 据文件组成据文件组成。 结点文件由结点记录组成，存贮每个结 点的结点号、结点坐标及与该结点连接 的弧段等 弧段坐标文件存贮组成弧段的点的坐标 弧段文件由弧记录组成，存贮弧段的起 止结点号和左右多边形号； 多边形文件由多边形记录组成，存贮多 边形号、组成多边形的弧段号以及多边 形的周长、面积、中心点坐标。 DIME(双重独立坐标地图编码，双重独立坐标地图编码，Dual Independent Map Encoding)编码系统编码系统 DIME是美国人口调查局在人口调查的 基础上发展起来的，它通过有向编码建立 了

10、多边形、边界、节点之间的拓扑关系， DIME编码成为其它拓扑编码结构的基础 拓扑整合的地理编码和参考系统（拓扑整合的地理编码和参考系统（TIGER) 多边形转换器（多边形转换器（POLYVRT） 特点： 点是相互独立的，点连成线，线构成 面。 每条线始于起始结点（FN），止于 终止结点（TN）并与左右多边形（LP和 RP）相邻接。 构成多边形的线又称为链段或弧段，两条 以上的弧段相交的点成为结点，由一条弧 段组成的多边形成为岛，多边形图中不含 岛的多边形称为简单多边形，表示单连通 区域；含岛区的多边形成为复合多边形， 表示复连通区域。 在这种数据结构中，弧段或链段是数据组 织的基本对象。 拓扑

11、数据结构最重要的技术特征和贡献是拓扑数据结构最重要的技术特征和贡献是 具有拓扑编辑功能。具有拓扑编辑功能。 拓扑编辑功能拓扑编辑功能包括包括多边形连接编辑多边形连接编辑和和结点结点 连接编辑连接编辑 a.多边形连接编辑多边形连接编辑 弧段号起点 终点左多边形右多边形 a2N2N40p4 a7N3N4p4p3 a8N2N3p4p2 弧段号起点 终点左多边形右多边形 a2N2N40p4 a7N4N3p3p4 a8N3N2p2p4 弧段号起点 终点左多边形右多边形 a2N2N40p4 a8N4N3p3p4 a7N3N2p2p4 N1 N3 N5 N2 N4 P2 P1 P4 P3 如果依照上述顺序连

12、接的结点不能自行闭 合，或者出现记录缺损或记录多余等情况， 则表示弧段文件有错，必须改正出错的记 录。直到所有多边形都经过编辑和改正， 再转入结点连接编辑。 b.结点连接编辑结点连接编辑 N1 N3 N5 N2 N4 P2 P1 P4 P3 弧段号起点终点左多边形右多边形 a8N2N3p4p2 a6N3N5p3p1 a7N3N4p4p3 a5N1N3p2p1 弧段号起点终点左多边形右多边形 a8N2N3p4p2 a6N5N3p1p3 a7N4N3p3p4 a5N1N3p2p1 弧段号起点终点左多边形右多边形 a5N1N3p2p1 a6N5N3p1p3 a7N4N3p3p4 a8N2N3p4p2

13、 如果依照上述顺序连接的多边形不能首尾 呼应，或者出现记录缺损或记录多余等情 况，同样也表示弧段文件有错，必须改正 出错的记录。直到结点都经过编辑和改正， 才能将该弧段文件和多边形文件的自动生 成以及数据库的建立。 3）曲面数据结构）曲面数据结构 曲面是指连续分布现象的覆盖表面，具有曲面是指连续分布现象的覆盖表面，具有 这种覆盖表面的要素有地形、降水量、温这种覆盖表面的要素有地形、降水量、温 度、磁场等。表示和存储这些要素的基本度、磁场等。表示和存储这些要素的基本 要求是必须便于连续现象在任一点的内插要求是必须便于连续现象在任一点的内插 计算，因此经常采用不规则三角网来拟合计算，因此经常采用不

14、规则三角网来拟合 连续分布现象的覆盖表面，称为连续分布现象的覆盖表面，称为TIN （Triangulated Irregular Network）数据）数据 结构结构 3 4 2 7 1 8 6 5 这种基于这种基于TIN的曲面数据结构，通常用于数的曲面数据结构，通常用于数 字地形的表示，或者按照曲面要素的实测字地形的表示，或者按照曲面要素的实测 点分布，将它们连成三角网，三角网中每点分布，将它们连成三角网，三角网中每 个三角形要求尽量接近等边形状，并保证个三角形要求尽量接近等边形状，并保证 由最邻近的点构成的三角形，即三角形的由最邻近的点构成的三角形，即三角形的 边长之和最小。边长之和最小。

15、在所有可能的三角网中，在所有可能的三角网中， 狄洛尼（狄洛尼（Delaunay）三角网在地形拟合方）三角网在地形拟合方 面表现最为出色。面表现最为出色。 狄洛尼（狄洛尼（Delaunay）三角网）三角网：为相互邻接：为相互邻接 且互相不重叠的三角形的集合，每一个三且互相不重叠的三角形的集合，每一个三 角形的外接圆内不含其他的点。角形的外接圆内不含其他的点。 狄洛尼三角形外接圆不包含其他点的特性狄洛尼三角形外接圆不包含其他点的特性 被用作从一系列不重合的平面点建立狄洛被用作从一系列不重合的平面点建立狄洛 尼三角网的基本法则，可以称为尼三角网的基本法则，可以称为狄洛尼法狄洛尼法 则则 狄洛尼三角网

16、的构建：狄洛尼三角网的构建： （三角网生长法）（三角网生长法） Delaunay三角网的特性 其Delaunay三角网是唯一的； 三角网的外边界构成了点集P的凸多边形 “外壳”； 没有任何点在三角形的外接圆内部，反之， 如果一个三角网满足此条件，那么它就是 Delaunay三角网； 如果将三角网中的每个三角形的最小角进行 升序排列，则Delaunay三角网的排列得到的数值 最大，从这个意义上说， Delaunay三角网是 “最接近于规则化”的三角网。（等边三角形） 3 4 2 7 1 8 6 5 三角 形的 标识 码 相邻三角形三角形顶点顶点坐标和特征值 1231st2st3st X1，y1，

17、z1X2，y2，z2X3，y3，z3 ABCD127 A B C D 泰森多边形（Thiessen Polygon） 弗若洛依图（弗若洛依图（Voronoi Diagram）在二维空间中）在二维空间中 也称泰森多边形（也称泰森多边形（Thiessen Polygon）。）。 区域D上有n个离散点Pi(Xi,Yi)(i=1,2,n),若将D 用一组直线段分成n个互相邻接的多边形,满足: 1)每个多边形内含且仅含一个离散点 2)D中任意一点P(X,Y)若位于Pi所在的多边形内, 则满足 由以上定义可知,泰森多边形泰森多边形的分法是唯一的;每 个泰森多边形泰森多边形均是凸多边形;任意两个泰森多边形泰

18、森多边形 不存在公共区域。 从左图中可以看出来，将泰森 多边形中各已知点(参考点)相 连形成的一个三角形网，该三 角形网是泰森多边形的对偶图， 它被称为狄洛尼三角网（D- TIN）。 用迪洛尼三角网构建泰森多边形用迪洛尼三角网构建泰森多边形 给定一个给定一个D-TIN，对于它的所有内边，连接共，对于它的所有内边，连接共 有每条内边的两个三角形的外接圆的圆心，即构有每条内边的两个三角形的外接圆的圆心，即构 成该成该TIN的平面点集的平面点集Voronoi图。图。 （1）首先构建离散平面点集的）首先构建离散平面点集的D-TIN； （2）然后求取各三角形的外接圆心；）然后求取各三角形的外接圆心； （

19、3）对每一个离散点，按顺时针或逆时针方）对每一个离散点，按顺时针或逆时针方 向连接与其关联的三角形的外接圆心，即得到该向连接与其关联的三角形的外接圆心，即得到该 离散点的泰森多边形；离散点的泰森多边形； （4）将各离散点的泰森多边形形成集合，即）将各离散点的泰森多边形形成集合，即 得到本平面点集的泰森多边形。得到本平面点集的泰森多边形。 矢量数据结构编码矢量数据结构编码 一、编码的概念和意义一、编码的概念和意义 地理数据编码，是根据GIS的目的和任务， 把地图、图像等资料按一定数据结构转换为适于 计算机存贮和处理的数据过程。地理内容的编码 要反映出地理实体的几何特征，以及地理实体的 属性特征，

20、空间数据的编码是地理信息系统设计 中最重要的技术步骤，它表现由现实世界到数据 世界之间的界面，是联结从现实世界到数据世界 的纽带。 二、矢量数据结构编码方法二、矢量数据结构编码方法 1）点实体矢量编码方法 2）线实体矢量编码方法 3）多边形矢量编码方法 1） 点实体编码点实体编码 比例 朝向 线指针 线交汇编 比例 朝向 字体 文句 x,y 坐标 其它非几何属性 建立和显示数据库联系的属性 简单点符号 文本点字符 结 点符号 统一标识 类别或系列号 点类型 简单点 文本点 结 点 2） 线实体编码线实体编码 唯一标示码唯一标示码 线标示码线标示码 起始点起始点 终止点终止点 坐标对序列坐标对序

21、列 显示信息显示信息 非几何属性非几何属性 唯一标识码是系统排列序号； 线标识码可以标识线的类型； 起始点和终止点号可直接用坐 标表示； 显示信息是显示时的文本或符 号等； 与线相联系的非几何属性可以 直接存储于线文件中，也可单 独存储，而由标识码联接查找 。 3） 多边形矢量编码多边形矢量编码 多边形环路（坐标序列法）法多边形环路（坐标序列法）法 树状（层次）索引编码法树状（层次）索引编码法 拓扑结构编码法拓扑结构编码法 由多边形边界的x,y 坐标队集合及说明 信息组成 对所有边界点数字化，将坐 标对以顺序方式存储，由点 索引与边界线号相联系，以 线索引与各多边形相联系 形成完整的 拓扑结构

22、 （1）多边形环路法）多边形环路法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 P1 P2 P3 P1 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，y6 P3 x12，y12；x13，y13；x14，y14；x15，y15 坐标序列法文件结构简单，易于实现以多边形为 单位的运算和显示。这种方法的缺点是： 多边形之间的公共边界被数字化和存储两次， 由此产生冗余和碎屑多边形； 每个多边形自成体系而缺少邻域信息，难以进 行邻域处理，如消除某两个

23、多边形之间的共同边 界； 岛只作为一个单个的图形建造，没有与外包多 边形的联系； 不易检查拓扑错误。这种方法可用于简单的粗 精度制图系统中。 多边形环路法的多边形环路法的优缺点优缺点 (2) 树状索引法树状索引法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 P1 P2 P3 P1P3 P2 1 2 3 4 5 6 5 6 5 6 7 8 9 1012 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 P1 P2 P3 点文件 点号 坐标 1 x1，y1 2 x2，y2 15 x15，y15 (2) 树状索引法树状索引法 1 2

24、 3 4 5 6 7 8 9 10 11 12 13 14 15 P1 P2 P3 1 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) 树状索引法树状索引法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 P1 P2 P3 多边形文件 多边形号 边界线号 1 ， 2 ， 3 P1P3 P2 (2) 树状索引法树状索引法 树状索引编码法的优势和不足树状索引编码法的优势和不足 树状索引编码消除了相邻多边形边界的数据 冗余和不一致的问题