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

测绘信息网http://www.othermap.com

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

王卫安 王玉树

摘 要 在GIS领域中,拓扑结构是广泛应用的数据结构,它的应用促进了GIS技术在各行各业中的推广和普及。本文结合利用程序实现拓扑关系建立的经验,重点讲述拓扑结构建立的基本过程和思想,并就拓扑结构的应用作一定的阐述。http://www.othermap.com 测绘信息网 关键词 GIS; 拓扑结构; 数据结构; 拓扑化 中国图书资料分类号 P208

The Establishment of Topological Data Structure and Its

Applications

Wang Weian Wang Yushu (Tongji University, Shanghai, 200092)

Abstract Topological 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. http://www.othermap.com 测绘信息网

Key words GIS; Topological structure; Data structure; Topologizing

0 前言

地理信息系统(GIS—Geographic Information system)是一个利用现代计算机图形和数据库技术来输入、存贮、编辑、查询、分析、显示处理图形及属性信息的计算机系统,是融地理学、几何学、计算机科学及各类应用对象为一体的综合性高新技术。GIS的最大特点就在于它能够把周围世界的各种信息与反映地理位置的空间信息有机地结合在一起,并可根据需要对些信息进行分析,将结果提交给各级管理部门作为决策的参考。http://www.othermap.com 测绘信息网 GIS 数据库中具有如下基本内容:

第一,具有地理位置的空间实体,它是GIS系统中属性数据描述的对象。GIS把地理实体抽象地用点、线、面(多边形)三个基本特征形态来表示。点可以是消防栓、水井等,线可以是道路、河流,市政管线等,面可以是地块、行政区域等等。

测绘信息网—测绘专业门户网站.

测绘信息网http://www.othermap.com

第二,实体的属性数据。如地块权属主、土地的用途、价格,道路的路面质量、建造年代等等。http://www.othermap.com 测绘信息网 第三,空间实体之间的拓扑关系。我们不仅能得出空间实体的空间坐标、长度、面积、高度和体积等描述地物空间尺度的数量特征,而且还能得到地物之间的空间联系。图形数据的拓扑结构就是用来描述空间实体的空间联系。点、线、面三类实体的关系可以有六种组合,即点与点,如消防站与火灾地点的距离;点与线,如一条公路与两旁城镇,村庄之间的联系;点与面,如排污的烟筒与周围的环境;线与线,如表示公路、铁路或河流组成的运输网络;线与面,如一条输油管道流经哪些地区;面与面,如表示洪水影响区域与土地利用的叠合等。这些组合表现了实体间拓扑关系的相邻性、连接性、闭合性、包含性和一致性等,是地理空间数据处理的依据。

1 GIS空间数据模型http://www.othermap.com 测绘信息网

在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。环状多边形数据结构不能完整地描述空间实体间的空间关系,而矢量空间数据的拓扑化数据结构可以克服这一缺陷。http://www.othermap.com 测绘信息网

2 GIS系统中的拓扑结构及其建立

拓扑学(Topology)一词源于希腊文,意为“形状的研究”(Study of

测绘信息网—测绘专业门户网站.

测绘信息网http://www.othermap.com

Form)。拓扑结构就是指在数据结构上借助拓扑几何学的概念来定义空间实体的相互关系。http://www.othermap.com 测绘信息网

在GIS系统拓扑数据结构中,通常具有如下三种重要的拓扑形式: 1) 说明线串如何相连的连通性(Connectivity),即线串(Line String)是在结点(Node)上相互连接的。

2) 多边形是由一系列相连通的线串组成的。

3) 记录多边形的相邻信息以表示拓扑结构的连续性(Contiguity)是指根据线串的走向,可以决定谁是左多边形,谁是右多边形。同时,两多边形之所以相邻是因为二者具有共同的边界。 2.1 图形矢量数据拓扑的组织

在数字化矢量图形中,空间实体通常抽象地定义为以下几种特征的实体: http://www.othermap.com 测绘信息网

结点(Node):有三条或多于三条通路经过的点或线串(或链)的端点; 顶点(Vertex):仅有一条或两条通路经过的点;

线段(Line):连接两个点(顶点或结点)之间的通路;

