An immune genetic algorithm to buildings displacement with constraint of safety zones

doi:10.11947/j.AGCS.2021.20200395

Abstract

Abstract: For the combinatorial optimization displacement algorithms based on heuristic search or swarm intelligence, it is a difficult problem to maintain the spatial relationship and distribution characteristics of map features. This article proposes an optimal algorithm to buildings displacement based on immune genetic algorithm (IGA) with the constraint of safety zones. In the study, the displacement problem of buildings is defined as a multi-objective optimization problem, and then the immune genetic algorithm is used to search the optimal solution. In order to keep the spatial relationship and globe spatial distribution characteristics of buildings as far as possible and avoid topology errors, Voronoi diagram and buffer areas are used to construct the displacement safety zone of each building to limit the displacement range of buildings; meanwhile, the strategy to shift the building group as a whole is used to keep local building patterns. Finally, the effectiveness of the improved algorithm is verified by taking the displacement of buildings in a block of beijing as an example. The results indicate that the algorithm can not only solve the proximity conflicts, but also keep the spatial relationship and spatial distribution characteristics of map objects.

Key words: map generalization, displacement, proximity conflict, immune genetic algorithm, buildings

CLC Number:

P208

LIU Yuangang, LI Shaohua, CAI Yongxiang, HE Zhenming, MA Xiaoya, LI Pengcheng, GUO Qingsheng, HE Zongyi. An immune genetic algorithm to buildings displacement with constraint of safety zones[J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(6): 812-822.

References

[1] 王家耀, 李志林, 武芳. 数字地图综合进展[M]. 北京: 科学出版社, 2011. WANG Jiayao, LI Zhilin, WU Fang. Advances in digital map generalization[M]. Beijing: Science Press, 2011.
[2] BADER M. Energy minimization methods for feature displacement in map generalization[D]. Switzerland: University of Zurich, 2001.
[3] 艾廷华. 基于场论分析的建筑物群的移位[J]. 测绘学报, 2004, 33(1): 89-94. AI Tinghua. A displacement of building cluster based on field analysis[J]. Acta Geodaetica et Cartographica Sinica, 2004, 33(1): 89-94.
[4] 吴小芳, 杜清运, 徐智勇. 多层次移位原则的道路与建筑物空间冲突处理[J]. 测绘学报, 2010, 39(6): 649-654. WU Xiaofang, DU Qingyun, XU Zhiyong. Disposal of spatial conflict between roads and buildings based on the multilevel displacement principles[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(6): 649-654.
[5] 孙雅庚. 建筑物群与道路空间冲突解决的移位方法研究[D]. 武汉: 武汉大学, 2015. SUN Yageng. The displacement method research of conflict solution relate to buildings and roads[D]. Wuhan: Wuhan University, 2015.
[6] 刘远刚. 基于能量最小化原理的地图要素移位算法研究与改进[D]. 武汉: 武汉大学, 2015. LIU Yuangang. Research and improvement of cartographic displacement algorithms based on energy minimization principles[D]. Wuhan: Wuhan University, 2015.
[7] BURGHARDT D, MEIER S. Cartographic displacement using the snakes concept[C]//FÖRSTNER W, PLVMER L. Semantic Modeling for the Acquisition of Topographic Information from Images and Maps. Basel: Birkhaeuser Verlag, 1997: 59-71.
[8] BOBRICH J. Cartographic displacement by minimization of spatial and geometric conflicts[C]//Proceedings of the 20th International Cartographic Conference. Beijing: [s.n.], 2001: 2032-2042.
[9] BURGHARDT D, MEIER S. Cartographic displacement using the snakes concept[C]//FÖRSTNER W, PLVMER L.Semantic Modeling for the Acquisition of Topographic Information from Images and Maps. Basel: Birkhaeuser Verlag, 1997: 114-120.
[10] HARRIE L E. The constraint method for solving spatial conflicts in cartographic generalization[J]. Cartography and Geographic Information Science, 1999, 26(1): 55-69.
[11] HØJHOLT P. Solving space conflicts in map generalization: using a finite element method[J]. Cartography and Geographic Information Science, 2000, 27(1): 65-74.
[12] WARE J M, JONES C B. Conflict reduction in map generalization using iterative improvement[J]. GeoInformatica, 1998, 2(4): 383-407.
[13] WARE J M, JONES C B, THOMAS N. Automated map generalization with multiple operators: a simulated annealing approach[J]. International Journal of Geographical Information Science, 2003, 17(8): 743-769.
[14] MACKANESS W A, PURVES R S. Automated displacement for large numbers of discrete map objects[J]. Algorithmica, 2001, 30(2): 302-311.
[15] LONERGAN M, JONES C B. An iterative displacement method for conflict resolution in map generalization[J]. Algorithmica, 2001, 30(2): 287-301.
[16] WARE J M, WILSON I D, WARE J A,et al. A tabu search approach to automated map generalisation[C]//Proceedings of the 10th ACM International Symposium on Advances in Geographic Information Systems. New York, NY:ACM, 2002: 101-106.
[17] WILSON I D, WARE J M, WARE J A. A genetic algorithm approach to cartographic map generalisation[J]. Computers in Industry, 2003, 52(3): 291-304.
[18] SUN Yageng, GUO Qingsheng, LIU Yuangang,et al. An immune genetic algorithm to buildings displacement in cartographic generalization[J]. Transactions in GIS, 2016, 20(4), 585-612.
[19] HUANG Hesheng, GUO Qingsheng, SUN Yageng, et al. Reducing building conflicts in map generalization with an improved PSO algorithm[J]. ISPRS International Journal of Geo-Information, 2017, 6(5): 127.
[20] LI Wende, AI Tinghua, SHEN Yilang, et al. A novel method for building displacement based on multipopulation genetic algorithm[J]. Applied Sciences, 2020, 10(23): 8441. DOI: 10.3390/app10238441.
[21] 陈占龙, 叶文. 复杂面实体拓扑关系的精细化模型[J]. 测绘学报, 2019, 48(5): 630-642. DOI: 10.11947/j.AGCS.2019.20170531. CHEN Zhanlong, YE Wen. The precise model of complex planar objects’ topological relations[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(5): 630-642. DOI: 10.11947/j.AGCS.2019.20170531.
[22] ZHANG Lihua, TANG Lulu, JIA Shuaidong, et al. A collaborative simplification method for multiple coastlines based on the hierarchical triangulation network partition[J]. Journal of Geodesy and Geoinformation Science, 2020, 3(2): 93-104. DOI: 10.11947/j.JGGS.2020.0210.
[23] AI Tinghua, ZHANG Xiang, ZHOU Qi, et al. A vector field model to handle the displacement of multiple conflicts in building generalization[J]. International Journal of Geographical Information Science, 2015, 29(8): 1310-1331. DOI: 10.1080/13658816.2015.1019886.
[24] LIU Yuangang, GUO Qingsheng, SUN Yageng, et al. A combined approach to cartographic displacement for buildings based on skeleton and improved elastic beam algorithm[J]. PLoS One, 2014, 9(12): e113953. DOI: 10.1371/journal.pone.0113953.
[25] CONS A. Constraint analysis(DA2)[R]. The Agent Project, Esprit/LTR/24 939, 2001.
[26] Swiss Society of Cartography. Topographic maps: map graphics and generalization[M]. Berne: Federal Office of Topography, 2005.
[27] 刘远刚, 郭庆胜, 蔡永香, 等. 基于CDT骨架线的地图目标邻近冲突识别[J]. 测绘工程, 2017, 26(8): 10-13, 19. LIU Yuangang, GUO Qingsheng, CAI Yongxiang, et al. Identifying proximity conflicts of map objects based on CDT skeleton[J]. Engineering of Surveying and Mapping, 2017, 26(8): 10-13, 19.
[28] 国家测绘局测绘标准化研究所. GB/T 20257.3—2006 国家基本比例尺地图图式第3部分: 1∶25000 1∶ 50000 1∶ 100000地形图图式[S]. 北京: 中国标准出版社, 2006. National Administration of Surveying, Mapping and Geoinformation of China. GB/T 20257.3—2006 Cartographic symbols for national fundamental scale maps—Part 3: Specifications for cartographic symbols 1∶25000 1∶50000 & 1∶100000 topographic maps[S]. Beijing: Standards Press of China, 2006.
[29] 郭庆胜, 李国贤, 王勇, 等. 直线排列建筑物群渐进式典型化方法[J]. 测绘学报, 2020, 49(10): 1354-1364. DOI: 10.11947/j.AGCS.2020.20190495. GUO Qingsheng, LI Guoxian, WANG Yong, et al. The method of progressive typification for building groups with straight linear patterns[J]. Acta Geodaetica et Cartographica Sinica, 2020, 49(10): 1354-1364. DOI: 10.11947/j.AGCS.2020.20190495.
[30] ZHANG Xiang, AI Tinghua, STOTER J, et al. Building pattern recognition in topographic data: examples on collinear and curvilinear alignments[J]. Geoinformatica, 2013, 17(1): 1-33.
[31] 王煦法, 张显俊, 曹先彬, 等. 一种基于免疫原理的遗传算法[J]. 小型微型计算机系统, 1999, 20(2): 117-120. WANG Xufa, ZHANG Xianjun, CAO Xianbin, et al. An improved genetic algorithm based on immune principle[J]. Mini-Micro Systems, 1999, 20(2): 117-120.