矢量图形数据拓扑结构的生成及应用.doc

测绘信息网矢量图形数据拓扑结构的生成及应用王卫安王玉树摘要在GIS领域中,拓扑结构是广泛应用的数据结构,它的应用促进了GIS技术在各行各业中的推广和普及。本文结合利用程序实现拓扑关系建立的经验,重点讲述拓扑结构建立的基本过程和思想,并就拓扑结构的应用作一定的阐述。 测绘信息网关键词GIS; 拓扑结构; 数据结构; 拓扑化中国图书资料分类号P208The Establishment of Topological Data Structure and Its ApplicationsWang WeianWang Yushu(Tongji University, Shanghai, 200092)AbstractTopological data structure of graphic data is most wide adopted in recent GIS system, which prompt GIS technology to be extended and spread in various field. The paper focuses on the principle and necessary process on establishment of topological structure as well as its application based upon the experience of its implementation with computer programming. 测绘信息网Key wordsGIS; Topological structure; Data structure; Topologizing0前言地理信息系统(GISGeographic Information system)是一个利用现代计算机图形和数据库技术来输入、存贮、编辑、查询、分析、显示处理图形及属性信息的计算机系统,是融地理学、几何学、计算机科学及各类应用对象为一体的综合性高新技术。GIS的最大特点就在于它能够把周围世界的各种信息与反映地理位置的空间信息有机地结合在一起,并可根据需要对些信息进行分析,将结果提交给各级管理部门作为决策的参考。 测绘信息网GIS 数据库中具有如下基本内容:第一,具有地理位置的空间实体,它是GIS系统中属性数据描述的对象。GIS把地理实体抽象地用点、线、面(多边形)三个基本特征形态来表示。点可以是消防栓、水井等,线可以是道路、河流,市政管线等,面可以是地块、行政区域等等。第二,实体的属性数据。如地块权属主、土地的用途、价格,道路的路面质量、建造年代等等。 测绘信息网第三,空间实体之间的拓扑关系。我们不仅能得出空间实体的空间坐标、长度、面积、高度和体积等描述地物空间尺度的数量特征,而且还能得到地物之间的空间联系。图形数据的拓扑结构就是用来描述空间实体的空间联系。点、线、面三类实体的关系可以有六种组合,即点与点,如消防站与火灾地点的距离;点与线,如一条公路与两旁城镇,村庄之间的联系;点与面,如排污的烟筒与周围的环境;线与线,如表示公路、铁路或河流组成的运输网络;线与面,如一条输油管道流经哪些地区;面与面,如表示洪水影响区域与土地利用的叠合等。这些组合表现了实体间拓扑关系的相邻性、连接性、闭合性、包含性和一致性等,是地理空间数据处理的依据。1GIS空间数据模型 测绘信息网在GIS数据库中存储的数据有记录地理位置及连接信息的空间数据和描述地理要素的属性数据两大类。空间数据通常有矢量数据(Vector Data)和栅格数据(Raster Data)两种形式。栅格数据形式是指地理实体使用网格单元的行列作为位置标识符,行与列的数目取决于栅格的分辨率和实体的特征,是GIS多种空间图形数据形式之一。栅格数据被广泛地使用在遥感像片、数字摄影图像以及各种网格化的数据形式。矢量数据描述地理要素的空间特点是通过离散的位置坐标来表示的。矢量数据较栅格数据具有空间关系描述全面,对线状或网络状事务分析方便,空间属性综合查询方便等诸多优点,在城市分区规划和详细规划、土地管理等公用事业的管理中有广泛的应用。在GIS中描述地理实体的要素有点(Points)、线(Lines)、面(Polygons)等。点用来表示那些实体太小的地图上无法用按比例描绘的地理要素。如消防栓、井、测量控制点等;线用来表示那些线状或网络状的地理要素。如溪流、道路、管线等;面用来表示那些由一个封闭的多边形包围的区域状的地理要素。如水系、地块、房屋建筑、行政边界等。矢量数据结构通常有环状多边形数据结构和拓扑化数据结构两种基本形式。环状多边形数据结构与平面解析几何对物体的描述十分相似,点是由一对坐标(x,y)来表示的,线表示成x1,y1,x2,y2,xn,yn的形式,面则表示为x1,y1,x2,y2,xn,yn,x1,y1。环状多边形数据结构不能完整地描述空间实体间的空间关系,而矢量空间数据的拓扑化数据结构可以克服这一缺陷。 测绘信息网2GIS系统中的拓扑结构及其建立拓扑学(Topology)一词源于希腊文,意为“形状的研究”(Study of Form)。拓扑结构就是指在数据结构上借助拓扑几何学的概念来定义空间实体的相互关系。 测绘信息网在GIS系统拓扑数据结构中,通常具有如下三种重要的拓扑形式:1) 说明线串如何相连的连通性(Connectivity),即线串(Line String)是在结点(Node)上相互连接的。2) 多边形是由一系列相连通的线串组成的。3) 记录多边形的相邻信息以表示拓扑结构的连续性(Contiguity)是指根据线串的走向,可以决定谁是左多边形,谁是右多边形。同时,两多边形之所以相邻是因为二者具有共同的边界。2.1图形矢量数据拓扑的组织在数字化矢量图形中,空间实体通常抽象地定义为以下几种特征的实体: 测绘信息网结点(Node):有三条或多于三条通路经过的点或线串(或链)的端点;顶点(Vertex):仅有一条或两条通路经过的点;线段(Line):连接两个点(顶点或结点)之间的通路;线串(Line String or Chain):有线段连接在两个结点之间的通路;面(Polygon):由线串围成的封闭区域,相互间不重叠。目前,对于矢量图形的拓扑关系的描述,主要有基于网络的拓扑模型和基于点集拓扑理论的拓扑模型。基于网络的拓扑模型具有直观,结构清晰,互导性强,便于组织存储等优点。本文地图矢量数据拓扑关系的建立是基于网络拓扑模型的。 测绘信息网2.2地图矢量数据拓扑关系建立的基本过程1) 线的疏化(Lines Simplification)在某些情况下,为了使得图形曲线更为圆滑、美观,往往数字化时取点过于密集,超出了实际的需要程度,而且使得查询、分析速度迟缓。在保证实际精度不明显下降的情况下,我们选用较少的关键点来表示曲线。对于近似直线的曲线直接用一段直线来代替。使得数据的存储量明显减少,并提高建立线串结点表、线串表、面表的速度,提高查询、分析的速度。 测绘信息网2) 长线断列(Fracture)在线的相交点上产生新的结点,使原来连续的线在交点处被打断。3) 消除隙差并删除重复线数字化时,相应图上的一个点会在计算机内得到一对坐标,我们称之为图纸上点的映射点坐标。在数字化过程中由于对同一点可能进行多次数字化,如某个点既为房角点又是围墙点,还可能是界址点,此时由于每次数字化时,同一点每次对应的映射点之间可能存在一定大小的隙差(Overshoot or Undershoot)。另外,数字化时没有使用或未正确使用捕捉方式也可能造成隙差的存在。进行隙差的消除工作可以保证线串的连通性。在进行数字化时,有时可能对同一边界进行多次重复输入,造成数据冗余。建立拓扑关系应考虑消除重复线,减少数据冗余。4) 连成网络 测绘信息网检查处理线遗漏、在连续线中出现不应有的结点的等情况。5) 建立线串点表,线串表。由此,我们可以知道一条线串的起始结点和尾结点,以及顶点(Vertex)。同时,知道一个结点我们也能很快地找出通过此结点的所有线串。 测绘信息网6) 搜索多边形,建立面串表从任意一条线串开始,根据左转法或右转法进行多边形的搜索。在多边形搜索过程中,当重新回到起始的线串时,完成一个多边形的搜索,并根据线串的前进方向,确定线串的左侧多边形或右侧多边形。在多边形自动生成过程中,应遵循线串的先后相继的原则,即前一条线串的尾结点为后继线串的头结点。7) 生成多边形表根据面串表 ,找出与当前的多边形相关的所有线串,计算得出多边形的面积、周长。进行标识点在多边形内的判断,得出多边形的用户标识,用于同属性库相连。2.3拓扑数据的组织拓扑化数据结构描述空间实体间的相互关系,我们将图形的矢量数据设计成下列的组织方式(图1),为了程序更好地实现,我们增加了线串结点表,面线串表指针,为其后的线串表的建立、面表的建立提供必要的支持。 测绘信息网图1是一个实例,用其点坐标表、线段表、线串线段表、线串表、面表线串表、面表等表示空间关系。图形中顶点(包括结点)的坐标及点的标识存储在一个“点坐标表”中;“线段表”存储线的标识和两个端点的标识(或指针);“线串线段表”存储一条线串由哪些线段组成,包含了一个相互连通的线段序列,每根线串的两端即为结点;“线串表”存储某线串在“线串线段表”中的线段序列的起始位置。“面线串表”存储组成面的线串序列,以及使用此线串的前进方向(0表示逆时针方向,1表示顺时针方向)。“面表”中包含面的内部标识、用户标识、与此面实体相关的线串在“面线串表”的线串序列的起始位置,用户标识为用户自己确定的,如一宗地的宗地号或某一建筑物的名称等。图1实例2.4程序实现的几个关键 测绘信息网1) 面串表的生成面串表的生成从线串表的表头开始,到线串表的结束为止。一个多边形的搜索是从任意一条线串开始、到重新回到多边形的起始边界为止。如果在多边形的搜索过程中,不能返回到多边形的起始边界则视为当前线串为悬挂线,在图形上用醒目的颜色表示,提示操作人员编辑修改。如图1所示,假设从18号线串开始一新的多边形的搜索,由线串表可以知道18号线串的尾结点的标识为24,程序就到线串表中查找始结点为24的14号和15号线串。此时要判断14和15号线串的前进方向,即24号点是它们各自的起始结点还是尾结点。为起始结点用其起始方位角减去18号线串的尾端方位角,找出差最小的线串标识15,否则用其尾端方位角相减。根据此线串的前进方向确定其左或右的多边形标识为4。如此反复执行,直到返回到起始的18号线串为止。2) 面表的生成 测绘信息网根据面串表,把所有与当前研究的多边形相关的线串按先后相继的原则,并按照记录中的线串的前进方向,将围成该多边形的所有点的标识放在一动态数组中,然后计算其面积、周长。根据点在多边形内的判别方法射线法,找出用户标识记录在面表中。3) 对最外多边形和内部岛屿的解决当一个多边形仅有一条线串围合而成、而且该线串的外侧(左或右)多边形的标识只有一个时,我们判定该多边形为内部岛屿,其外侧多边形的面积应减去其内部岛屿的面积。如一多边形的面积等于其余的所有的多边形的面积的总和,认为围成该多边形的所有的线串为图形的外边界,面积计为负数形式。在形成坐标表时我们利用限差处理,保证了点的唯一性。并且在生成线串表的过程中,因为利用线段表中的点标识,而不需计算点的坐标值,大大地提高拓扑处理的速度。另外,删除重复线,对边界线只进行一次存储的方式减小了图形矢量的数据冗余。3具有拓扑关系数据的应用 测绘信息网在目前的GIS领域中,拓扑结构是最广泛应用的空间数据结构。利用拓扑型数据结构,我们可以将属性数据库和空间数据库通过实体的标识(在GIS中,每一实体其标识唯一)连接起来,使得许多分析、查询工作相对简化。拓扑结构的应用促进了GIS技术在各个应用领域的推广和普及。3.1网络追踪 测绘信息网网络分析是利用GIS产品进行空间分析的一个重要应用。网络(Network)是由一系列的线状要素和点状要素组成的,用于模拟、分析资源在线性网络状空间内的运动。网络追踪是拓扑结构在网络分析中的一个重要应用。例如在城市地下管线的管理信息系统中,将各个结点描述为地下管网的控制阀,一条线串(或链)表示为交叉分布的地下管线。当某一段管线发生故障时,可以在最短的时间内找出该段管线的控制阀,及时排除故障。又如在城市的道路交通网络中,各个结点描述为城市道路中心线在主要交叉路口的交点,每条线串表示城市内部的交通联系。当把每条线串的长度或沿此线串(或链)运输所花费时间或交通费用表示为该路径的权值时,就可以进行最佳路径的选择,为城市交通管理提供服务。网络追踪与空间卫星定位系统(GPS)技术相结合,可以使得GIS的应用得到更大的发展。3.2多边形的叠置分析多边形的叠置分析是指将同一地区,同一比例尺的两组或两组以上的多边形要素的数据文件进行叠置,根据两组多边形边界的交点来建立具有多重属性的多边形或进行多边形范围内的属性特征的统计分析,即所谓的合成叠置和统计叠置。我们知道,非拓扑化的矢量模型对公共边界需要定义两次,同时由于隙差存在使得多边形在多次叠合后,其边界变得相当复杂,从而很难保证多边形的数据结构,加上重复数字化的可能使得数据存储量、数据冗余都特别大,造成查询、空间分析特别缓慢,使其很难适合多次多边形的叠置分析。在大比例尺的GIS系统,诸如城市的详细规划管理系统、土地管理信息系统以及公用事业的管理系统中,常常选择具有拓扑结构的多边形进行多边形的叠合分析。 测绘信息网多边形的叠置分析的应用十分广泛,是GIS系统的必不可少的空间分析功能之一。如将地块多边形和高程多边形进行叠置,提取土地使用为住宅和高程低于洪水水位的多边形,通过数据计算,可以大体地估算出由于洪水带来的财产损失。又如在城市规划管理中,将某一权属地块多边形与建筑层多边形或者与绿化多边形进行多边形的叠置分析,就可以获得宗地的建筑密度或绿化比率,从而为城市规划管理、决策提供服务。3.3数字化数据的检查(质量控制)优化数字化数据的检查是拓扑结构的又一应用。在目前GIS系统中,地图数字化仍是数据采集的重要方式之一,其质量的优劣对GIS系统的可靠性和实用性,以及其空间查询、分析功能具有很大的影响。由于拓扑结构在空间关系上比环状结构更为严密而内容丰富,并且又是靠计算机来自动建立的,因而能容易地在生成拓扑关系的过程中检查出数据输入过程 的错误。如图3所示,在拓扑过程中我们可以检查出:1) 数字化时,取点过于密集的情况。2) 作为多边形用户标识的重复输入或者由于数字化时遗漏了公共边界,造成的一个多边形具有多个用户标识的现象。3) 由于数字化时没有使用或没有正确使用捕捉方式,造成的线过短或者过长而未在结点处正确连接的情况。4) 用户标识遗漏或标识点的位置偏离太大的情况。5) 在线串两两相交处未产生结点和一条线串中出现不必要的结点的情况。 测绘信息网6) 利用欧拉(Euler)定理检查面数f、节点数v、线串数e的关系:f-e+v=1。4结束语 测绘信息网目前,大多数的GIS系统均采用拓扑结构的数据模型,拓扑结构的应用拓宽了GIS的空间分析功能的应用领域,为GIS技术的推广、普及起到巨大的推动作用。但是几乎所有的GIS系统所提供的拓扑处理功能往往是与GIS平台绑在一起的。不同系统之间进行数据转换时,就很难保证其原有拓扑结构的完整转换,给GIS的应用带来诸多不便。我们在对拓扑结构进行深入地分析之后,利用C和VC+面向对象的技术设计实现了拓扑关系的自动建立。并完成了AutoCAD R12下数字化地图的拓扑建立,最后将拓扑关系写成MIF和MID文件转入MapInfo系统中,这样使原有的拓扑结构得以保证,又成功的实现了不同系统的数据之间的转换,具有一定的实用价值。当然程序本身还有待进一步的改进和完善,我们将在今后的时间里将程序功能进一步完善,使其能更好实现拓扑关系建立过程,拓