﻿ 建筑物合并的Delaunay三角网分类过滤法
 文章快速检索 高级检索

1. 山东科技大学测绘科学与工程学院， 山东 青岛 266590
2. 中国测绘科学研究院GIS所， 北京 100830

Classification and Filtering of Constrained Delaunay Triangulation for Automated Building Aggregation
GUO Peipei1,2, LI Chengming2, YIN Yong2
1. College of Geomatics, Shandong University of Science and Technology, Qingdao 266590, China ;
2. Institute of GIS, Chinese Academy of Surveying and Mapping, Beijing 100830, China
Foundation support: Project Supported by the National Key Technology Research and Development Program of the Ministry of Science and Technology of China (No.2015BAJ06B01); Project Supported by Special Scientific Research Fund of Public Welfare Profession on Surveying, Mapping and Geo-Information(No. 201412003); Basic Research Support Project of China Academy of Surveying and Mapping (No.7771530)
First author: GUO Peipei(1986-), female, PhD candidate, majors in automated map generalization and data mining.E-mail:guopeipei925@163.com
Abstract: Building aggregation is an important part of research on large scale map generalization. A triangulation based approach is proposed from the perspective of shape features, six measure parameters of triangles in a constrained Delaunay triangulation are proposed. First of all, use the six measure parameters to determine which triangles are retained and which are erased. Then, the contours of retained triangles, as bridge areas between buildings, are automatically identified and right angle processed. And then, the buildings are aggregated with right angle feature retained by merging the bridge areas with connecting buildings. Finally, the approach is verified by being carried out on actual data. Experimental result shows that it is efficient and practical.
Key words: map generalization     building aggregation     constrained Delaunay triangulation     rectangularity

1 合并原理 1.1 建筑物合并

 图 1 建筑物合并 Fig. 1 Building aggregation

1.2 C-Delaunay三角网

Delaunay三角网是对空间的一种特殊剖分，具备多种优异特性：如邻近性、最优性、区域性、凸多边形性等。C-Delaunay是在构建三角网的过程中，要求指定的边必须作为三角形的边存在，不能够被穿越。由于实际生产中的线、面数据也隐含着边界不被穿越的要求，使用C-Delaunay三角网对空间的划分更加理想，在实际生产活动中的应用也更广泛[14]图 2(a)(b)分别是用建筑物构建的Delaunay三角网和C-Delaunay三角网，后者保留了建筑物的边线信息更合理。

 图 2 建筑物构建的三角网 Fig. 2 Triangulation built with buildings

1.3 基于C-Delaunay的建筑物合并

1.3.1 位置特征

1.3.2 属性特征

1.3.3 关联特征

1.3.4 高度特征

1.3.5 角度特征

1.3.6 边长特征

2 合并方法 2.1 合并过程

 图 3 建筑物合并流程 Fig. 3 Blueprint for building aggregation

2.2 合并方法

2.2.1 加密数据，建立C-Delaunay三角网

(1) 确定加密阈值，对建筑物数据进行加密。借助三角网进行建筑物面的合并时，三角网是探测建筑物面邻近关系以及进行连接的关键所在。为了使三角形保持良好的几何形态，加密建筑物面的边线是非常重要的一步。加密阈值的选择需要综合考虑建筑物之间的距离和目标比例尺的大小。阈值过小会造成加密点冗余，降低处理效率。阈值过大不能保证三角网的良好形态。假设加密阈值为L，要加密线的长度为l，本文设计的加密算法如图 4所示。

 图 4 边线数据加密算法流程 Fig. 4 Densification algorithm flow chart

(2) 建立约束Delaunay三角网。使用加密后的点集，以建筑物边为限制边条件，建立约束Delaunay三角网的方法已经有很多研究，这里不再赘述。

2.2.2 根据6种度量参数对三角形进行过滤操作

(1) 位置特征过滤。排除建筑物面内的三角形，保留面外的。

(2) 属性特征过滤。排除3边均不是或只有一条是建筑物边的Ⅰ类三角形，保留Ⅱ类三角形，预留两边是建筑物边的Ⅰ类三角形和Ⅲ类三角形以备修复。

(3) 边长特征过滤。排除平均边长大于阈值的三角形，保留平均边长小于阈值的三角形。

(4) 角度特征过滤。保留钝角对边是建筑物边的钝角三角形，预留其余的钝角三角形以备修复；保留包含建筑物边界边的锐角三角形，预留不含边界边的锐角Ⅱ类三角形以备修复。

(5) 修复预留的钝角三角形。当钝角三角形存在两条非建筑物边，且他们关联的三角形处于保留状态时，把该三角形放回保留集。

