空间数据增量更新是综合利用不同来源的现势性数据，通过对变化信息进行检测提取增量信息，最后对原始数据库进行增加、删除、修改和关系协调等操作^{[1, 2]}。由于在更新过程中各个来源数据的精度、尺度、主题、时态等不尽相同，而且操作过程复杂，使更新后的数据存在不一致的状况，即存在空间冲突^[3]。这些冲突的存在降低了空间数据的更新质量，严重影响着空间数据的可用性。因此，如何对更新后的空间数据进行冲突检测、发现错误的拓扑关系并进行纠正，就成为空间数据库更新后必须面对的问题。

空间冲突包括空间数据的几何结构冲突、拓扑冲突、方向冲突和距离冲突。文献[4-6]分别以四交或九交模型为拓扑关系计算和表达的基础，通过定义空间目标间的拓扑关系一致性规则进行拓扑错误检测。Gadish通过数理统计的方法，发现空间目标间拓扑规则，提出了基于规则发现的空间冲突检测方法^[7]。陈军等在进行全国1:5万数据库更新时，从应用的角度对水系更新中河流与等高线、河流与道路网等空间目标间的不合理空间关系进行了自动检测方法的研究，在应用中取得了很好的效果^[8-10]。杨敏从匹配的角度对水网与等高线间的冲突进行了检测^[11]。何津、费立凡等对居民地与道路的图形冲突进行了深入的研究^{[12, 13]}。

以上这些研究极大地提高了空间数据中冲突检测的自动化程度，但这些算法并不适合增量更新中的冲突检测。因此，以居民地增量更新为例，本文提出了一种高效的拓扑空间冲突自动检测方法。

1 增量更新拓扑错误检测模型

增量更新的显著特点就是只针对部分发生变化的目标进行更新操作，对未发生变化的目标并没有进行任何操作。因此，冲突也往往发生在这些进行更新操作的空间目标邻近的局部区域，拓扑冲突的检测也应针对更新目标邻近区域，并不需要对更新区域的所有数据进行一次遍历检测。

1.1   利用格网索引的冲突检测算法的基本思想

文献[14]利用Delaunay三角网技术判断更新目标的邻近目标，这种对更新目标邻近对象探测和表达的方法存在着三点不足：①需要对整个检测区域构建Delaunay三角网，然后逐个判断与更新目标相邻近的空间目标，时间代价非常高；②存在一些“伪邻近”目标，如图 1所示，空间目标D为更新的居民地目标，A、B、C、E、F为未更新的目标，利用Delaunay技术可得到更新目标D的邻近对象为A、B、C、E共4个目标，但是由图 1可知，目标E与更新目标D相离较远，不存在冲突的可能性，本文称E这样非真正意义上的邻近目标为“伪邻近”目标。“伪邻近”目标的存在必定大大增加拓扑计算量，影响冲突检测效率；③ Delaunay三角网技术适合表达离散目标的邻近关系，在表达有相交关系的空间目标间的邻近关系时比较困难。

图  1  基于Delaunay三角网的邻近关系表达

Figure  1.  Expressing Neighborhood Relation Based on Delaunay Triangulation

下载: 全尺寸图片 幻灯片

为此，本文提出了利用规则格网表达更新目标的邻近区域，其基本思路是在检测区域建立格网索引，判断更新目标所在的格子集，格子集表示的区域即为更新目标的邻近区域，邻近区域内的空间目标即为更新目标的邻近目标，这样的邻域探测和表达方法既简单又可排除一些与更新目标相距较远的“伪邻近”目标。如图 2所示，若面目标A₁为更新目标，其所占的格子集为图中的灰色区域，即目标A₁的邻近区域，位于邻近区域内的点目标P₁、面目标A₂、线目标L₂为与目标A₁的邻近对象，即需要进行冲突检测的候选集。

图  2  利用格网索引表达邻近关系

Figure  2.  Expressing Neighborhood Relation Using Grid Index

下载: 全尺寸图片 幻灯片