线串(Line String or Chain):有线段连接在两个结点之间的通路; 面(Polygon):由线串围成的封闭区域,相互间不重叠。

目前,对于矢量图形的拓扑关系的描述,主要有基于网络的拓扑模型和基于点集拓扑理论的拓扑模型。基于网络的拓扑模型具有直观,结构清晰,互导性强,便于组织存储等优点。本文地图矢量数据拓扑关系的建立是基于网络拓扑模型的。http://www.othermap.com 测绘信息网 2.2 地图矢量数据拓扑关系建立的基本过程 1) 线的疏化(Lines Simplification)

在某些情况下,为了使得图形曲线更为圆滑、美观,往往数字化时取点过于密集,超出了实际的需要程度,而且使得查询、分析速度迟缓。在保证实际精度不明显下降的情况下,我们选用较少的关键点来表示曲线。对于近似直线的曲线直接用一段直线来代替。使得数据的存储量明显减少,并提高建立线串—结点表、线串表、面表的速度,提高查询、分析的速度。http://www.othermap.com 测绘信息网 2) 长线断列(Fracture)

在线的相交点上产生新的结点,使原来连续的线在交点处被打断。 3) 消除隙差并删除重复线

数字化时,相应图上的一个点会在计算机内得到一对坐标,我们称之为图纸上点的映射点坐标。在数字化过程中由于对同一点可能进行多次数字化,如某个点既为房角点又是围墙点,还可能是界址点,此时由于每次数字化时,同一点每次对应的映射点之间可能存在一定大小的隙差(Overshoot or Undershoot)。另外,数字化时没有使用或未正确使用捕捉方式也可能造成隙差的存在。进行隙差的消除工作可以保证线串的连通性。

在进行数字化时,有时可能对同一边界进行多次重复输入,造成数据冗余。建立拓扑关系应考虑消除重复线,减少数据冗余。 4) 连成网络http://www.othermap.com 测绘信息网

检查处理线遗漏、在连续线中出现不应有的结点的等情况。 5) 建立线串—点表,线串表。

测绘信息网—测绘专业门户网站.

测绘信息网http://www.othermap.com

由此,我们可以知道一条线串的起始结点和尾结点,以及顶点(Vertex)。同时,知道一个结点我们也能很快地找出通过此结点的所有线串。http://www.othermap.com 测绘信息网 6) 搜索多边形,建立面—串表

从任意一条线串开始,根据左转法或右转法进行多边形的搜索。在多边形搜索过程中,当重新回到起始的线串时,完成一个多边形的搜索,并根据线串的前进方向,确定线串的左侧多边形或右侧多边形。在多边形自动生成过程中,应遵循线串的先后相继的原则,即前一条线串的尾结点为后继线串的头结点。 7) 生成多边形表

根据面—串表 ,找出与当前的多边形相关的所有线串,计算得出多边形的面积、周长。进行标识点在多边形内的判断,得出多边形的用户标识,用于同属性库相连。 2.3 拓扑数据的组织

拓扑化数据结构描述空间实体间的相互关系,我们将图形的矢量数据设计成下列的组织方式(图1),为了程序更好地实现,我们增加了线串—结点表,面—线串表指针,为其后的线串表的建立、面表的建立提供必要的支持。http://www.othermap.com 测绘信息网

图1是一个实例,用其点坐标表、线段表、线串—线段表、线串表、面表—线串表、面表等表示空间关系。图形中顶点(包括结点)的坐标及点的标识存储在一个“点坐标表”中;“线段表”存储线的标识和两个端点的标识(或指针);“线串—线段表”存储一条线串由哪些线段组成,包含了一个相互连通的线段序列,每根线串的两端即为结点;“线串表”存储某线串在“线串—线段表”中的线段序列的起始位置。“面—线串表”存储组成面的线串序列,以及使用此线串的前进方向(0表示逆时针方向,1表示顺时针方向)。“面表”中包含面的内部标识、用户标识、与此面实体相关的线串在“面—线串表”的线串序列的起始位置,用户标识为用户自己确定的,如一宗地的宗地号或某一建筑物的名称等。

测绘信息网—测绘专业门户网站.