第三节 矢量数据结构

基于矢量模型的数据结构简称为矢量数据结构。矢量也叫向量，数学上称“具有大小和方向的量”为向量。矢量数据结构是通过记录坐标的方式来表示点、线、面等地理实体空间分布的一种数据组织方式。

一、矢量数据结构的概念

矢量数据结构直接以几何空间坐标为基础，记录取样点坐标。矢量数据结构的优点是：坐标空间设为连续，允许任意位置、长度和面积的精确定义；数据以点、线或多边形为单元进行组织，结构简单、直观、易实现等优点。其缺点是数据结构复杂、矢量叠置较为复杂、数学模拟比较困难、技术复杂等。这种数据组织方式定位明显，属性隐含，能最好地逼近地理实体的空间分布特征，数据精度高，数据存储的冗余度低，便于进行地理实体的网络分析，但对于多层空间数据的叠合分析比较困难。

二、矢量数据结构的编码的基本内容

（一）点实体

点实体包括由单独一对x，y坐标定位的一切地理或制图实体。在矢量数据结构中，除点实体的x，y坐标外还应存储其他一些与点实体有关的数据来描述点实体的类型、制图符号和显示要求等。点是空间上不可再分的地理实体，可以是具体的也可以是抽象的，如地物点、文本位置点或线段网络的结点等，如果点是一个与其他信息无关的符号，则记录时应包括符号类型、大小、方向等有关信息；如果点是文本实体，记录的数据应包括字符大小、字体、排列方式、比例、方向以及与其他非图形属性的联系方式等信息。对其他类型的点实体也应做相应的处理。图2-5说明了点实体的矢量数据结构的一种组织方式。

（二）线实体

线实体可以定义为直线元素组成的各种线性要素，直线元素由两对以上的x、y坐标定义。最简单的线实体只存储它的起止点坐标、属性、显示符等有关数据。例如，线实体输出时可能用实线或虚线描绘，这类信息属符号信息，它说明线实体的输出方式。

弧、链是n个坐标对的集合，这些坐标可以描述任何连续而又复杂的曲线。组成曲线的线元素越短，x、y坐标数量越多，就越逼近于一条复杂曲线，既要节省存储空间，又要求较为精确地描绘曲线，唯一的办法是增加数据处理工作量。亦即在线实体的纪录中加入一个指示字，当启动显示程序时，这个指示字告诉程序：需要数学内插函数(例如样条函数)加密数据点且与原来的点匹配。于是能在输出设备上得到较精确的曲线。不过，数据内插工作却增加了，弧和链的存储记录中也要加入线的符号类型等信息。

线的网络结构。简单的线或链携带彼此互相连接的空间信息，而这种连接信息又是供排水网和道路网分析中必不可少的信息。因此要在数据结构中建立指针系统才能让计算机在复杂的线网结构中逐线跟踪每一条线。指针的建立要以结点为基础。如建立水网中每条支流之间连接关系时必须使用这种指针系统。指针系统包括结点指向线的指针。每条从结点出发的线汇于结点处的角度等，从而完整地定义线网络的拓扑关系。

如上所述，线实体主要用来表示线状地物(公路、水系、山脊线)、符号线和多边形边界，有时也称为“弧”“链”“串”等，其矢量编码包括的内容如图2-6所示。其中唯一标识是系统排列序号：线标识码可以标识线的类型；起始点和终止点可以用点号或直接用坐标表示；显示信息是显示线的文本或符号等；与线相连的非几何属性可以直接存储于线文件中，也可单独存储，而由标识码连接查找。

（三）面实体

多边形(有时称为区域)数据是描述地理空间信息的最重要的一类数据。在区域实体中，具有名称属性和分类属性的，多用多边形表示，如行政区、土地类型、植被分布等；具有标量属性的有时也用等值线描述(如地形、降雨量等)。

多边形矢量编码，不但要表示位置和属性，更重要的是能表达区域的拓扑特征，如形状、邻域和层次结构等，以便使这些基本的空间单元可以作为专题图的资料进行显示和操作，由于要表达的信息十分丰富，基于多边形的运算多而复杂，因此多边形矢量编码比点和线实体的矢量编码要复杂得多，也更为重要。

面实体编码主要有实体式、树状索引法、双重独立式、链状双重独立式。

1.实体式

实体数据结构指构成多边形边界的各个线段，以多边形为单元进行组织，按照这种数据结构，边界坐标数据和多边形单元实体一一对应，各个多边形边界都单独编码和数字化。如图2-7所示的多边形，可以用表2-10的数据编码来表示。