居民地增量更新拓扑语义冲突检测的基本思路如下：针对增量更新中拓扑冲突只发生在更新目标所在局部区域的特点，利用格网索引的思想表达更新居民地目标的邻近区域，根据更新目标所在的格子集，判断出位于这些格子集内的邻近空间目标，进而排除大量无关空间目标，通过计算更新居民地目标与这些邻近空间目标的拓扑关系是否满足冲突规则来检测更新中的拓扑冲突。

1.2   拓扑关系的表达与计算

现有的拓扑表达模型除了经典的4交、9交、Voronoi图模型外，近年来又提出了许多细化表达模型，这些表达模型区分度越来越高，但计算越来越复杂。4交模型区分的类型较少，Voronoi图模型和细化表达模型计算都比较复杂，9交模型无法将发生在居民地边界的冲突区分开来，线状河流与居民地之间的拓扑关系如图 3所示，而且这两种拓扑关系的9交表达是相同的。但是图 3(a)表示的拓扑关系为禁止的关系；图 3(b)表示的拓扑关系是一种允许的拓扑关系，这时就出现了无法正确区分冲突的状况。另外，类似的状况在面状目标与面状居民地之间也有出现，为了克服这类缺陷，本文建立了扩展9交模型作为拓扑关系表达计算的模型，扩展的9交模型如下：

图  3  居民地与河流的拓扑关系示意图

Figure  3.  Topological Relations Between Settlement and River

下载: 全尺寸图片 幻灯片

式中，T⁹指两空间目标间的9交拓扑表达；insert_dimension指两目标交的维数，取值为-1、0、1、2，当两目标相离时取值设定为-1。

1.3   拓扑冲突规则库的构建

1.3.1   冲突规则的形式化表达

当前, 国内外的学者基于产生式的规则表达方法提出了三元组、四元组及其改进模型^[5]，这些模型在本质上都是相似的，但这些表达模型并没有考虑规则的使用范围，而每个冲突规则都应该有一定的使用范围。本文在文献[15]提出的约束规则模型表达的基础上提出了五元组表达模型：

式中，(Scale, Theme) 表示规则的使用范围，其中Scale表示比例尺，Theme表示规则的主题应用环境；C₁、C₂表示不同的两个不同的要素类；TR为测试条件，在这里指拓扑冲突对应的拓扑关系；S表示冲突的语义描述。

该规则表达模型不仅提高了规则的辨识度，避免了规则之间冲突，而且通用性较强，适用于不同的环境和用途，易于对规则库进行修改和维护。

1.3.2   与居民地相关的拓扑冲突

由于居民地形态多样且与其他许多要素关系密切，使得居民地与其他要素的拓扑冲突的类型较多，表 1列出了居民地与其他要素常见拓扑冲突。

表  1  常见的与居民地相关冲突

Table  1.  Common Topological Conflicts Related to Settlement

要素类	冲突描述	冲突规则形式化表达
道路	道路进入面状居民地	{(Scale, Theme), Settlement, (T9cross, -), Road, 道路穿越居民地}
水系	线状水系与面状居民地边界重合	{(Scale, Theme), Settlement, (T9touch, 1), River, 道路与居民地边界重合}
水系	线状水系穿越面状居民地	{(Scale, Theme), Settlement, (T9cross, -), River, 线状河流穿越居民地}
水系	点房、线房落水	{(Scale, Theme), Building, (T9coveredby, -), Waterarea, 点房、线房入水}
水系	居民地中有面状水域	{(Scale, Theme), Settlement, (T9contain, -), Waterarea, 居民地内部有面状水域}
居民地	面状居民地之间压盖	{(Scale, Theme), Settlement, (T9overlap, -), Settlement, 面状居民地之间相交}
居民地	面状居民地内部有点房、线房	{(Scale, Theme), Settlement, (T9contain, -), Building, 点房、线房落入面状居民地}
境界线	境界线穿越居民地	{(Scale, Theme), Settlement, (T9cross, -), Boundary, 境界线穿越居民地}
注：为表达方便，T9cross表示9交模型所表达的线状目标穿越面状目标的拓扑关系; T9touch、T9coveredby、T9overlap等表达的意思类似；“-”表示条件缺省。

