空间拓扑查询研究与实现

鲁 磊，张红波

(73603部队，江苏 南京210049)

一、引 言

空间数据库作为现代数据库的一个分支，已经发展的比较成熟。空间拓扑关系是空间数据库研究中的一个重要问题。空间对象间的拓扑关系、特性和操作已被广泛讨论。

本文在Topology Suite的基础上，扩展了空间拓扑操作类，提出了自己的空间数据拓扑查询语言以及在查询结果显示时用到的索引算法。并对这些工作进行了系统的理论分析，在实际项目中对查询语言进行试验分析。分析结果表明，本文的拓扑查询语言可以准确高效的对空间数据进行查询与分析。

二、空间数据类型

开放空间信息协会(The Open Geospatial Consortium，OGC)组织各成员单位制定了一系列地理信息共享方面的标准，它是一个非盈利的、国际化的、自愿协商的标准化组织，其主要目的就是制定与空间信息、基于位置服务相关的标准。OGC的SFS(简单要素规范)APIS(application programming interfaces)规定了对点、线、面以及多点等简单要素的发布、存储、读取和简单操作。这些规范的目的是使得GIS软件设计师在不同的技术下(OLE/COM，SQL，CORBA)能够使用这些接口来操作由简单几何要素组成的要素(如图1所示)。

图1 几何对象模型

图1显示的是SFS中几何对象的关系结构，简单要素中的几何对象主要就是定义了点、线、面和多点、多线、多面。曲线是基类，线和孔曲线的子类。几何集也是基类，复合线，复合面都是几何集的子类。几何体是基类，所有的空间类型都是几何体的子类。

三、空间关系

空间拓扑关系描述空间对象之间在拓扑变化下的不变关系，是空间数据研究中最广泛并且解决方案最完备的一种关系。空间对象之间的拓扑关系包括点/点关系(P/P)、点/线关系(P/L)、点/面关系(P/A)、线/线关系(L/L)、线/面关系(L/A)和面/面关系(A/A)，这些关系表现了对象间的相邻性、连接性、关联性、闭合性、包含性和一致性等，是对空间数据进行查询处理的依据［1］。

对于空间对象之间的拓扑关系的描述，主要有基于点集拓扑学的拓扑模型和基于图论的拓扑模型。基于点集拓扑学的空间拓扑关系描述有3种方法：Egenhofer提出的四交模型和九交模型［2］以及扩展九交模型。基于点集拓扑学的空间关系描述框架能够十分有效地描述有公共元素的空间目标间的拓扑关系，甚至能够根据交集的维数更进一步区分成为各种不同形式。

九交模型实现了空间对象之间的拓扑关系描述。该模型主要以点集拓扑学为基础，用两个对象的内部(Ao)、边界(∂A)与外部(A－)子集是否相交来刻画两个对象间的拓扑关系。具体的可用九交矩阵来表示，即

集合有相交(1)和不相交(0)两种情况。可以区分29=512种不同的情况。

四、基于Topology Suite的空间拓扑查询实现

为实现空间对象存储，本文引入自定义的空间数据类型，使用的空间抽象数据类型包括非实例化的基类Geometry和基本派生类 Point、Curve、Surface和Geometrycollection等，同时规定了与派生类相适应的空间参考系。本文还扩展SQL使之包含空间关系谓词，根据OGC的简单要素规范，定义了空间对象之间的关系和空间分析功能，通过采用C#开发语言实现空间拓扑处理函数，从而支持空间查询。在得到查询结果数据后，通过空间R树索引，将查询结果以地图形式返回给客户。

1.拓扑查询空间操作类

本文采用维扩展九交模型处理几何体间的拓扑关系，使用关联算法实现基于维扩展九交模型的拓扑结构计算。首先设计了数据结构，定义了相关的空间操作类。如图2所示，主要包括：①Geometry类，定义最基本的几何体对象和基本属性(如坐标序列、面积、最小外包矩形等)及拓扑关系判断方法;②IntersectionMatrix类，用于描述维扩展九交矩阵及匹配的字符串;③geometrygraph类，用于构建两个几何体对象的拓扑结构图，拓扑结构图由Node和Edge组成，分别对应几何体的节点和边线，每个成员以标签表示其相对于几何体的拓扑位置，以几何体a的节点a1为例：如下图，a的一个节点a1内含于 b，则得出 a1标签为{a：ebi;b：iii}(e，b，i分别表示外部、边界、内部);④Dimension类定义平面二维几何对象维度;⑤Location类定义矩阵行列与几何体内部、外部、及边界的关系。

图2 拓扑查询空间操作类

