基于关系探测聚类的图形自动接边算法

2011-05-31 11:11周丽珠刘富东周义军王光昇

城市勘测 2011年6期

周丽珠，刘富东，周义军，王光昇

(1.天津市测绘院，天津 300381;2.天津市市政工程建设公司，天津 300100)

1 引言

地理信息是图形信息和属性信息两类信息的集成，地理要素是地理信息的载体。现实中，所有的地理要素都是完整的个体。由于传统习惯和用户的需求，数字测图仍采用分幅的图幅设计方法，将连续的地表空间划分为若干子空间，将图幅边线处完整的地理实体分割后放置在相邻的图幅中。而实际应用中，所需的数据中地理要素应为一个完整的个体，因此，数据的图幅接边不可避免，如何精确高效地解决图幅接边问题成为测图领域中的一个研究课题，同样也是GIS应用领域的一个研究课题。为此，笔者设计了一种基于关系探测聚类的图幅自动接边算法，并利用ArcGIS Engine 9.3二次开发组件实现了此算法，提高了接边效率和准确度。

2 自动接边关键技术

2.1 地物匹配

接边线两侧的地物自动匹配是自动接边算法的核心所在，本文从如下三个方面提高匹配的准确度:类别匹配，图形匹配和属性匹配。

(1)类别匹配，只有同类的地物才进行匹配。在数据表现上，以图层为划分单位。

(2)图形匹配，一般以距离为指标，距离在阈值范围内的图形要素才进行匹配。但是，面要素应排除点连接的情况，只保留线连接情况，如图1所示。

(3)属性匹配，综合考虑属性结构和属性值这两类因素，完全相同，则匹配成功，否则失败。

这三方面，每一方面都独立于其他两方面存在，假设每方面的匹配错误概率都为10%，那么，综合考虑三方面后的匹配错误率为P，则P在区间［0，10%］内，由“中心极限定理”可知，如果一个量是由许多微小的独立随机因素影响的结果，那么这个量就可看成符合正态分布的，可见这种匹配系统是可行且有效的。

图1 面要素连接的两种方式

2.2 空间聚类

空间聚类是将空间对象几何划分为由相似对象组成的多个簇的过程。同簇内的对象之间具有尽可能大的相似性，而不同簇的对象之间则具有较大的差异性，从而有助于人们认识现象的整体分布模式。在GIS研究中，学者们将计算几何技术、图论方法与传统的聚类分析方法结合提出了面向空间目标的空间聚类方法。

本文基于空间聚类方法的思想，联系自动接边的实际需求，设计出基于关系探测聚类的图形自动接边算法，方便接边检查，提高了运算效率。

2.3 合并要素

合并要素是将某类几何要素合成一体，并保证其属性不变。在理论上，这些几何要素应完全吻合，实际中，由于数据的误差，常常做不到这一点。如图2所示，线要素间存在错位和面要素间存在缝隙。这时，就需要采取一些方法来将几何要素接合起来，使得图形完全吻合［1］。

图2 合并要素错误

解决这个问题通常有三种方式［2］:

(1)平均法

平均法是取图形两边待接点的坐标均值作为接边后的点的坐标。该方法简单易行，适用于接边误差在精度允许范围内的各种直线、折线的接边处理，容易实现接边的全自动批量处理。

(2)强制法

强制法是把一条待接边的待接点强制附和到另一条待接边的待接点上。该方法主要用于用户能明显判断出哪一条待接边比另一条待接边更准确、可靠，适合交互式的接边处理。

(3)优化法

无论采用平均法还是强制法，在边界处都要产生一个拐点。一般拐点的拐角很小。但是如果待接边明显是一条直线边的话，这个很小的拐角也影响图形美观。因此应考虑接边后两端线段仍要在一条直线上，既要共点，也要共线。

以上三种方式各有优缺点，可根据实际情况决定采用哪种方式。本文采用了平均法的方式处理图形误差，实现自动接边算法。而且线要素和面要素可以统一为一种方式进行处理，以面要素为例，如图2中的面要素缝隙所示。

首先，找出面A上与接边线距离在阈值范围内的点的集合Q={点a，点b}，同理，面B的点集合为W={点 c，点 d}。

其次，针对点集Q和W中的点元素进行匹配，如点a和点c分属点集Q和W，并且点a和点c之间的距离在阈值范围内，则匹配成功。

最后，对匹配成功的点对，用平均法进行处理，之后进行要素合并。

3 自动接边的逻辑思维

