数据结构与拓扑数据结构的区别.doc

简单数据结构和拓扑数据结构

我们的世界五彩缤纷，人类的生活与这个环境密不可分，要利用和改造自然世界为人类的生存、生活创造有利的条件，必须将所有关注的局部世界加以简化和抽象，人类才能揭示出控制客观事物的演变过程的基本规律，而实现这一目标的普遍手段是采用模型的方法，利用一个模型来描述和表达这个世界，用空间数据结构去表示我们所要了解的客观事物。空间数据结构就是指空间数据的编排方式和组织关系，空间数据结构是空间数据在计算机中的具体组织方式。目前尚无一种统一的数据结构能够同时存储上述各种类型的数据，而是将不同类型的空间数据以不同的数据结构存储。一般来说，属性数据与其他信息系统一样常用二维关系表格形式存储。元数据以特定的空间元数据格式存储，而描述地理位置及其空间关系的空间特征数据是地理信息系统所特有的数据类型，主要以矢量数据结构和栅格数据结构两种形式存储。空间数据编码是空间数据结构的实现，目的是将不同的空间实体按一定的数据结构转换适用于计算机储存和处理的过程。不同的实体对象，其空间数据结构相差很大，即使是同一对象实体，也可以用许多种方式来组织数据，按不同数据结构去处理，得到的结果内容页是截然不同的。而计算机存储和处理数据的效率，在很大程度上是依赖于数据结构的组织方式的优劣。抽象是人们观察和分析复杂事物和现象的常用手段之一。将地理系统中复杂的地理现象进行抽象得到的地理对象称为地理实体或空间实体、空间目标，简称实体(Entity)。实体现实世界中客观存在的，并可相互区别的事物。实体可以指个体，也可以指总体，即个体的集合.抽象的程度与研究区域的大小、规模不同而有所不同，如在一张小比例尺的全国地图中，武汉市被抽象为一个点状实体，抽象程度很大；而在较大比例尺的武汉市地图上，需要将武汉市的街道、房屋详尽地表示出来，武汉市则被抽象为一个由简单点、线、面实体组成的庞大复杂组合实体，其抽象程度较前者而言较小。所以说，实体是一个具体有概括性、复杂性、相对意义的概念。
数据结构在GIS中对于数据的采集、存储、查询、检索和应用分析等操作方式有着重要的影响，一种高效率的数据结构应该具备以下几个要求：
1、组织的数据能够表示要素之间的层次关系，便于不同数据联系于覆盖；
2、正确反映地理实体之间的空间排列方式和各实体之间的相互关系；
3、便于存取与检索；
4、节省存储空间，减少数据冗余；
5、存取速度快，在运算速度较慢的微机上要达到快速响应；
6、具有足够的灵活性，数据组织应具有插入新的数据、删除或修改部分数据的基本功能。
栅格数据结构
栅格结构是以规则的阵列来表示空间地物或现象分布的数据组织,组织中的每个数据表示地物或现象的非几何属性特征。
栅格结构的显著特点:属性明显,定位隐含,即数据直接记录属性的指针或数据本身,而所在位置则根据行列号转换为相应的坐标。
栅格数据的编码方法:直接栅格编码,就是将栅格数据看作一个数据矩阵,逐行（或逐列）逐个记录代码;压缩编码,包括链码（弗里曼链码）比较适合存储图形数据;游程长度编码通过记录行或列上相邻若干属性相同点的代码来实现;块码是有成长度编码扩展到二维的情况,采用方形区域为记录单元;四叉树编码是最有效的栅格数据压缩编码方法之一,还能提高图形操作效率,具有可变的分辨率。

矢量数据结构
矢量数据结构是通过记录坐标的方式尽可能精确地表示点、线和多边形等地理实体,坐标空间设为连续,允许任意位置、长度和面积的精确定义。
矢量结构的显著特点:定位明显,属性隐含。
矢量数据的编码方法:
对于点实体和线实体,直接记录空间信息和属性信息;
对于多边形地物,有坐标序列法、树状索引编码法和拓扑结构编码法。坐标序列法是由多边形边界的x,y坐标对集合及说明信息组成,是最简单的一种多边形矢量编码法,文件结构简单,但多边形边界被存储两次产生数据冗余,而且缺少邻域信息;树状索引编码法是将所有边界点进行数字化,顺序存储坐标对,由点索引与边界线号相联系,以线索引与各多边形相联系,形成树状索引结构,消除了相邻多边形边界数据冗余问题;拓扑结构编码法是通过建立一个完整的拓扑关系结构,彻底解决邻域和岛状信息处理问题的方法,但增加了算法的复杂性和数据库的大小。

