《数据结构与拓扑数据结构.doc》由会员分享，可在线阅读，更多相关《数据结构与拓扑数据结构.doc（6页珍藏版）》请在三一文库上搜索。
1、简单数据结构和拓扑数据结构我们的世界五彩缤纷，人类的生活与这个环境密不可分，要利用和改造自然世界为人类 的生存、生活创造有利的条件，必须将所有关注的局部世界加以简化和抽象，人类才能揭示 出控制客观事物的演变过程的基本规律，而实现这一目标的普颯手段是采用模型的方法，利 用一个模型来描述和表达这个世界，用空间数据结构去表示我们所要了解的客观事物。空间 数据结构就是指空间数据的编排方式和组织关系，空间数据结构是空间数据在计算机中的具 体组织方式。目前尚无一种统一的数据结构能够同时存储上述各种类型的数据，而是将不同 类型的空间数据以不同的数据结构存储。一般来说，属性数据与其他信息系统一样常用二维 关系
2、表格形式存储。元数据以特左的空间元数据格式存储，而描述地理位置及其空间关系的 空间特征数据是地理信息系统所特有的数据类型，主要以矢量数据结构和栅格数据结构两种 形式存储。空间数据编码是空间数据结构的实现，目的是将不同的空间实体按一左的数据结 构转换适用于讣算机储存和处理的过程。不同的实体对象，其空间数据结构相差很大，即使 是同一对象实体，也可以用许多种方式来组织数据，按不同数据结构去处理，得到的结果内 容页是截然不同的。而计算机存储和处理数据的效率，在很大程度上是依赖于数据结构的组 织方式的优劣。抽象是人们观察和分析复杂事物和现象的常用手段之一。将地理系统中复杂 的地理现象进行抽象得到的地理对
3、象称为地理实体或空间实体、空间目标，简称实体 （Entity）.实体现实世界中客观存在的，并可相互区别的事物。实体可以指个体，也可以指 总体，即个体的集合.抽象的程度与研究区域的大小、规模不同而有所不同，如在一张小比 例尺的全国地图中，武汉市被抽象为一个点状实体，抽象程度很大；而在较大比例尺的武汉 市地图上，需要将武汉市的街道、房屋详尽地表示出来，武汉市则被抽象为一个由简单点、 线、面实体组成的庞大复杂组合实体，英抽象程度较前者而言较小。所以说，实体是一个具 体有概括性、复杂性、相对意义的槪念。数据结构在GIS中对于数据的采集、存储、查询、检索和应用分析等操作方式有着重 要的影响，一种高效率的
4、数据结构应该具备以下几个要求：1、组织的数据能够表示要素之间的层次关系，便于不同数据联系于覆盖：2、正确反映地理实体之间的空间排列方式和务实体之间的相互关系：3、便于存取与检索；4、节省存储空间，减少数据冗余：5、存取速度快，在运算速度较慢的微机上要达到快速响应：6、具有足够的灵活性，数据组织应具有插入新的数据、删除或修改部分数拯的基本 功能。栅格数据结构栅格结构是以规则的阵列来表示空间地物或现象分布的数据组织,组织中的每个数据表 示地物或现象的非几何属性特征。栅格结构的显著特点:属性明显，左位隐含，即数据直接记录属性的指针或数据本身，而所在 位置则根据行列号转换为相应的坐标。栅格数据的编码方
5、法:直接栅格编码,就是将栅格数据看作一个数据矩阵，逐行（或逐列） 逐个记录代码;压缩编码，包括链码（弗里曼链码）比较适合存储图形数拯;游程长度编码通过 记录行或列上相邻若干属性相同点的代码来实现;块码是有成长度编码扩展到二维的情况，采 用方形区域为记录单元;四叉树编码是最有效的栅格数据压缩编码方法之一，还能提髙图形操 作效率，具有可变的分辨率。矢量数据结构矢量数据结构是通过记录坐标的方式尽可能精确地表示点、线和多边形等地理实体，坐标 空间设为连续，允许任意位置、长度和而积的精确定义。矢量结构的显箸特点:泄位明显，属性隐含。矢疑数据的编码方法：对于点实体和线实体，直接记录空间信息和属性信息；对于
6、多边形地物，有坐标序列法、树状索引编码法和拓扑结构编码法。坐标序列法是由多 边形边界的x,y坐标对集合及说明信息组成，是最简单的一种多边形矢量编码法，文件结构简 单，但多边形边界被存储两次产生数据冗余，而且缺少邻域信息;树状索引编码法是将所有边 界点进行数字化，顺序存储坐标对,由点索引与边界线号相联系，以线索引与各多边形相联系， 形成树状索引结构，消除了相邻多边形边界数据冗余问题;拓扑结构编码法是通过建立一个完 整的拓扑关系结构,彻底解决邻域和岛状信息处理问题的方法，但增加了算法的复杂性和数据 库的大小。矢量栅格数据的比较矢量数据的优缺点：优点为数据结构紧凑、冗余度低，有利于网络和检索分析，图
7、形显示质疑好、精度高； 缺点为数据结构复杂，多边形叠加分析比较困难。栅格数据的优缺点：优点为数据结构简单，便于空间分析和地表模拟，现势性较强；缺点为数据量大,投影转换比较复杂。两者比较：栅格数据操作总的来说容易实现,矢量数据操作则比较复杂；栅格结构是矢就结构在某种程度上的一种近似，对于同一地物达到于矢疑数拯相同的精度需 要更大疑的数据;在坐标位置搜索、计算多边形形状而积等方而栅格结构更为有效，而且易于 遥感相结合，易于信息共享;矢量结构对于拓扑关系的搜索则更为髙效，网络信息只有用矢量 才能完全描述，而且精度较髙。对于地理信息系统软件来说，两者共存，各自发挥优势是十分有 效的。矢量栅格相互转换算
8、法矢量转栅格:内部点扩散法，即由多边形内部种子点向周弗I邻点扩散，直至到达各边界为 止;复数积分算法，即由待判別点对多边形的封闭边界计算复数积分，来判断两者关系;射线算 法和扫描算法，即由图外某点向待判点引射线,通过射线与多边形边界交点数来判断内外关系; 边界代数算法，是一种基于积分思想的矢量转栅格算法，适合于记录拓扑关系的多边形矢量数 拯转换，方法是由多边形边界上某点开始，顺时针搜索边界线，上行时边界左侧具有相同行坐 标的栅格减去某值，下行时边界左侧所有栅格点加上该值,边界搜索完毕之后即完成多边形的 转换。柵格转矢量:即是提取具有相同编号的栅格集合表示的多边形区域的边界和边界的拓 扑关系，并
9、表示成矢量格式边界线的过程。步骤包括:多边形边界提取，即使用髙通滤波将栅格 图像二值化;边界线追踪,即对每个弧段由一个肖点向另一个肖点搜索;拓扑关系生成和去处 多余点及曲线圆滑。拓扑的基本概念几何信息和拓扑关系是地理信息系统中描述地理要素的空间位巻和空间关系的不可缺 少的基本信息。其中几何信息主要涉及几何目标的坐标位置、方向、角度、距离和而积等信 息，它通常用解析几何的方法来分析。而空间关系信息主要涉及几何关系的“相连”、“相邻”、 “包含”等信息，它通常用拓扑关系或拓扑结构的方法来分析。拓扑关系是明确左义空间关 系的一种数学方法。在地理信息系统中用它来描述并确立空间的点、线、而之间关系及属性
10、, 并可实现相关的查询和检索。从拓扑观点岀发，关心的是空间的点、线、面之间的联接关系, 而不管实际图形的几何形状。因此，几何形状相差很大的图形，它们的拓扑结构却可能相同。在矢屋拓扑数据结构中，空间数据不但要记录空间实体的位巻，而且要记录空间实体 间的拓扑关系，这是地理信息系统区别于其他数据库管理系统的重要标志。建立拓扑关系是 一种对空间结构关系进行明确定义的数学方法。目前，空间数据的拓扑数据结构的表示方式 没有固泄的格式，也没有形成标准，英基本原理是相同的。因此，在矢量拓扑结构表示方法 中，任何地理实体均可以用点、线、而来表示其特征，并且可根据各实体间的空间拓扑关系, 解译岀更多的信息。对于二
11、维空间数据而言，矢量数据可以抽象点、线、而三种要素，也称拓扑要素。对 三维而言，还要加上体。其最基本的拓扑关系主要有拓扑邻接、拓扑关联、拓扑包含等几种。 拓扑数据结构中关键的就是对这些拓扑要素间的拓扑关系进行表示，几何数据的表示可参照 矢量数据的简单数拯。虽然目前GIS中基本的拓扑关系的表示方法不尽相同，但只要能完 整表达出拓扑要素间的基本拓扑关系就可以。拓扑数据结构：拓扑数据结构包括DIME（对偶独立地图编码法）、POLYVRT（多边形转换器）、TIGER（地 理编码和参照系统的拓扑集成）等。它们共同的特点是:点是相互独立的，点连成线，线构成 而。每条线始于起始结点（FN）,止于终止结点TN
12、）,并与左右多边形（LP和RP）相邻接。构 成多边形的线叉称为链段或弧段，两条以上的弧段相交的点称为结点，由一条弧段组成的多 边形称为岛，多边形图中不含岛的多边形称为简单多边形，表示单连通区域;含岛区的多边 形称为复合多边形，表示复连通区域。在复连通区域中，包括有外边界和内边界，岛区多边 形看作是复连通区域的内边界，复连通区域的内边界多边形对应的区域含有平面上的无穷远 虑。该数据结构的基本元素如图2-11所示。在这种数据结构中，弧段或链段是数据组织的基本对象。弧段文件由弧段记录组成， 每个弧段记录包括弧段标识码、FN、TN、LP和RP。结点文件由结点记录组成，包括每个 结点的结点号、结点坐标及
13、与该结点连接的弧段标识码等。多边形文件由多边形记录组成, 包括多边形标识码、组成该多边形的弧段标识码以及相关属性等。现以图2-11为例，列出 拓扑数据结构的弧段文件格式（表2-5）:O结点弧段多边形一 一O岛结点码G弧段码P多边形图2-11 矢量结构图形基本元素表25拓扑数据结构的弧段文件构成弧段号起结点终结点左多边形右务边形5*P2P15叫P15Npl5Ni申P立5讯P25p3P立5%P45©P3CgP55n3%P4拓扑数据结构最重要的技术特征和贡献是具有拓扑编辑功能。这种拓扑编辑功能，不 但保证数字化原始数据的自动査错编辑，而且可以自动形成封闭的多边形边界，为由各个单 独存储的弧
14、段组成所需要的各类多边形及建立空间数据库奠泄基础。拓扑编辑功能包括多边形连接编辑和结点连接编辑，前者指顺序连接组成封闭多边形 一组线段的编借，后者指顺序连接环绕某个结点所有多边形的编辑。具体的编辑算法如下:(1)多边形连接编辑。例如，设需要对多边形P1进行编辑，其算法过程为： 从表2-5所示的弧段文件中，检出与当前编辑的多边形P1相关的所有记录：趣号起结点左零边形右爹边形C«N«严PC2N3PiP4CiNiNiPi如在检出的记录中，计算机检査当前编借的多边形P1所处的位置：如果P1位在左多边形位垃，将之与位于右多边形位置的多边形号相交换，同时 也将该记录的结点号位置作相应的
15、交换;反之，如果当前编辑的多边形P1位于右多边形位 置，则该记录的所有数据项顺序不作改变。按照上述规则，检出的记录变为以下形式：肠号左套边形右爹逍形GC2P4PlCmNiPl从经过代码位置转换的记录中，任取一个起结点作为起点，顺序连接各个结点, 必要时可对记录的前后顺序作调整，使得连接的结点能自行封闭.如图2J2所示。肠号笑结点左爹过形右寒边形G=W，*甩P'C2J N3P4PlCilit_J HlPl如果依照上述顺序连接的结点不能自行闭合，或者出现记录缺损或记录多余等情 况，则表示弧段文件有错，必须改正出错的记录。直到所有多边形都经过编辑和改正，再转 入结点连接编辑。(2)结点连接编
16、借。例如，设需要对结点N2进行编辑，其算法过程为：从表2-5所示的弧段文件中，检出与当前编辑的结点N2相关的所有记录： 觸号 起结点適点左零过形右参边形c«Nic?Pic$W$在检出的记录中，计算机检查当前编辑的结点N2所处的位置：如果N2位在起结点位宜，将之与位于终结点位置的结点号相交换，同时也符该 记录的多边形号位這作相应的交换;反之，如果当前编辑的结点N2位于终结点位宜，则该记 录所有数据项顺序不作改变。按照上述规则，检出的记录变为以下形式：磁号左零边形右多边形c«N«严PC2bhN?PiPiCsNsPhP2从经过代码位置转换的记录中，任取一个左多边形作为起
17、点，顺序连接各个多 边形，同样，必要时可对记录的前后顺序作调整，使得连接的多边形能首尾呼应，如图2-13 所示。如果依照上述序连接的多边形不能首尾呼应，或者出现记录缺损或记录多余等情 况，同样也表示弧段文件有错.必须改正出错的记录。直到所有结点都经过编辑和改正，才 能将该弧段文件用于结点文件和多边形文件的自动生成以及数据库的建立。这种拓扑数据结构及其自动编傅功能，已经被许多商品化的GIS软件所采用，例 如美国的ARC/INFO GIS软件等。拓扑数据结构的结构特点：1、空间关系明确，不依赖于具体的坐标位置。多边形的公共边界、网络的节点表达简明。2、便于分析查询，尤其是点、线、面直线的相邻关系查
18、询和分析。拓扑数据结构的优缺点：1、图形的修改方便，可由软件检查数据输入错误，容易保证数据质量：2、便于叠合分析、网络分析等：3、数据结构复杂，软件复杂：4、建立拓扑关系需花il算时间，特别是当地图覆盖范国很大，数据量很大时。拓扑数据结构的构建实际上大大增加了数据编借的难度和复杂性，以至于它成了引起 广泛争议的问题。显然，拓扑关系的存在为数据错误的查找和空间分析提供了必要的前提, 但并不是所有的GIS应用丢必须具备这种预先存储的、消耗大疑精力才能创建的数拯结构。 许多GIS软件只使用英中集中最基本的拓扑关系，就能满足大多数空间分析的需要，但更 复杂的空间分析，也许需要更多的拓扑关系。一般的，建
19、立的拓扑关系越多，数据编借维护 难度越大、越复杂，但进行处理比较复杂的空间分析就越方便，空间分析花费的时间就越少。 因此，究竟是否应该预先存储拓扑关系、存储哪些拓扑关系就成为当前争论的焦点。数据结构为我们人类利用模型来描述这个世界带来更方便的操作，也是目前我们利用最为广 泛的方式，随着世界的发展，人类所需要研究的客观事物越来越多，也越来越复杂，因此描 述这个世界的数据也将越来越多、越来越复杂。但是要想实现如此庞大的数据量以及数据的 复杂性在运行速度比较缓慢的微机上流畅的被运行，被处理使用，对数据结构的要求也将会 越来越髙，只有进一步优化数据结构，才能使微机更好更快的处理数据来模拟我们的客观事 物，才更有利于人类研究这个现实的世界。