下载: 导出CSV 

| 显示表格

表 1只是列出了居民地要素与其他空间要素常见的拓扑冲突，除此之外，各种应用主题、不同比例尺的数据库中还存在很多其他类型的冲突或自定义的冲突，这里不再一一列出。

1.4   格网索引的设计与建立

本文格网结构采用规则的正方形网格，设每个网格的边长为d，其取值可根据具体的情况进行最优取值。遍历每个要素类的每一个对象并根据其几何类型 (点、线、面) 建立索引关系，具体建立过程比较简单，这里不再赘述。索引的数据结构设计如下：

{

String Featureclass_Code;

List Featureset_Grid[][];

List Gridset[];

}

索引数据结构中有以下3个变量：Featureclass_Code表示索引对应的要素类编码；Featureset_Grid[][]表示格网对应的索引数组，Featureset_Grid [i][j]表示行列号分别为i、j的格子包含的相应要素类的空间目标集，方便查找每个格子中包含的要素目标；Gridset[]表示要素类中空间目标邻近区域的索引数据，Gridset[i]表示相应要素类ID号为i的空间目标对应的格子集，方便查询空间目标的邻近区域。

1.5   检测步骤

在拓扑语义冲突规则形式化表达和索引关系建立的基础上，基于格网索引的居民地增量更新拓扑冲突检测的流程如图 4，具体步骤如下。

图  4  冲突检测流程图

Figure  4.  Flowchart of Conflict Checking

下载: 全尺寸图片 幻灯片

1) 冲突检测策略采用逐个要素类检测的方法，因此，首先从数据集中读取某个要素类数据作为与更新居民地对象冲突检测的待检测数据，以图 5的虚线表达的湖泊数据为例。

图  5  冲突检测过程图

Figure  5.  Example of Conflict Checking

下载: 全尺寸图片 幻灯片

2) 求出更新对象邻近区域。从居民地增量更新对象集中取出一个更新居民地对象S(图 5中实线多边形)，根据构建的索引关系查询更新居民地对象S对应的格子集Gridset (S) 即为更新居民地对象S的邻近区域 (图 5中的灰色区域)。

3) 筛选可能存在冲突的邻近对象集。遍历Gridset(S)中每个格子，根据每个格子对应的索引数组，查询位于对象S邻近区域内的空间对象集合Prefeatureset (S)={L₁, L₂, L₃}，剔除候选集中最小外界矩形与S的最小外界矩形不相交的空间对象，最终得到与增量更新对象S可能存在冲突的空间对象集Candidate (S)={L₂, L₃}。

4) 计算拓扑关系并与冲突规则进行匹配判断和确认冲突。根据居民地对象S与L₂、L₃的几何类型，分别计算S与L₂、L₃的拓扑关系，与拓扑冲突规则进行匹配，匹配成功判定存在冲突，否则不存在冲突。S与L₂拓扑关系相交，判定两者之间存在拓扑冲突。

5) 遍历其他增量更新居民地对象，并重复步骤2)~步骤4) 操作，直到所有增量更新居民地对象都遍历完毕。

6) 当前要素类数据检测完成后，读取其他要素类数据，重复步骤2)~步骤5)，探测更新居民地对象与各个要素类的拓扑冲突。

7) 输出检测结果并可视化表达出冲突的空间对象和具体位置，以便于纠正。

2 实验分析

实验数据 (图 6) 为美国东部某地区的数据，包括居民地、道路网、面状水系、线状河流以及点状公交站点等5个图层。利用本文提出的方法对待检测区域各个要素类的空间对象建立格网索引关系，格子的大小设为50 m×50 m，根据居民地与各个要素类空间目标拓扑语义冲突定义相应的冲突检测规则，分别利用本文提出的检测方法和基于全局的检测方法进行拓扑冲突检测，检测统计结果如表 2所示。

图  6  实验图例

Figure  6.  Example of Experiment