矢量栅格数据的比较
矢量数据的优缺点:
优点为数据结构紧凑、冗余度低,有利于网络和检索分析,图形显示质量好、精度高;
缺点为数据结构复杂,多边形叠加分析比较困难。
栅格数据的优缺点:
优点为数据结构简单,便于空间分析和地表模拟,现势性较强;
缺点为数据量大,投影转换比较复杂。
两者比较:
栅格数据操作总的来说容易实现,矢量数据操作则比较复杂;
栅格结构是矢量结构在某种程度上的一种近似,对于同一地物达到于矢量数据相同的精度需要更大量的数据;在坐标位置搜索、计算多边形形状面积等方面栅格结构更为有效,而且易于遥感相结合,易于信息共享;矢量结构对于拓扑关系的搜索则更为高效,网络信息只有用矢量才能完全描述,而且精度较高。对于地理信息系统软件来说,两者共存,各自发挥优势是十分有效的。
矢量栅格相互转换算法
矢量转栅格:内部点扩散法,即由多边形内部种子点向周围邻点扩散,直至到达各边界为止;复数积分算法,即由待判别点对多边形的封闭边界计算复数积分,来判断两者关系;射线算法和扫描算法,即由图外某点向待判点引射线,通过射线与多边形边界交点数来判断内外关系;边界代数算法,是一种基于积分思想的矢量转栅格算法,适合于记录拓扑关系的多边形矢量数据转换,方法是由多边形边界上某点开始,顺时针搜索边界线,上行时边界左侧具有相同行坐标的栅格减去某值,下行时边界左侧所有栅格点加上该值,边界搜索完毕之后即完成多边形的转换。
栅格转矢量:即是提取具有相同编号的栅格集合表示的多边形区域的边界和边界的拓扑关系,并表示成矢量格式边界线的过程。步骤包括:多边形边界提取,即使用高通滤波将栅格图像二值化;边界线追踪,即对每个弧段由一个节点向另一个节点搜索;拓扑关系生成和去处多余点及曲线圆滑。

拓扑的基本概念

几何信息和拓扑关系是地理信息系统中描述地理要素的空间位置和空间关系的不可缺少的基本信息。其中几何信息主要涉及几何目标的坐标位置、方向、角度、距离和面积等信息，它通常用解析几何的方法来分析。而空间关系信息主要涉及几何关系的“相连”、“相邻”、“包含”等信息，它通常用拓扑关系或拓扑结构的方法来分析。拓扑关系是明确定义空间关系的一种数学方法。在地理信息系统中用它来描述并确定空间的点、线、面之间关系及属性，并可实现相关的查询和检索。从拓扑观点出发，关心的是空间的点、线、面之间的联接关系，而不管实际图形的几何形状。因此，几何形状相差很大的图形，它们的拓扑结构却可能相同。
在矢量拓扑数据结构中，空间数据不但要记录空间实体的位置，而且要记录空间实体间的拓扑关系，这是地理信息系统区别于其他数据库管理系统的重要标志。建立拓扑关系是一种对空间结构关系进行明确定义的数学方法。目前，空间数据的拓扑数据结构的表示方式没有固定的格式，也没有形成标准，其基本原理是相同的。因此，在矢量拓扑结构表示方法中，任何地理实体均可以用点、线、面来表示其特征，并且可根据各实体间的空间拓扑关系，解译出更多的信息。
对于二维空间数据而言，矢量数据可以抽象点、线、面三种要素，也称拓扑要素。对三维而言，还要加上体。其最基本的拓扑关系主要有拓扑邻接、拓扑关联、拓扑包含等几种。拓扑数据结构中关键的就是对这些拓扑要素间的拓扑关系进行表示，几何数据的表示可参照矢量数据的简单数据。虽然目前GIS中基本的拓扑关系的表示方法不尽相同，但只要能完整表达出拓扑要素间的基本拓扑关系就可以。
拓扑数据结构：
拓扑数据结构包括DIME(对偶独立地图编码法)、POLYVRT(多边形转换器)、TIGER(地理编码和参照系统的拓扑集成)等。它们共同的特点是:点是相互独立的，点连成线，线构成面。每条线始于起始结点(FN)，止于终止结点TN)，并与左右多边形(LP和RP)相邻接。构成多边形的线叉称为链段或弧段，两条以上的弧段相交的点称为结点，由一条弧段组成的多边形称为岛，多边形图中不含岛的多边形称为简单多边形，表示单连通区域;含岛区的多边形称为复合多边形，表示复连通区域。在复连通区域中，包括有外边界和内边界，岛区多边形看作是复连通区域的内边界，复连通区域的内边界多边形对应的区域含有平面上的无穷远虑。该数据结构的基本元素如图2-11所示。
在这种数据结构中，弧段或链段是数据组织的基本对象。弧段文件由弧段记录组成，每个弧段记录包括弧段标识码、FN、TN、LP和RP。结点文件由结点记录组成，包括每个结点的结点号、结点坐标及与该结点连接的弧段标识码等。多边形文件由多边形记录组成，包括多边形标识码、组成该多边形的弧段标识码以及相关属性等。现以图2-11为例，列出拓扑数据结构的弧段文件格式(表2-5):