这种数据结构具有编码容易、数字化操作简单和数据编排直观等优点，但这种方法也有以下缺点：

（1）相邻多边形的公共边界被数字化并存储两次，造成数据冗余和碎屑多边形数据不一致，浪费空间，导致双重边界不能精确匹配。

（2）自成体系，缺少多边形的邻接信息，无拓扑关系，难以进行邻域处理，如消除多边形公共边界，合并多边形。

（3）岛作为一个单个图形，没有与外界多边形联系，不易检查拓扑错误。

所以，这种结构只用于简单的制图系统中。

2.树状索引法

树状索引法数据结构采用树状索引以减少数据冗余并间接增加邻域信息，具体方法是对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状索引结构。

树状索引结构消除了相邻多边形边界的数据冗余和不一致的问题，在简化过于复杂的边界线或合并多边形时可不必改造索引表，邻域信息和岛状信息可以通过对多边形文件的线索引处理得到，但是比较繁琐，因而给邻域函数运算、消除无用边、处理岛状信息以及检查拓扑关系等带来一定的困难，而且两个编码表都要以人工方式建立，工作量大且容易出错。

这种数据结构的优点：用建索引的方法消除多边形数据的冗余和不一致，邻接信息、岛信息可在多边形文件中通过是否公共弧段号的方式查询。

但缺点是表达拓扑关系较繁琐，给相邻运算、消除无用边、处理岛信息、检索拓扑关系等带来困难，以人工方式建立编码表，工作量大，易出错。

图2-9和图2-10分别为图2-8的多边形文件和线文件树状索引。

3.双重独立式

这种数据结构最早是由美国人口统计局研制来进行人口普查分析和制图的，简称为DIME(Dual Independent Map Encoding)系统或双重独立式的地图编码法。它以城市街道为编码的主体，其特点是采用了拓扑编码结构。

双重独立式数据结构是对图上网状或面状要素的任何一条线段，用其两端的节点及相邻面域来予以定义。例如对图2-11所示的多边形数据，用双重独立数据结构表示如表2-11所示。

表2-11中的第一行表示线段a的方向是从节点1到节点8，其左侧面域为O，右侧面域为A。在双重独立式数据结构中，节点与节点或者面域与面域之间为邻接关系，节点与线段或者面域与线段之间为关联关系。这种邻接和关联的关系称为拓扑关系。利用这种拓扑关系来组织数据，可以有效地进行数据存储正确性检查，同时便于对数据进行更新和检索。因为在这种数据结构中，当编码数据经过计算机编辑处理以后，面域单元的第一个始节点应当和最后一个终节点相一致，而且当按照左侧面域或右侧面域来自动建立一个指定的区域单元时，其空间点的坐标应当自行闭合。如果不能自行闭合，或者出现多余的线段，则表示数据存储或编码有错，这样就达到数据自动编辑的目的。例如，从表2-11中寻找右多边形为A的记录，则可以得到组成A多边形的线及结点见表2-12，通过这种方法可以自动形成面文件，并可以检查线文件数据的正确性。

4.链状双重独立式

链状双重独立式数据结构是DIME数据结构的一种改进。在DIME中，一条边只能用直线两端点的序号及相邻的面域来表示，而在链状数据结构中，将若干直线段合为一个弧段（或链段），每个弧段可以有许多中间点。

在链状双重独立数据结构中，主要有四个文件：多边形文件、弧段文件、弧段坐标文件、结点文件。多边形文件主要由多边形记录组成，包括多边形号、组成多边形的弧段号以及周长、面积、中心点坐标及有关“洞”的信息等，多边形文件也可以通过软件自动检索各有关弧段生成，并同时计算出多边形的周长和面积以及中心点的坐标，当多边形中含有“洞”时则此“洞”的面积为负，并在总面积中减去，其组成的弧段号前也冠以负号；弧段文件主要有弧记录组成，存储弧段的起止结点号和弧段左右多边形号；弧段坐标文件由一系列点的位置坐标组成，一般从数字化过程获取，数字化的顺序确定了这条链段的方向。结点文件由结点记录组成，存储每个结点的结点号、结点坐标及与该结点连接的弧段。结点文件一般通过软件自动生成，因为在数字化的过程中，由于数字化操作的误差，各弧段在同一结点处的坐标不可能完全一致，需要进行匹配处理。当其偏差在允许范围内时，可取同名结点的坐标平均值。如果偏差过大，则弧段需要重新数字化。

对如图2-12所示的矢量数据，其链状双重独立式数据结构的多边形文件、弧段文件、弧段坐标文件见表2-13～表2-15。