下载: 全尺寸图片 幻灯片

表  2  拓扑冲突检测结果统计表

Table  2.  Result of Topological Conflict Checking

空间冲突描述	参照图层	冲突个数
		本文	全局
居民地与居民压 盖	居民地	2	2
道路穿越居民地	道路网	6	6
线状水系与居民地相交	线状水系	4	4
居民地落如水中	面状水系	3	3
公交站点落入居民地内	基础设施	1	1

下载: 导出CSV 

| 显示表格

本文提出的针对更新居民地对象局部区域进行冲突检测的方法的检测结果与基于全局遍历的检测方法的检测结果是相同的，因此，本文方法并没有遗漏任何冲突，验证了居民地增量更新过程冲突发生在更新居民地对象的邻近区域内的特点。

为了对算法的效率进行验证，本文对基于全局的检测方法和本文方法的检测效率进行了两组实验的比较分析。第一组实验保持增量居民地对象数量不变，逐渐增加待检测要素类的空间对象数量，检测所用时间的统计结果见表 3；第二组实验保持检测区域各要素类空间对象的数量不变，逐渐增加增量居民地对象的数量，实验结果如表 4所示。

表  3  检测效率统计结果1

Table  3.  Time Consumed in Group 1

实验编号	1	2	3	4	5	6	7	8
数据量/MB	1.09	1.29	1.55	1.70	1.82	1.97	2.05	2.17
本文/s	1.80	2.01	2.30	2.49	2.60	2.79	2.89	3.07
全局/s	116	136	166	179	192	209	219	232
注：增量居民地对象的个数为108个。

下载: 导出CSV 

| 显示表格

表  4  检测效率统计结果2

Table  4.  Time Consumed in Group 2

试验编号	1	2	3	4	5	6	7	8
增量对象数	38	48	58	68	78	88	98	108
本文/s	2.78	2.89	2.98	3.03	3.06	3.11	3.14	3.25
时间/s	81.0	102.4	125.2	146.4	168.0	190.1	212.8	231.7

下载: 导出CSV 

| 显示表格

第一组实验是为了验证检测区域空间对象的数量对检测效率的影响。实验结果表明，随着检测区域空间对象数量的不断增加，基于全局的方法所用的时间增加较快，而本文提出的方法时间增加十分缓慢，可见检测区域空间对象的数量对本文方法的效率影响较小。第二组实验是为了验证居民地增量对象数量对检测效率的影响，实验结果表明，随着居民地增量对象的增多，两种方法的检测时间都是增加的，本文提出的方法每增加10个增量对象检测用时平均增加208 ms，基于全局的方法平均增加21.5 s，可见本文提出的方法与全局检测的方法相比明显更快。

为了弄清楚检测效率与格子大小的关系，我们通过改变格子的大小进行了多组实验来观测检测效率与格子大小的关系，将各组实验结果绘制成了散点图并通过Matlab软件拟合成了曲线 (图 7)。由实验结果可知，随着格子的变大，检测效率先提高后降低，格子太大或太小都会降低检测的效率。从实验可知，边长为4 m时，检测用时15.8 s，当边长为2 000 m时，检测用时为14.5 s，而边长为50 m时检测效率最高，用时为3.1 s，这也是本文格子大小选用50 m×50 m的原因。

图  7  格子大小对检测效率的影响

Figure  7.  Relationships Between Grid Size and Checking Rate

下载: 全尺寸图片 幻灯片

3 结语

本文以居民地增量更新中的拓扑冲突检测为例，针对居民地增量更新过程中拓扑冲突只发生在更新居民地对象邻近区域的特点，通过建立规则格网索引，利用格子集合表达增量更新居民地对象的邻近区域，通过判断增量居民地对象与其邻域内其他要素拓扑关系是否与冲突规则相匹配来检测空间冲突，这样就避免了大量无关的拓扑关系计算，提高了检测效率。最后实验证实了该方法不仅能够检测出拓扑冲突，而且具有较高的效率，与居民地增量更新的特点相一致，能够在更新数据质量检测中得到应用。