表2-5 拓扑数据结构的弧段文件构成

拓扑数据结构最重要的技术特征和贡献是具有拓扑编辑功能。这种拓扑编辑功能，不但保证数字化原始数据的自动查错编辑，而且可以自动形成封闭的多边形边界，为由各个单独存储的弧段组成所需要的各类多边形及建立空间数据库奠定基础。
拓扑编辑功能包括多边形连接编辑和结点连接编辑，前者指顺序连接组成封闭多边形一组线段的编辑，后者指顺序连接环绕某个结点所有多边形的编辑。具体的编辑算法如下:
　　(1)多边形连接编辑。例如，设需要对多边形P1进行编辑，其算法过程为:
　　①从表2-5所示的弧段文件中，检出与当前编辑的多边形P1相关的所有记录:

　　②在检出的记录中，计算机检查当前编辑的多边形P1所处的位置:
　　如果P1位在左多边形位置，将之与位于右多边形位置的多边形号相交换，同时也将该记录的结点号位置作相应的交换;反之，如果当前编辑的多边形P1位于右多边形位置，则该记录的所有数据项顺序不作改变。
　　按照上述规则，检出的记录变为以下形式:

　　③从经过代码位置转换的记录中，任取一个起结点作为起点，顺序连接各个结点，必要时可对记录的前后顺序作调整，使得连接的结点能自行封闭，如图2-12所示。

　　如果依照上述顺序连接的结点不能自行闭合，或者出现记录缺损或记录多余等情况，则表示弧段文件有错，必须改正出错的记录。直到所有多边形都经过编辑和改正，再转入结点连接编辑。
　　(2)结点连接编辑。例如，设需要对结点N2进行编辑，其算法过程为:
　　①从表2-5所示的弧段文件中，检出与当前编辑的结点N2相关的所有记录：

　　②在检出的记录中，计算机检查当前编辑的结点N2所处的位置:
　　如果N2位在起结点位置，将之与位于终结点位置的结点号相交换，同时也符该记录的多边形号位置作相应的交换;反之，如果当前编辑的结点N2位于终结点位置，则该记录所有数据项顺序不作改变。
　　按照上述规则，检出的记录变为以下形式:

　　③从经过代码位置转换的记录中，任取一个左多边形作为起点，顺序连接各个多边形，同样，必要时可对记录的前后顺序作调整，使得连接的多边形能首尾呼应，如图2-13所示。

　　如果依照上述序连接的多边形不能首尾呼应，或者出现记录缺损或记录多余等情况，同样也表示弧段文件有错，必须改正出错的记录。直到所有结点都经过编辑和改正，才能将该弧段文件用于结点文件和多边形文件的自动生成以及数据库的建立。
　　这种拓扑数据结构及其自动编辑功能，已经被许多商品化的GIS软件所采用，例如美国的ARC/INFO GIS软件等。
拓扑数据结构的结构特点：
1、空间关系明确，不依赖于具体的坐标位置。多边形的公共边界、网络的节点表达简明。
2、便于分析查询，尤其是点、线、面直线的相邻关系查询和分析。

拓扑数据结构的优缺点：
1、 图形的修改方便，可由软件检查数据输入错误，容易保证数据质量；
2、 便于叠合分析、网络分析等；
3、 数据结构复杂，软件复杂；
4、 建立拓扑关系需花计算时间，特别是当地图覆盖范围很大，数据量很大时。
拓扑数据结构的构建实际上大大增加了数据编辑的难度和复杂性，以至于它成了引起广泛争议的问题。显然，拓扑关系的存在为数据错误的查找和空间分析提供了必要的前提，但并不是所有的GIS应用丢必须具备这种预先存储的、消耗大量精力才能创建的数据结构。许多GIS软件只使用其中集中最基本的拓扑关系，就能满足大多数空间分析的需要，但更复杂的空间分析，也许需要更多的拓扑关系。一般的，建立的拓扑关系越多，数据编辑维护难度越大、越复杂，但进行处理比较复杂的空间分析就越方便，空间分析花费的时间就越少。因此，究竟是否应该预先存储拓扑关系、存储哪些拓扑关系就成为当前争论的焦点。
数据结构为我们人类利用模型来描述这个世界带来更方便的操作，也是目前我们利用最为广泛的方式，随着世界的发展，人类所需要研究的客观事物越来越多，也越来越复杂，因此描述这个世界的数据也将越来越多、越来越复杂。但是要想实现如此庞大的数据量以及数据的复杂性在运行速度比较缓慢的微机上流畅的被运行，被处理使用，对数据结构的要求也将会越来越高，只有进一步优化数据结构，才能使微机更好更快的处理数据来模拟我们的客观事物，才更有利于人类研究这个现实的世界。
6