自动接边算法实质为确定其逻辑顺序的过程，而自动接边的逻辑思维大体可分为两类，一是循环逻辑思维，一是阶段性逻辑思维。

3.1 循环逻辑思维

循环逻辑思维是抽出具有共性的过程作为基本单元，循环基本单元，直到满足临界条件为止。现有的自动接边算法大多采用循环逻辑思维，如图3所示，设线要素1与线要素2接边为一个过程A，即为接边过程的基本单元。过程A通常包含“地物匹配”和“合并要素”两个步骤，通过这两个步骤可得到线要素1'，将线要素1'取代线要素1和2加入到选择集中，更新地物和选择集。重复过程A直到所有地物接边完成。

图3 循环逻辑思维

3.2 阶段性逻辑思维

阶段性逻辑思维是将过程分成各个阶段，每个阶段完成后才进行下一阶段的操作。本文从实际应用出发，采用了这种逻辑思维方式进行自动接边算法设计。利用关系探测聚类的方法，将自动接边过程分成“地物聚类”和“合并地物”两个阶段。

地物聚类是将接边线两侧需要接边的图形要素聚集成n个子类，如图4所示，线段1、线段2和线段3为一个子类;线段4和线段5为另一个子类。

合并地物是依据地物聚类后的结果，利用ArcGIS Engine组件中 ITopologicalOperator接口的ConstructU-nion方法分别对各个子类中的图形要素进行合并操作，得到接边后的结果。

图4 顺序逻辑思维

3.3 两种逻辑思维的比较

在自动接边算法上，阶段性逻辑思维与循环逻辑思维相比，具有两种优势。

第一，在同一图层数据的接边中，“地物匹配”和“合并要素”彻底分离开来，也即将接边检查和实际接边操作分离开来，接边检查只需进行地物聚类过程，提高了接边检查的速度。

第二，减少更新图形数据和数据选择集的次数，提高了算法的效率，而且选择集中的要素数量越多，算法效率提升得越明显。

4 基于关系探测聚类的自动接边算法设计

本文按照阶段性逻辑思维，融合空间聚类的思想，设计出基于关系探测聚类的自动接边算法，其算法具体步骤如图5所示。

4.1 算法流程

通过接边线建立接边要素的选择集，对选择集中的要素通过关系探测方法进行聚类，得到子类1，子类2，…，子类n，这其中，只有一个地理要素的子类属于接边错误，输出到错误报表。之后分别对需要接边的子类进行合并要素操作，得到接边完成的数据。

图5 自动接边算法流程

4.2 关系探测聚类

(1)关系聚类算法设计

本文中，空间对象的相似性可理解为空间对象之间的关系定义，这种关系定义决定了聚类的结果。基于此，本文提出了一种关系探测聚类方法。根据实际需要定义关系函数，依据关系函数初始化关系链，再通过探测各个关系链达到聚类目的。

算法步骤如下:

输入:几何要素集 δ={几何要素 a，b，c，d，e，……}

输出:几何要素子集 A，B，C，……

步1:根据实际要求，定义关系函数f(x，y)，f(x，y)表示几何要素x与y的关系。

步2:对几何要素集δ中每一个几何要素都产生一个关系集 S(a)，S(a)定义如下式子，S(a)={x|f(x，a)=1，x∈δ}，其中 a 为几何要素集 δ中任意一个几何要素。

步3:关系探测得到一个聚类结果——几何要素子集A。

搜索 S(a)，设 S(a)={x，y，z，……}，此时子集A为空集，所以几何要素 x，y，z，……都不属于子集A，则将几何要素 x，y，z，……加入到子集 A中，循环搜索对应于几何要素 x，y，z，……的关系集 S(x)，S(y)，S(z)，……。如果S(x)中存在几何要素α不属于子集A，则将几何要素α加入到几何要素集A中，更新子集A，接着搜索S(a)，搜索过程同S(a)。关系集S(x)(x∈δ)完成搜索的标志为——几何要素集A的个数不再增加。

步4:循环探测，得到所有聚类后的几何要素子集。

设几何要素b属于几何要素集δ，但几何要素b对应的关系集没有被探测，即不属于任何一个现有的几何要素子集A，B，C，……。用几何要素b代替步4中的几何要素a，重复步3，直到所有的几何要素的关系集都被探测，得到最后聚类的结果——几何要素子集A，B，C，……。

(2)定义自动接边的聚类关系函数

根据本文所提的地物匹配原则，具体定义关系函数 f(x，y)，如图6所示。