(6) 高度特征过滤。对保留集中的三角形聚类，计算每一个三角形分组的平均高度，排除大于阈值的三角形集合，保留小于阈值的三角形集合。

(7) 修复预留的Ⅰ、Ⅱ、Ⅲ类三角形。考量预留Ⅱ、Ⅲ类三角形标记状态下的关联特征，若属于B类三角形则放回保留集。考虑预留的Ⅰ类三角形的非建筑物边是否关联了保留状态的三角形，若是则放回保留集。

 图 5 特殊特征的三角形 Fig. 5 Special triangles

2.2.3 自动提取、直角化桥接多边形

 图 6 直角化处理 Fig. 6 Rectangularity of bridge polygon

2.2.4 合并桥接部分和建筑物

3 试验与分析

3.1 试验平台和数据

3.2 结果分析

 图 7 合并效果对比图 Fig. 7 Comparison chart

 试验序号 数据范围/km2 原始比例尺 目标比例尺 运行时间 备注 1 6 1:500 1:5 000 15.37 s 自动合并 2 6 1:500 1:10 000 20.08 s 自动合并 3 36 1:500 1:5 000 200.27 s 自动合并 4 36 1:500 1:10 000 241.22 s 自动合并 5 651 1:2000 1:5 000 4.5 h 自动综合 6 651 1:2000 1:10 000 7.5 h 自动综合

4 结 论

