顾及居民地分布特征的建筑物分组合并算法研究

刘　洋，兰泽英，张　荣

(1. 广州市城市规划勘测设计研究院，广东 广州 510060； 2. 广东工业大学管理学院，广东 广州 510060)

Research on Algorithm of Building Group and Aggregation Considering

Residential Distribution Features

LIU Yang, LAN Zeying, ZHANG Rong



顾及居民地分布特征的建筑物分组合并算法研究

刘洋1，兰泽英2，张荣1

(1. 广州市城市规划勘测设计研究院，广东 广州 510060； 2. 广东工业大学管理学院，广东 广州 510060)

Research on Algorithm of Building Group and Aggregation Considering

Residential Distribution Features

LIU Yang, LAN Zeying, ZHANG Rong

摘要：建筑物多边形分组合并是城市大比例尺地图综合中的重要问题。本文在建筑物群的约束Delaunay三角网空间剖分模型及目标间“视觉距离”计算模型研究基础上，以广州地区3种具有典型分布特征的建筑物群分组合并操作为研究对象，并基于“分而治之”的思想，分别提出不同处理方法。设计的算子兼顾了适用性和效率，在广州地区序列比例尺空间数据库快速构建中得到了成功应用。

关键词：建筑物多边形分组合并；视觉距离；建筑物多边形邻近关系

一、引言

建筑物多边形综合是大中比例尺地图缩编的重要内容。与一般的水系、植被等自然地物不同，建筑物作为人造地物具有其特殊性[1-2]，如房屋多边形角为直角、分布在道路两侧的房屋呈阵列化对齐等，这对建筑物综合算子的适用性和效率提出了较高要求。

大比例尺地图综合中，建筑物多边形分组合并是一个重要问题[1]，取得了较多的研究成果。郭仁忠[1]认为邻近关系是建筑物多边形合并过程的重要依据，并针对拓扑邻近与视觉邻近两种空间关系，分别提出基于矢量拓扑结构的“剪枝扩展”算法和基于栅格结构的两垂直方向扫描填充算法。艾廷华[3]提出综合考虑目标间距离、方向和大小差异的“视觉距离”计算模型。钱海忠等[4]提出了把Agent技术与TIN技术、聚类技术相结合的算法(ABTM)。孟妮娜等[5]建立基于相同特征量的邻近关系相似性模型和基于等距离关系曲线的邻近关系相似性模型，对建筑物邻近关系相似性作定量化计算和判断。许文帅等[6]提出一种基于视觉邻近探测的缝合算法。以上研究成果在理论层面为建筑物多边形间的邻近关系判定和分组合并方法提供了有益借鉴，但对于大规模工程化应用中，设计顾及不同地域特征的建筑物分组合并算子无法面面俱到，而且此类应用中对算子的适用性和效率提出了更高要求。

为此，在借鉴已有的研究成果的基础上，本文以广州地区3种具有典型分布特征的建筑物群分组合并操作为研究对象，3种样本分别是城区规则排列建筑物群、城中村不规则排列建筑物群及郊区散列式建筑物群。本文基于“分而治之”的思想，分别提出不同的处理方法(具体算法见下文),本文设计的算子兼顾了适用性和效率，在广州地区序列比例尺空间数据库快速构建中得到了成功应用。

二、城区规则排列建筑物分组合并

文献[3]提出一种综合考虑距离、方向、大小等因素的“视觉距离”来衡量建筑物多边形间的邻近关系。其中，距离为建筑物多边形间的平均距离，是描述目标关系疏密的主导因素，方向差异和大小差异作为权值加载到平均距离上，从而综合衡量目标间的邻近关系。基于此思想，并考虑工程化应用的便利，本文提出综合采用建筑物多边形间邻接相关边长度和平均距离来衡量其视觉邻近关系。

1. 建筑物多边形间的邻接相关边长度计算

邻接相关边是基于建筑物群的约束Delaunay三角网空间剖分模型及邻接跨立三角形判定为基础来定义的[3]，它构成了建筑物目标间的“邻近通廊”，具体如下：

