顾及空间分布与注记相关性的点要素注记配置算法

doi:10.11947/j.AGCS.2022.20210247

摘要/Abstract

摘要： 点状要素注记自动配置问题是数据可视化研究的难点之一。稠密型点状要素注记之间往往存在着较大的相关性和冲突性，从而导致注记效率低下及配置结果不合理的问题。本文通过充分挖掘稠密型点状要素的空间分布特征和注记相关性，提出了一种顾及空间分布与注记相关性的点要素注记配置算法。首先，充分挖掘点要素的局部空间分布特征和注记间的相关性构建注记关联度模型；其次，利用基于注记关联度模型的空间聚类算法对其整体空间分布特征进行描述和分析，将单一数据集划分为若干个独立的子数据集，以消除整体求解中独立数据集产生的干扰性和模糊性；最后，利用点要素的局部空间分布特征和注记相关性构建基于增序注记关联度模型的注记次序规则，并采用多层次元启发算法求解注记配置的近似最优解。试验结果表明：在5%~40%注记密度下的点要素注记配置，新算法较传统元启发式算法的求解效率提高10.41%~28.92%，注记质量评价函数值下降5.5~35.9，有效提升了点要素注记配置的效率和质量。

关键词: 点要素注记配置, 注记关联度模型, 注记空间分布, 注记相关性, 元启发式算法

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

中图分类号:

P283
P208

曹闻, 彭斐琳, 童晓冲, 戴浩然, 张勇. 顾及空间分布与注记相关性的点要素注记配置算法[J]. 测绘学报, 2022, 51(2): 301-311.

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.

参考文献

[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.