A point-feature label placement algorithm considering spatial distribution and label correlation

doi:10.11947/j.AGCS.2022.20210247

Abstract

Abstract: The problem of Point-Feature Label Placement is one of the difficulties in data visualization. Large correlation and overlap among the labels of dense point features lead to the low efficiency of labeling and unreasonable labeling results. Fully mining the local spatial distribution characteristics and label correlation of dense point features, this paper proposes an automatic point feature label placement algorithm considering spatial distribution and label correlation of point features. Firstly, we build a label association model by mining the spatial distribution characteristics of point features and the label correlation; Secondly, the spatial clustering algorithm based on label association model is used to describe and analyze its global spatial distribution characteristics, which divides a single dataset into several independent sub-datasets to eliminate the interference and ambiguity among independent datasets in the overall solution; Finally, the labeling order rules based on the ascending order of label association model are constructed by using the local spatial distribution characteristics of point feature and the label correlation, which is used to guide the solution of the approximate optimal solution of label placement in the multi-hierarchy metaheuristic algorithm. The experimental results show that:when the label density range from 5% to 40%, the efficiency of the new algorithm is improved by 10.41%~28.92%, and the label quality evaluation value has dropped by 5.5~35.9, which effectively improves efficiency and quality of label placement.

Key words: point-feature label placement, label association model, label spatial distribution, label correlation, metaheuristic algorithm

CLC Number:

P283
P208