1) 采用Delaunay三角网建立建筑物群的空间剖分模型。为避免建筑物边界与三角形相交及三角形穿越道路，本文采用约束Delaunay三角网，参加三角网构建的点为建筑物边界及道路中心线上的端点和内插点，内插步长为相邻建筑物间的最小距离阈值。

2) 确定多边形间的邻接跨立三角形。剔除位于多边形内部或其凹部区域的三角形，仅保留跨立三角形(即两个节点在同一个要素上，另外一个节点在另一个要素上的三角形)。设跨立三角形位于同一要素上的边为底边，其他两边为腰，排除掉任意一条腰长度超过距离阈值的三角形，排除掉腰与底边形成的夹角中任意角度超过阈值θ(经验取值)的三角形，剩下的即为多边形间的邻接跨立三角形。

3) 计算多边形间的邻接相关边长度。多边形间所有邻接跨立三角形底边的集合即为多边形间的邻接相关边，其长度采用加权方式计算。设三角形的底边长度为l，底边中点到顶点距离为d，通过d与阈值D比值的加权取得有效相关边长度，计算公式为

f(l,d)=l(1-wd/D)

式中，w为权，取值范围为(0，1)，根据试验数据经验取值。累加两个多边形之间所有跨立三角形的有效边长度，得到两个多边形的邻近边长度。

2. 建筑物多边形间的平均距离计算

邻接跨立三角形集构成了多边形间的“邻近通廊”，基于经典算法[3]提取“邻近通廊”的骨架线，获取骨架线总长度L、邻接跨立三角形数量n、每个邻接跨立三角形的高hi及骨架线落在每个邻接跨立三角形的长度si，然后基于微积分思想加权累积得到两多边形间的平均距离

3. 建筑物分组合并

建筑物分组合并时，采用建筑多边形间平均距离、建筑多边形间邻接相关边长度及建筑分组面积3个指标作为控制指标。其中，距离控制建筑物分组资格，只有建筑物距离小于阈值时才能分为一组；邻接相关边长度控制分组决策过程，优先合并邻接相关边长度最长的两个建筑多边形；建筑分组面积控制分组停止条件，即综合的粒度，当分为一组的多边形总面积超过阈值(缩编后最小上图面积)时，此组多边形将丧失“活性”，不再参与合并。建筑物分组的具体过程如下：

1) 计算每个建筑物多边形的面积并排序，面积大于缩编后最小上图面积的多边形将丧失“活性”，不再参与分组操作，取面积最小的“活跃”多边形A作为当前目标。

2) 在Delaunay三角网建立的建筑物群的空间剖分模型中考察与A有邻接跨立三角形联系的建筑物多边形集U，获取与A平均距离在阈值以内的建筑物多边形集U′，取U′中与A邻接相关边长度最长的建筑物多边形B与之优先分为一组(当邻接相关边长度相同时，考虑平均距离较小的多边形)；分组后的多边形集将作为一个完整的大多边形参与面积计算、排序和分组操作。

3) 返回步骤1)。

4) 直至所有多边形均丧失“活性”，分组操作停止。

具体系统开发时，还应提供高效的人机交互工具，方便作业员对不合理的分组进行调整。调整完成后在保持建筑物直角化特征的情况下进行建筑物合并操作，最后删除面积小于上图面积的建筑物。

三、城中村不规则排列建筑物分组合并

广州市城中村建筑物群具有其独特的分布特征：建筑物分布杂乱，无统一的朝向及明显的分布模式，呈片团不规则聚集；存在大量“握手楼”，建筑物间距狭小，街道蜿蜒、宽度不一、存在较多断头路现象。若直接采用上节的算法，效果并不理想。在传统人工综合缩编时，对此类建筑物处理采用如下思路：根据城中村街道及建筑群分布间隙，生成较完整的区域路网，首先依据综合尺度对路网进行抽稀，保持区域的骨架结构，然后以道路为硬约束条件对建筑群进行分割，并设置较小的距离阈值对建筑物进行分组合并。基于此“先路网生成处理，后建筑物分组合并”的迂回策略，本文提出“四步走”的处理方法：