﻿

 [1] 王光霞, 杨培. 数学形态学在居民地街区合并中的应用[J]. 测绘学院学报 , 2000, 17 (3) : 201–206. WANG Guangxia, YANG Pei. Application of Mathematic Morphology in Uniting Blocks of Residential Area[J]. Journal of Institute of Surveying and Mapping , 2000, 17 (3) : 201 –206. [2] 王辉连, 武芳, 张琳琳, 等. 数学形态学和模式识别在建筑物多边形化简中的应用[J]. 测绘学报 , 2005, 34 (3) : 269–276. WANG Huilian, WU Fang, ZHANG Linlin, et al. The Application of Mathematical Morphology and Pattern Recognition to Building Polygon Simplification[J]. Acta Geodaetica et Cartographica Sinica , 2005, 34 (3) : 269 –276. [3] 郭仁忠, 艾廷华. 制图综合中建筑物多边形的合并与化简[J]. 武汉测绘科技大学学报 , 2000, 25 (1) : 25–30. GUO Renzhong, AI Tinghua. Simplification and Aggregation of Building Polygon in Automatic Map Generalization[J]. Journal of Wuhan Technical University of Surveying and Mapping , 2000, 25 (1) : 25 –30. [4] 郭建忠, 谢明霞, 李柱林. 基于线缓冲区分析的街区合并方法[J]. 地理与地理信息科学 , 2011, 27 (6) : 111–112. GUO Jianzhong, XIE Mingxia, LI Zhulin. Block Aggregation Based on Line Buffer Analysis[J]. Geography and Geo-Information Science , 2011, 27 (6) : 111 –112. [5] 何宇兵.地学制图综合中多边形对象的合并算法研究与应用[D].杭州:浙江大学, 2007. HE Yubing.Study and Application of Algorithm for Polygon Aggregation in Geo-Cartographic Generalization[D].Hangzhou:Zhejiang University, 2007. [6] 齐琳.D-TIN并行构建方法及其在地图综合中的应用研究[D].南京:南京师范大学, 2011. QI Lin.Delaunay Triangulation Parallel Construction Method and Its Application in Map Generalization[D].Nanjing:Nanjing Normal University, 2011. http://cdmd.cnki.com.cn/article/cdmd-10319-1011248229.htm [7] 张巧凤.应用Delaunay三角网进行城市居民地和路网自动综合理论和方法研究[D].太原:太原理工大学, 2005. ZHANG Qiaofeng.The Method and Theory Research on Automated Map Generalization of City Settlement and Road Network Applying Delaunay Triangulation Network[D].Taiyuan:Taiyuan University of Technology, 2005. http://cdmd.cnki.com.cn/article/cdmd-10112-2005148447.htm [8] REGNAULD N.Spatial Structures to Support Automatic Generalisation[C]//Proceedings of the 22nd International Cartographic Conference.A Coruña:[s.n.], 2005. [9] 艾廷华. Delaunay三角网支持下的空间场表达[J]. 测绘学报 , 2006, 35 (1) : 71–76. AI Tinghua. A Spatial Field Representation Model Based on Delaunay Triangulation[J]. Acta Geodaetica et Cartographica Sinica , 2006, 35 (1) : 71 –76. [10] 艾廷华, 郭仁忠. 支持地图综合的面状目标约束Delaunay三角网剖分[J]. 武汉测绘科技大学学报 , 2000, 25 (1) : 35–41. AI Tinghua, GUO Renzhong. A Constrained Delaunay Partitioning of Areal Objects to Support Map Generalization[J]. Journal of Wuhan Technical University of Surveying and Mapping , 2000, 25 (1) : 35 –41. [11] 艾廷华, 郭仁忠, 陈晓东. Delaunay三角网支持下的多边形化简与合并[J]. 中国图象图形学报 , 2001, 6 (7) : 703–709. AI Tinghua, GUO Renzhong, CHEN Xiaodong. Simplification and Aggregation of Polygon Object Supported by Delaunay Triangulation Structure[J]. Journal of Image and Graphics , 2001, 6 (7) : 703 –709. [12] JONES C B, WARE J M. Proximity Search with a Triangulated Spatial Model[J]. The Computer Journal , 1998, 41 (2) : 71 –83. DOI:10.1093/comjnl/41.2.71 [13] JONES C B, WARE J M, EYNON C D. Triangulated Spatial Models and Neighbourhood Search:An Experimental Comparison with Quadtrees[J]. The Visual Computer , 1999, 15 (5) : 235 –248. DOI:10.1007/s003710050175 [14] 童小华, 熊国锋. 建筑物多边形的多尺度合并化简与平差处理[J]. 同济大学学报(自然科学版) , 2007, 35 (6) : 824–829. TONG Xiaohua, XIONG Guofeng. Aggregation, Simplification and Adjustment of Building Polygon Objects in Multi-scale Map Generalization[J]. Journal of Tongji University (Natural Science) , 2007, 35 (6) : 824 –829. [15] 黄继风. 基于Delaunay三角网的城市多边形合并算法[J]. 计算机工程与设计 , 2004, 25 (7) : 1220–1222. HUANG Jifeng. Urban Polygon Aggregation Algorithms Based on Delaunay Trigonometry Network[J]. Computer Engineering and Design , 2004, 25 (7) : 1220 –1222. [16] LI Z, YAN H, AI T, et al. Automated Building Generalization Based on Urban Morphology and Gestalt Theory[J]. International Journal of Geographical Information Science , 2004, 18 (5) : 513 –534. DOI:10.1080/13658810410001702021 [17] YAN Haowen, WEIBEL R, YANG Bisheng. A Multi-parameter Approach to Automated Building Grouping and Generalization[J]. Geoinformatica , 2008, 12 (1) : 73 –89. DOI:10.1007/s10707-007-0020-5 [18] 钱海忠, 武芳, 谭笑, 等. 基于ABTM的城市建筑物合并算法[J]. 中国图象图形学报 , 2005, 10 (10) : 1224–1233. QIAN Haizhong, WU Fang, TAN Xiao, et al. The Algorithm for Merging City Buildings Based on ABTM[J]. Journal of Image and Graphics , 2005, 10 (10) : 1224 –1233. [19] 邵春丽, 胡鹏, 黄承义, 等. DELAUNAY三角网的算法详述及其应用发展前景[J]. 测绘科学 , 2004, 29 (6) : 68–71. SHAO Chunli, HU Peng, HUANG Chengyi. The Expatiation of Delaunay Algorithms and a Promising Direction in Application[J]. Science of Surveying and Mapping , 2004, 29 (6) : 68 –71. [20] 刘鹏程, 艾廷华, 邓吉芳. 基于最小二乘的建筑物多边形的化简与直角化[J]. 中国矿业大学学报 , 2008, 37 (5) : 699–704. LIU Pengcheng, AI Tinghua, DENG Jifang. Simplification and Rectangularity of Building-polygon Based on Least Squares Adjustment[J]. Journal of China University of Mining & Technology , 2008, 37 (5) : 699 –704. [21] 刘鹏程, 艾廷华, 胡晋山. 一种基于条件极值的建筑多边形直角化的方法[J]. 测绘与空间地理信息 , 2008, 31 (5) : 12–14. LIU Pengcheng, AI Tinghua, HU Jinshan. Rectangularity of Building Polygon Based on Condition-Extremum[J]. Geomatics & Spatial Information Technology , 2008, 31 (5) : 12 –14. [22] BADER M, WEIBEL R.Detecting and Resolving Size and Proximity Conflicts in the Generalization of Polygonal Maps[C]//Proceedings of the 18th International Cartographic Conference.Stockholm:[s.n.], 1997.
http://dx.doi.org/10.11947/j.AGCS.2016.20150587

0

#### 文章信息

GUO Peipei, LI Chengming, YIN Yong

Classification and Filtering of Constrained Delaunay Triangulation for Automated Building Aggregation

Acta Geodaetica et Cartographica Sinica, 2016, 45(8): 1001-1007
http://dx.doi.org/10.11947/j.AGCS.2016.20150587