CAO Wen, PENG Feilin, TONG Xiaochong, DAI Haoran, ZHANG Yong. A point-feature label placement algorithm considering spatial distribution and label correlation[J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(2): 301-311.

References

[1] QIN X, LUO Y, TANG N, et al. Making data visualization more efficient and effective:a survey[J]. The VLDB Journal, 2020, 29(1):93-117.
[2] CAO X, WANG M, LIU X. Application of big data visualization in urban planning[C]//Proceedings of IOP Conference Series Earth and Environmental Science, Xian:IOP Publishing Ltd, 2020, 440:042-066.
[3] 高俊. 地理空间数据的可视化[J]. 测绘工程, 2000, 9(3):1-7. GAO Jun. Visualization in geo-spatial data[J]. Engineering of Surveying And Mapping, 2000, 9(3):1-7.
[4] LI Zhilin, GAO Peichao, XU Zhu. Information theory of cartography:an information-theoretic framework for cartographic communication[J]. Journal of Geodesy and Geoinformation Science, 2021,4(1):1-16.
[5] LHUILLIER A, VAN GARDEREN M, WEISKOPF D. Density-based label placement[J]. The Visual Computer, 2019, 35(6-8):1041-1052.
[6] 胡冯伟,乔俊军,陈张健,等.改进的地图制图点注记配置探测信息模型[J].测绘学报,2021,50(1):132-141. DOI:10.11947/j.AGCS.2021.20200018. HU Fengwei, QIAO Junjun, CHEN Zhangjian, et al. An improved detecting Information model of point annotation labelling in cartography[J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(1):132-141. DOI:10.11947/j.AGCS.2021.20200018.
[7] 王昭,吴中恒,费立凡,等.基于几何信息熵的面状要素注记配置[J].测绘学报,2015,38(2):183-188. WANG Zhao, WU Zhongheng, FEI Lifan, et al. Automatic name placement of area feature:a metric information approach[J]. Acta Geodaetica et Cartographica Sinica, 2015, 38(2):183-188.
[8] WU C, DING Y, ZHOU X, et al. A grid algorithm suitable for line and area feature label placement[J]. Environmental Earth Sciences, 2016, 75(20):1368. DOI:10.1007/s12665-016-6190-4.
[9] 周鑫鑫,吴长彬,孙在宏,等.小规模地理场景中点要素三维注记优化配置算法[J]. 测绘学报, 2016, 45(12):1476-1484. ZHOU Xinxin, WU Changbin, SUN Zaihong, et al. A 3D annotation optimal placement algorithm for the point features in the small scale geographic scene[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(12):1476-1484.
[10] CHRISTENSEN J, MARKS J, SHIEBER S. An empirical study of algorithms for point-feature label placement[J]. ACM Transactions Graphics,1995,14(3):203-232.
[11] OSMAN I H, KELLY J P. Meta-Heuristics theory and applications[J]. Journal of the Operational Research Society, 1997, 48(6):657-658.
[12] YAMAMOTO M, CAMARA G, LORENA L A N. Tabu search Heuristic for point-feature cartographic label placement[J]. GeoInformatica, 2002, 6(1):77-90.
[13] LI L, ZHANG H, ZHU H, et al. A labeling model based on the region of movability for point-feature label placement[J]. International Journal of Geo-Information, 2016, 5(9):159. DOI:10.3390/ijgi5090159.
[14] ARAÚJO E J, CHAVES A A, LORENA L A N. Improving the Clustering Search:An application to cartographic labeling[J]. Applied Soft Computing Journal, 2019, 77:261-273. DOI:10.1016/j.asoc.2018.11.003.
[15] 彭珊鸰,宋鹰,吴凡.基于蚁群算法的点状注记智能化配置[J].测绘科学,2007, 32(5):80-81,203. PENG Shanling, SONG Ying, WU Fan. The research of intelligent point-feature cartographic label placement base on ant colony algorithm[J]. Science of Surveying and Mapping, 2007, 32(5):80-81,203.
[16] RIBEIRO G M, LORENA L A N. Lagrangean relaxation with clusters for point-feature cartographic label placement problems[J]. Computers & Operations Research, 2008, 35(7):2129-2140.
[17] MAURI G R, RIBEIRO G M, LORENA L A N. A new mathematical model and a Lagrangean decomposition for the point-feature cartographic label placement problem[J]. Computers & Operations Research, 2010, 37(12):2164-2172.
[18] 郭庆胜,王涛.稠密型点状地图要素注记自动配置的智能化渐进式方法[J]. 武汉测绘科技大学学报, 2000(4):362-367. GUO Qingsheng, WANG Tao. Intelligently progressive model for dense point feature label placement[J]. Journal of Wuhan Technical University of Surveying and Mapping, 2000(4):362-367.
[19] 周鑫鑫,孙在宏,吴长彬, 等. 地图点要素注记自动配置中聚类分组的蚁群算法应用[J]. 地球信息科学学报, 2015, 17(8):902-908. ZHOU Xinxin, SUN Zaihong, WU Changbin, et al. Automatic label placement of point feature:using ant colony algorithm based on group clustering[J]. Journal of Geo-Information Science, 2015, 17(8):902-908.
[20] 罗广祥,徐斌.基于Voronoi图的点状要素注记自动配置[J].长安大学学报(地球科学版), 2003(2):63-65,69. LUO Guangxiang, Xu Bin. The study on automatic name placement around point features based on voronoi[J]. Journal of Chan'an University(Earth Science Edition), 2003(2):63-65,69.
[21] 李霖,张航,朱海红,等. 基于可移动区域的点状要素注记配置[J]. 武汉大学学报(信息科学版), 2018, 43(8):1129-1137. LI Lin, ZHANG Hang, ZHU Haihong, et al. A point-feature labeling algorithm based on movable regions[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8):1129-1137.
[22] KLAU G W, MUTZEL P. Optimal labeling of point features in rectangular labeling models[J]. Mathematical Programming, 2003, 94(2-3):435-458.
[23] STRIJK T, VAN KREVELD M. Practical extensions of point labeling in the slider model[J]. GeoInformatica, 2002, 6(2):181-197.
[24] VAN DIJK S, VAN KREVELD M, STRIJK T, et al. Towards an evaluation of quality for names placement methods[J]. International Journal of Geographical Information Science, 2002, 16(7):641-661.
[25] 樊红,张祖勋,杜道生. 地图注记质量评价模型的研究[J]. 测绘学报, 2004(4):362-366. FAN Hong, ZHANG Zuxun, DU Daosheng. The study of evaluation model for map labeling[J]. Acta Geodaetica et Cartogtoraphica Sinica, 2004(4):362-366.
[26] QI J, TAO Y, CHANG Y, et al. Packing R-trees with space-filling curves:theoretical optimality, empirical efficiency, and bulk-loading parallelizability[J]. ACM Transactions on Database Systems, 2020, 45(3):14. DOI:10.1145/3397506.
[27] TONG X, CHENG C, WANG R, et al. An efficient integer coding index algorithm for multi-scale time information management[J]. Data & Knowledge Engineering, 2019, 119(JAN.):123-138. DOI:10.1016/j.datak.2019.01.003.
[28] 杨涛.基于粒子群退火的高密度目标注记配置[J]. 电子设计工程, 2020, 28(15):182-187,193. YANG Tao. PSO-SA based on annotation configuration for highly dense targets[J]. Electronic Design Engineering, 2020, 28(15):182-187,193.