1) “背景”区域提取：首先基于约束Delaunay三角网建立城中村建筑物群的空间剖分模型，构建建筑物群的凸壳，用凸壳与建筑物区域作差运算来提取背景区域；

2) 构建道路网stroke模型[7]：包括生成道路中心线弧段、道路中心线弧段stroke连接及stroke分级3个部分。所谓stroke是指具有连通延展性的弧段分组。

a. 生成道路中心线弧段：采用“骨架线”提取算法生成背景区域的骨架线网络，对骨架线进行平滑、化简和数据预处理(断线连接，删除伪结点、悬挂线、短线等)，生成道路中心线弧段网络，借鉴建筑物平均距离的计算方法获取每个弧段的平均宽度，并计算其长度。

b. 道路中心线弧段stroke连接：即判断拓扑关联的弧段是否属于同一stroke的过程，一般综合考虑弧段间的方向一致性和语义一致性进行判断，本文采用的连接策略是以方向一致性判断为主，辅以街道名称来判断(若为无名路则不考虑语义一致性)。设道路中心线弧段ei和ej，它们可划分为同一stroke进行连接的条件是：ei和ej具有公共结点p，且ei和ej的方向夹角θij(取锐角)小于阈值δ(一般根据试验结果确定)。θij越小，ei和ej的连通延展性越好，θij=0时，两者方向完全一致。然后计算同一组弧段的平均宽度和总长度作为stroke的宽度和长度。

c. 道路中心线弧段stroke分级：为了简便，本文主要综合考虑stroke的宽度和长度对其进行分级，判定标准如下：若stroke宽度和长度均满足当前等级I阈值要求时，直接设定其等级为I；若宽度达不到阈值要求，则直接与下一等级比较；若宽度满足要求，长度不够时，则直接设定其等级为I-2。计算机自动分级后局部不合理之处需人工调整。

3) 顾及道路目标stroke特征保持的路网自动综合：本文采用文献[7]提出的综合算法，首先依据方根模型确定道路的选取比例，采用约束Delaunay三角网构建道路中心线弧段的邻近关系模型，然后按如下算法对路网进行迭代抽稀：①锁定高等级道路；②删除最短没有被锁定且删除后不影响连通性的道路R；③锁定R周围的道路；④如果达到选取比例则终止，否则到⑤；⑤如果所有道路都被锁定则解锁所有低等级道路，并跳至②。本算法不仅可兼顾个体目标重要性和保持路网密度分布特征，而且可以动态维护路网的连通性。

4) 建筑物分组合并：以综合的道路为硬约束条件，设置比城区其他区域较小的距离阈值，按第2节视觉邻近关系计算方法和分组策略对建筑群进行处理。

四、郊区散列式居民地分组合并

广州市郊区的散列式居民地主要有两种分布类型，一般位于花都、从化及增城等山区。一是沿道路、河流分布的散列式居民地，此类居民地合并与城区不同，合并多边形边界除了应尽量满足垂直相交、边界平直之外，还需要顾及与周围河流、道路的延展方向，并保持整体范围性的部分居民地。二是随机分布的散列式居民地，此类居民地综合大多采用基于群点重采样算法进行化简和选取。本文主要对第一种具有方向延展性分布特征的居民地分组合并操作进行研究。

首先采用经典的道格拉斯算法对道路河流中心线进行化简，并获取其拟合直线，该直线表示居民地分布的延展方向。在此基础上，居民地合并时除考虑目标间的距离、邻接相关边长度外，还应考虑目标间的方向。文献[3]采用方向差异权值Cd对目标间的邻接相关边长度进行修正。获取相邻多边形重心连线与道路或河流拟合直线间的夹角∂，∂的取值范围为[0,90°]，Cd取值范围为[1,2]，角度越大，Cd越大，即方向的不一致将导致目标间的疏远，分组合并算法的总体框架与第2节一致。

