《简单数据结构和拓扑数据结构》由会员分享，可在线阅读，更多相关《简单数据结构和拓扑数据结构（22页珍藏版）》请在金锄头文库上搜索。
1、简单数据结构和拓扑数据结构【09级测绘工程】 梁艳【引言】空间数据结构是指对空间数据逻辑模型描述的数据组织关系和编排方式，对地 理信息系统中数据存储、查询检索和应用分析等操作处理的效率有着至关重要的影 响。空间数据结构是地理信息系统沟通信息的桥梁，只有充分理解地理信息系统所 采用的特定数据结构，才能正确有效地使用系统。在地理信息系统中，较常用的有 栅格数据结构和矢量数据结构，除此之外还有混合数据结构、镶嵌数据结构和超图 数据结构等。空间数据结构的选择取决于数据的类型、性质和使用的方式，应根据 不同的任务目标，选择最有效和最合适的数据结构。矢量数据结构对矢量数据模型进行数据的组织。它通过记录实体
2、坐标及其关系，尽可能精确地表示点、线、多边形等地理实体，坐标空间设为连续，允许任意 位置、长度和面积的精确定义。矢量数据结构直接以几何空间坐标为基础，记录取 样点坐标。按照这种数据组织方式，可以得到精美的地图。另外，该结构还可以对 复杂数据以最小的数据冗余进行存贮，它还具有数据精度高，存储空间小等特点， 是一种高效的图形数据结构。矢量数据结构中，传统的方法是几何图形及其关系用 文件方式组织，而属性数据通常采用关系型表文件记录，两者通过实体标识符连接。由于这一特点使得在某些方面有便利和独到之处，例如在计算长度、面积、形状和图形编辑、几何变换操作中，有很高的效率和精度。矢量数据结构按其是否明确表示
3、地理实体间的空间关系分为简单数据结构和拓 扑数据结构两大类。矢量数据结构是利用欧几里得几何学中的点、线、面及其组合体来表示地理实 体空间分布的一种数据组织方式。矢量数据结构分为无拓扑的矢量数据结构（也称 简单数据结构）、拓扑数据结构；拓扑数据结构最重要的技术特征和贡献是具有拓 扑编辑功能，包括多边形连接编辑和结点连接编辑。无拓扑的矢量数据结构仅记录 空间对象的位置坐标和属性信息，而不记录其拓扑关系。它有两种模式它有两种 模式：一种方式是用点一种方式是用点、线线、面对象面对象分别记录其坐标对； 另一种方式是用一个文件记录点坐标对，而线、面由点号组成。空间拓扑关系是 GIS的重要标志。目前大部分G
4、IS软件所存储的拓扑关系仅仅涉及空间对象的拓扑 关联关系，其它拓扑关系（如拓扑邻接、拓扑包含 拓扑包含、可以从关联关系中 导出，或通过实时空间运算得到。【关键字】数据结构、拓扑、空间实体空间数据结构是指适合于计算机存贮、管理、处理的几何数据的逻 辑结构。换句话说，是指几何数据以什么形式在计算机中存贮和处理。空间数据结构分为矢量数据结构和栅格数据结构两种（如图2-4 ）图2-4空间实体的栅格、矢量数据结构表示一、矢量数据结构矢量数据结构是通过坐标值来精确地表示点、线、面等地理实体 的方法。点由一对x,y坐标表示。线由一串有序的x,y坐标对表示。面由一串有序的、且首尾坐标相同的x,y坐标对表示。矢
5、量数据结构可以表示现实世界中各种复杂的实体，当问题可描述 成线和边界时，特别有效。矢量数据冗余度低，结构紧凑，并具有空间 实体的拓扑信息，便于深层次分析。矢量数据的输出质量好、精度高。矢量数据的获取方式通常有：(1) 由外业测量获得。可利用测量仪器自动记录测量成果(常称为电子手薄)，然后转到地理数据库中。(2) 由栅格数据转换获得。利用栅格数据矢量化技术，把栅格数据转 换为矢量数据。(3) 跟踪数字化。用跟踪数字化的方法，把地图变成离散的矢量数据。 矢量数据结构的表示：矢量数据的表示方法多种多样，但基本上类似，可触类旁通。在GIS中，矢量数据表示时应考虑以下问题：矢量数据自身的存贮和处理。与属
6、性数据的联系。矢量数据之间的空间关系(拓扑关系)。下面分别介绍矢量数据的简单数据结构和拓扑数据结构。(1) 简单数据结构矢量数据的简单数据结构没有拓扑关系，主要用于矢量数据的显 示、输出，以及一般的查询和检索。可分别按点、线、面三种基本形式 来描述。1、点的矢量数据结构可表示为：标识码X, Y坐标标识码：按一定的原则编码，简单情况下可顺序编号。标识码 具有唯一性，是联系矢量数据和与其对应的属性数据的关键字。属 性数据单独存放在数据库中。在点的矢量数据结构中也可包含属性 码，这时其数据结构为：标识码属性码X, Y坐标属性码：通常把与实体有关的基本属性（如等级、类型、大小等）作 为属性码。属性码可
7、以有一个和多个。X,Y坐标：是点实体的定位点，如果是有向点，则可以有两个坐 标对。2、线（链）的矢量数据结构 线（链）的矢量数据结构可表示为：标识码坐标对数nX, Y坐标标识码的含义与点的矢量数据结构相同。同样，在线的矢量数 据结构中也可含有属性码，如表示线的类型、等级、是否要加密、 兀滑等等o坐标对数n :构成该线（链）的坐标对的个数。X,Y坐标串：这是构成线（链）的矢量坐标，共有n对。也可把所有 线（链）的X,Y坐标串单独存放 这时只要给出指向该链 坐标串的首地址指针即可。3、面（多边形）面的矢量数据结构可以象线的数据结构一样表示，只是坐标串的 首尾坐标相同。这里介绍链索引编码的面（多边形
8、）的矢量数据结构， 可表示为：标识码琏数n谁标识码集标识码的含义同点和线的矢量数据结构，在面的矢量数据结构 中也可含有属性码。链数n :指构成该面（多边形）的链的数目。链标识码集：指所有构成该面（多边形）的链的标识码的集合，共有 n个。这样，一个面（多边形）就可由多条链构成，每条链的坐标可由线 （链）的矢量数据结构获取。这种方法可保证多边形公共边的唯一性； 但多边形的分解和合并不易进行；邻域处理比较复杂，需追踪出公 共边；在处理“洞”或“岛”之类的多边形嵌套问题时较麻烦，需计算多 边形的包含等。（2 ）拓扑数据结构拓扑关系是一种对空间结构关系进行明确定义的数学方法。具有 拓扑关系的矢量数据结构
9、就是拓扑数据结构，拓扑数据结构是GIS的 分析和应用功能所必需的。拓扑数据结构的表示方式没有固定的格式， 还没有形成标准，但基本原理是相同的。1、拓扑元素矢量数据可抽象为点（结点）、线（链、弧段、边）、面（多边形） 三种要素，即称为拓扑元素。点（结点）孤立点、线的端点、面的首尾点、链的连接点等。线（链、弧段、边）两结点间的有序弧段。面（多边形）一一若干条链构成的闭合多边形。2、最基本的拓扑关系最基本的拓扑关系是关联和邻接。关联一一不同拓扑元素之间的关系。如结点与链，链与多边形等。邻接相同拓扑元素之间的关系。如结点与结点，链与链，面与 面等。邻接关系是借助于不同类型的拓扑元素描述的，如 面通过链
10、而邻接。在GIS的分析和应用功能中，还可能用到其它拓扑关系，如：包含关系一一面与其它拓扑元素之间的关系。如果点、线、面在该 面内，则称为被该面包含。如某省包含的湖泊、河流等。几何关系一一拓扑元素之间的距离关系。如拓扑元素之间距离不超 过某一半径的关系。层次关系相同拓扑元素之间的等级关系。如国家由省（自治区、直辖市）组成，省（自治区、直辖市）由县组成等。3、拓扑关系的表示拓扑数据结构包括DIME（对偶独立地图编码法）、POLYVRT（多边 形转换器）、TIGER（地理编码和参照系统的拓扑集成）等。它们共同的 特点是:点是相互独立的，点连成线，线构成面。每条线始于起始结点 （FN），止于终止结点T
11、N），并与左右多边形（LP和RP）相邻接。构成 多边形的线叉称为链段或弧段，两条以上的弧段相交的点称为结点， 由一条弧段组成的多边形称为岛，多边形图中不含岛的多边形称为简 单多边形，表示单连通区域;含岛区的多边形称为复合多边形，表示复 连通区域。在复连通区域中，包括有外边界和内边界，岛区多边形看 作是复连通区域的内边界，复连通区域的内边界多边形对应的区域含 有平面上的无穷远虑。该数据结构的基本元素如图2-11所示。在这种数据结构中，弧段或链段是数据组织的基本对象。弧段文 件由弧段记录组成，每个弧段记录包括弧段标识码、FN、TN、LP和 RP。结点文件由结点记录组成，包括每个结点的结点号、结点坐
12、标及与该结点连接的弧段标识码等。多边形文件由多边形记录组成，包括 多边形标识码、组成该多边形的弧段标识码以及相关属性等。现以图 2-11为例，列出拓扑数据结构的弧段文件格式（表2-5）:图2-11矢量结构图形基本元素O结点弧段多边形C?岛N结点码弧段码多边形弧段号起结点Ni叫込Ni务叫5-10鹫结点左多边形P2PlPl右多边形P1卩5*拓扑数据结构最重要的技术特征和贡献是具有拓扑编辑功能。这 种拓扑编辑功能，不但保证数字化原始数据的自动查错编辑，而且可 以自动形成封闭的多边形边界，为由各个单独存储的弧段组成所需要 的各类多边形及建立空间数据库奠定基础。拓扑编辑功能包括多边形连接编辑和结点连接编
13、辑，前者指顺序 连接组成封闭多边形一组线段的编辑，后者指顺序连接环绕某个结点 所有多边形的编辑。具体的编辑算法如下：(1)多边形连接编辑。例如，设需要对多边形P1进行编辑，其算法过 程为： 从表2-5所示的弧段文件中，检出与当前编辑的多边形P1相关的 所有记录：郁段号左窑过总右窑过形ClNiNiPiC-JNiNiNi恥=- 在检出的记录中，计算机检查当前编辑的多边形P1所处的位置： 如果P1位在左多边形位置，将之与位于右多边形位置的多边形号相交换，同时也将该记录的结点号位置作相应的交换;反之，如 果当前编辑的多边形P1位于右多边形位置，则该记录的所有数据 项顺序不作改变。按照上述规则，检出的记
14、录变为以下形式：翌结点左窑过形右窑边总ClNiN-iPlNi恥曲Pl皿NiPl 从经过代码位置转换的记录中，任取一个起结点作为起点，顺序连 接各个结点，必要时可对记录的前后顺序作调整，使得连接的结点 能自行封闭，如图2-12所示。如果依照上述顺序连接的结点不能自行闭合，或者出现记录缺 损或记录多余等情况，则表示弧段文件有错，必须改正出错的记录。直到所有多边形都经过编辑和改正，再转入结点连接编辑。左实过形右窑过形一* N2PinP4PiCiHi二N1Pi(2) 结点连接编辑。例如，设需要对结点N2进行编辑，其算法过程为: 从表2-5所示的弧段文件中，检出与当前编辑的结点N2相关的所有记录：左窑过总右窑过形jCiNiNiPiNiNiRNiNsPiR 在检出的记录中，计算机检查当前编辑的结点N2所处的位置： 如果N2位在起结点位置,将之与位于终结点位置的结点号相交换, 同时也符该记录的多边形号位置作相应的交换;反之，如果当前编辑 的结点N2位于终结点位置，则该记录所有数据项顺序不作改变。按照上述规则，检出的记录变为以下形式：郁段号左窑过总右窑过形NiNiPiNiNiRNsNiP; 从经过代码位置转换的记录中，任取一个左多边形作为起点，顺序 连接各个多边形，同样，必要时可对记录的前后顺序作调整，使得 连接的多边形能首尾呼应