2.空间查询语言设计

作为与数据库交互的主要手段，查询语言是数据库管理系统的一个核心要素。SQL是用于关系数据库管理系统的一种常见的商业查询语言，具有通用性强，直观便捷的特点。由于空间数据库系统是一种扩充的数据库管理系统，既可以处理空间数据，也可以处理非空间数据，所以通过扩展SQL语言来支持空间数据比较好的选择。本文主要从增加抽象数据类型和空间谓词等方面扩展了标准的关系查询语言SQL，以满足空间数据查询的要求。如表1所示，根据OGC的简单要素规范，定义了空间对象之间的关系和空间分析功能，通过自定义函数的形式，将这些功能加以实现。

表1 空间谓词扩展函数功能

利用上述运算函数可以很方便的构造空间查询语句。例如查询中国政区内所有城市：select cities.* from cities，countries where countries.Name='China'and Within(cities.Sysgeometry，countries.Sys-Geometry)='true'。其中，空间数据的操作函数存储在HashTable中。以相交为例：Hashtable_functions;_functions.Add("Intersects"，"TerraNova.NetTopology-Suite.Geometries.Geometry.Intersects")。

3.空间数据拓扑查询流程

利用关联算法计算几何体之间的拓扑关系分为5个步骤(如图3所示);①建立几何体对象的拓扑结构图，拓扑结构图包含了对应几何体的节点和边线，其中每个节点和每条边线都被标志其相对于原几何体的拓扑位置;②初始化几何体对象的交集矩阵。实例化交集矩阵模型对象，将其字符串设为默认值“＊＊＊＊＊＊＊＊＊”;③获取两个几何体间的交集，可利用单调链方法快速精确地求出交集，将几何体的边线分解成单调链，使用双交点法简单求出两条单调链之间的交点，即为几何体之间交集的节点，添加到拓扑结构图中;④在几何体间的交集部分插入节点，并已添加到拓扑结构图中之后，通过拓扑结构图成员的标签，计算交集节点的标签，再计算几何体的拓扑结构图中独立元件的标签，独立元件是指该几何体中与其他几何体不相交的节点或边线;⑤根据拓扑结构图中所有成员的标签更新交集矩阵。

图3 空间数据拓扑查询处理流程

五、系统试验和应用

1.试验数据准备

试验数据采用ESRI(美国环境系统研究所)提供的世界地图数据(该数据的制作时间为1980年)作为输入，格式为SHP格式。

试验分为两组，一组是空间关系的查询，以求中国政区内的城市为例;另一组是空间操作的查询，以求中国和蒙古合并后的形状为例。

2.空间关系查询

为了对空间数据拓扑查询进行正确性进行评估，结合课题组已有的空间关系查询方法，在实际项目中进行了测试。下面就以求全球数据中中国政区内所有的城市为例。

首先需要从数据库中获取城市数据和中国政区数据。可以判定城市数据为一个点集，设为几何体a;中国政区数据则为一个区域，设为几何体b，则本例求的是几何体a相交几何体b的部分数据。图4是全球的城市分布图。

图4 全球的城市分布数据图

例1：求出中国政区内所有的城市，可以用以下SQL语句进行查询：

上述查询的文字结果如图5所示，共65条数据。

图5 实际结果记录

3.空间操作查询

为了对空间分析算法的正确性进行评估，下面就以求中国和蒙古合并后的形状为例。

首先从整体上分析中国和蒙古两个国家的形状。执行 SQL语句如下：Select* From Countries Where Countries.Name='China'Or Countries.Name='Mongolia'。

上述查询的文字结果共有两条记录，如图6所示。

图6 实际查询结果文字记录?

例2：求中国和蒙古两个国家合并后的形状。求解该查询可执行如下语句序列。

中国和蒙古合并后共一条记录，文字结果如图7所示。

图7 文字结果

六、结束语

空间数据库技术由于其在商业领域和军事应用等各方面的巨大前景，已成为数据库技术研究与发展的热点。其中，拓扑关系的描述与判断在空间数据建模、空间数据查询、分析和数据更新等方面起着重要的作用。本文在研究空间拓扑关系描述模型的基础上，设计实现的空间数据库拓扑查询与索引功能，性能较高，应用方便，对进一步开发新型空间数据库系统具有重要意义。

［1］陈军，赵仁亮.GIS空间关系的基本问题与研究进展［J］.测绘学报，1999，5(2)：95-102.

［2］张骏，秦小麟，包磊.一种三维空间9-交模型的简化方法［J］.南京航空航天大学学报，2006，38(3)：255-261.