五、试验结果

本文在3个典型样本区域抽取了大量数据对以上设计的算子进行了应用试验，并不断调整确定各种关键参数。其中最小距离阈值和最小上图面积阈值根据相应尺度综合的制图规范确定，可根据广州市的特殊情况作适当调整。而建筑物邻接相关边长度计算及道路中心线弧段stroke连接中的关键参数确定见表1。试验后，本文设计的算子在广州地区序列比例尺空间数据库快速构建中得到了大规模工程化应用，在适用性和计算效率方面均取得较好效果。

效率方面，本文中建筑物分组时间复杂度为O(nlogn)，空间复杂度为O(n)；城中村道路中心线弧段stroke分级算法时间复杂度为O(n)，空间复杂度为O(1)；城中村道路综合算法时间复杂度为O(nlogn)，空间复杂度为O(n)。通过工日对比测算，本文采用的建筑物分组合并算法在效率上约为人工的6倍以上。适用性方面，从试验结果来看，本文设计的算法很好地顾及了目标重要性、目标间视觉邻近关系及保持目标群整体分布特征等多方面的要求。

表1　参数值

六、结束语

建筑物多边形分组合并是城市大比例尺地图综合中的重要问题。本文在建筑物群的约束Delaunay三角网空间剖分模型及目标间“视觉距离”计算模型研究基础上，以广州地区3种典型分布特征的建筑物群分组合并操作为研究对象，基于“分而治之”的思想，分别提出不同处理方法：对于城区规则排列建筑物群，考虑工程化应用的便利，提出综合采用建筑物多边形间邻接相关边长度和平均距离来衡量建筑物多边形间的视觉邻近关系，并设计分组算法采用平均距离、邻接相关边长度及建筑分组面积3个控制指标来决策建筑物分组的“活性”、优先级和综合粒度；对于城中村不规则排列建筑物群，采用“先路网生成处理，后建筑分组合并”的迂回策略，提出背景区域提取、构建路网stroke模型、顾及道路目标stroke特征保持的路网自动综合、建筑物分组合并的“四步走”处理方法；对于郊区具有方向延展性的建筑物群，提出采用方向差异权值对目标间邻接相关边长度进行修正的做法，将方向因子纳入视觉邻近关系计算中。本文设计的算子在适用性和计算效率方面均取得了较好效果。

参考文献：

[1]郭仁忠，艾廷华.制图综合中建筑物多边形的合并与化简[J].武汉测绘科技大学学报,2000,25(1):25-29.

[2]童小华,熊国锋.建筑物多边形的多尺度合并化简与平差处理[J].同济大学学报：自然科学版,2007,35(6):824-828.

[3]艾廷华, 郭仁忠.基于格式塔识别原则挖掘空间分布模式[J].测绘学报，2007，36(3)：302-308.

[4]钱海忠，武芳，谭笑，等.基于ABTM的城市建筑物合并算法[J].中国图象图形学报，2005，10(10):1224-1233.

[5]孟妮娜，艾廷华，周校东.建筑群邻近关系相似性计算[J].武汉大学学报：信息科学版，2012，37(7):775-778.

[6]许文帅，龙毅，周侗，等.面向复杂多边形合并的视觉邻近探测与缝合算法[J].地理与地理信息科学,2014,30(1):125-126.

作者简介：刘洋(1981—)，男，博士，高级工程师，研究方向为地理信息系统、3S集成技术。E-mail：liuyang_052@163.com

基金项目：国家自然科学基金青年科学基金(41301377)

收稿日期：2015-01-03

中图分类号：P208

文献标识码：B

文章编号：0494-0911(2015)12-0050-04

引文格式： 刘洋，兰泽英，张荣. 顾及居民地分布特征的建筑物分组合并算法研究[J].测绘通报，2015(12)：50-53.DOI:10.13474/j.cnki.11-2246.2015.376