A point-feature label placement algorithm based on spatial data mining

Wen Cao; Jiaqi Xu; Feilin Peng; Xiaochong Tong; Xinyi Wang; Siqi Zhao; Wenhao Liu; Wen Cao; Jiaqi Xu; Feilin Peng; Xiaochong Tong; Xinyi Wang; Siqi Zhao; Wenhao Liu

doi:10.3934/mbe.2023542

Mathematical Biosciences and Engineering

2023, Volume 20, Issue 7: 12169-12193. doi: 10.3934/mbe.2023542

Previous Article Next Article

Research article

A point-feature label placement algorithm based on spatial data mining

1.
School of Geoscience and Technology, Zhengzhou University, Zhengzhou 450001, China
2.
Zhongke Yungu Technology, Changsha 201306, China
3.
School of Geospatial Information, University of Information Engineering, Zhengzhou 450001, China
4.
College of Resources and Environment, University of Chinese Academy of Sciences, Beijing 100101, China

Academic Editor: João M. C. Sousa

Received: 07 February 2023 Revised: 30 April 2023 Accepted: 30 April 2023 Published: 16 May 2023

The point-feature label placement (PFLP) refers to the process of positioning labels near point features on a map while adhering to specific rules and guidelines, finally obtaining clear, aesthetically pleasing, and conflict-free maps. While various approaches have been suggested for automated point feature placement on maps, few studies have fully considered the spatial distribution characteristics and label correlations of point datasets, resulting in poor label quality in the process of solving the label placement of dense and complex point datasets. In this paper, we propose a point-feature label placement algorithm based on spatial data mining that analyzes the local spatial distribution characteristics and label correlations of point features. The algorithm quantifies the interference among point features by designing a label frequent pattern framework (LFPF) and constructs an ascending label ordering method based on the pattern to reduce interference. Besides, three classical metaheuristic algorithms (simulated annealing algorithm, genetic algorithm, and ant colony algorithm) are applied to the PFLP in combination with the framework to verify the validity of this framework. Additionally, a bit-based grid spatial index is proposed to reduce cache memory and consumption time in conflict detection. The performance of the experiments is tested with 4000, 10000, and 20000 points of POI data obtained randomly under various label densities. The results of these experiments showed that: (1) the proposed method outperformed both the original algorithm and recent literature, with label quality improvements ranging from 3 to 6.7 and from 0.1 to 2.6, respectively. (2) The label efficiency was improved by 58.2% compared with the traditional grid index.
- metaheuristics,
- point-feature label placement,
- data mining,
- spatial distribution characteristics,
- label correlation
Citation: Wen Cao, Jiaqi Xu, Feilin Peng, Xiaochong Tong, Xinyi Wang, Siqi Zhao, Wenhao Liu. A point-feature label placement algorithm based on spatial data mining[J]. Mathematical Biosciences and Engineering, 2023, 20(7): 12169-12193. doi: 10.3934/mbe.2023542

Related Papers:

Abstract

The point-feature label placement (PFLP) refers to the process of positioning labels near point features on a map while adhering to specific rules and guidelines, finally obtaining clear, aesthetically pleasing, and conflict-free maps. While various approaches have been suggested for automated point feature placement on maps, few studies have fully considered the spatial distribution characteristics and label correlations of point datasets, resulting in poor label quality in the process of solving the label placement of dense and complex point datasets. In this paper, we propose a point-feature label placement algorithm based on spatial data mining that analyzes the local spatial distribution characteristics and label correlations of point features. The algorithm quantifies the interference among point features by designing a label frequent pattern framework (LFPF) and constructs an ascending label ordering method based on the pattern to reduce interference. Besides, three classical metaheuristic algorithms (simulated annealing algorithm, genetic algorithm, and ant colony algorithm) are applied to the PFLP in combination with the framework to verify the validity of this framework. Additionally, a bit-based grid spatial index is proposed to reduce cache memory and consumption time in conflict detection. The performance of the experiments is tested with 4000, 10000, and 20000 points of POI data obtained randomly under various label densities. The results of these experiments showed that: (1) the proposed method outperformed both the original algorithm and recent literature, with label quality improvements ranging from 3 to 6.7 and from 0.1 to 2.6, respectively. (2) The label efficiency was improved by 58.2% compared with the traditional grid index.

References

[1]	X. Qin, Y. Luo, N. Tang, G. Li, Making data visualization more efficient and effective: A survey, VLDB. J., 29 (2020), 93–117. https://doi.org/10.1007/s00778-019-00588-3 doi: 10.1007/s00778-019-00588-3
[2]	M. Aparicio, C. J. Costa, Data visualization, Commun. Design Quart. Rev., 3 (2015), 7–11. https://doi.org/10.1145/2721882.2721883 doi: 10.1145/2721882.2721883
[3]	S. Elwood, Geographic Information Science: Visualization, visual methods, and the geoweb, Prog. Hum. Geogr., 34 (2011), 401–408. https://doi.org/10.1177/0309132510374250 doi: 10.1177/0309132510374250
[4]	A. C. Robinson, U. Demšar, A B. Moore, A. Buckley, B. Jiang, K Field, et al. Geospatial big data and cartography: Research challenges and opportunities for making maps that matter, Int. J. Cartogr., 3 (2017), 32–60. https://doi.org/10.1080/23729333.2016.1278151 doi: 10.1080/23729333.2016.1278151
[5]	A. Lhuillier, M. V. Garderen, D. Weiskopf, Density-based label placement, Vis. Comput., 35 (2019), 1041–1052. https://doi.org/10.1007/s00371-019-01686-7 doi: 10.1007/s00371-019-01686-7
[6]	J. She, J. Liu, C. Li, J. Li, Q. Wei, A line-feature label placement algorithm for interactive 3D map, Comput. Graph-UK., 67 (2017), 86–94. https://doi.org/10.1016/j.cag.2017.06.002 doi: 10.1016/j.cag.2017.06.002
[7]	Y. Li, M. Sakamoto, T. Shinohara, T. Satoh, Automatic label placement of area-features using deep learning, Int. Arch. Photogr. Remote Sensing Spat. Inform. Sci., 43 (2020), 117–122. https://doi.org/10.5194/isprs-archives-XLIII-B4-2020-117-2020 doi: 10.5194/isprs-archives-XLIII-B4-2020-117-2020
[8]	J. She, X. Li, J. Liu, Y. Chen, J. Tan, G. Wu, A building label placement method for 3D visualizations based on candidate label evaluation and selection, Int. J. Geogr. Inf. Sci., 119 (2019), 123–138. https://doi.org/10.1080/13658816.2019.1606431 doi: 10.1080/13658816.2019.1606431
[9]	J. Christensen, J. Marks, S. Shieber, An Empirical Study of Algorithms For Point-Feature Label Placement, ACM Transactionson Graphic, 14 (1995), 203–232. https://doi.org/10.1145/212332.212334 doi: 10.1145/212332.212334
[10]	I. H. Osman, J. P. Kelly, Meta-Heuristics Theory and Applications, J. Oper. Res. Soc., 48 (1997), 657–657. https://doi.org/10.1007/978-1-4613-1361-8 doi: 10.1057/palgrave.jors.2600781
[11]	M. Yamamoto, G. Camara, L. A. N. Lorena, Tabu search heuristic for point-feature cartographic label placement, GeoInformation, 6 (2002), 77–90. https://doi.org/10.1023/A:1013720231747 doi: 10.1023/A:1013720231747
[12]	S. Zoraster, Practical results using simulated annealing for point feature label placement, Cartogr. Geogr. Inf. Sci., 24 (1997), 228–238. https://doi.org/10.1559/152304097782439259 doi: 10.1559/152304097782439259
[13]	S. P. Gomes, L. A. N. Lorena, G. M. Ribeiro, A constructive genetic algorithm for discrete dispersion on point feature cartographic label placement problems, Geogr. Anal., 48 (2016), 43–58. https://doi.org/10.1111/gean.12082 doi: 10.1111/gean.12082
[14]	S. Peng, Y. Song, F. Wu, The research of intelligent point-feature cartographic label placement base on ant colony algorithm, Sci. Survey. Map., 32 (2007), 80–81, https://doi.org/10.3771/j.issn.1009-2307.2007.05.029 doi: 10.3771/j.issn.1009-2307.2007.05.029
[15]	G. L. Cravo, G. M. Ribeiro, L. A. N. Lorena, A greedy randomized adaptive search procedure for the point-feature cartographic label placement, Comput. Geosci., 34 (2008), 373–386. https://doi.org/10.1016/j.cageo.2007.01.007 doi: 10.1016/j.cageo.2007.01.007
[16]	R. L. Rabello, G. R. Mauri, G. M. Ribeiro, L. A. N. Lorena, A clustering search metaheuristic for the point-feature cartographic label placement problem, Eur. J. Oper. Res., 234 (2014), 802–808. https://doi.org/10.1016/j.ejor.2013.10.021 doi: 10.1016/j.ejor.2013.10.021
[17]	E. J. Araújo, A. A. Chaves, L. A. N. Lorena, Improving the Clustering Search: An application to cartographic labeling, Appl. Soft. Comput., 77 (2019), 261–273. https://doi.org/10.1016/j.asoc.2018.11.003 doi: 10.1016/j.asoc.2018.11.003
[18]	Y. Ding, N. Jiang, C. Wu, X. Zhou, A two-phase algorithm for point-feature cartographic label placement, Earth. Sci. Inform., 11 (2018), 183–203. https://doi.org/10.1007/s12145-017-0320-8 doi: 10.1007/s12145-017-0320-8
[19]	J. Li, Q. Dong, a genetic taboo search algorithm for point-feature label placement considering the constrain of network, Bull. Survey. Map., 2 (2019), 80–85. https://doi.org/10.13474/j.cnki.11-2246.2019.0048 doi: 10.13474/j.cnki.11-2246.2019.0048
[20]	F. Lu, J. Deng, S. Li, H. Deng, A hybrid of differential evolution and genetic algorithm for the Multiple Geographical Feature Label Placement Problem, ISPRS Int. J. Geo-Inf., 8 (2019), 237. https://doi.org/10.3390/IJGI8050237 doi: 10.3390/ijgi8050237
[21]	J. Deng, Z. Guo, M. N. Lessani, Multiple geographical feature label placement based on multiple candidate positions in two degrees of freedom space, IEEE Access, 9 (2021), 144085–144105. https://doi.org/10.1109/ACCESS.2021.3120289 doi: 10.1109/ACCESS.2021.3120289
[22]	A. C. F. Alvim, E. D. Taillard, POPMUSIC for the point feature label placement problem, Eur. J. Oper. Res., 192 (2009), 396–413. https://doi.org/10.1016/j.ejor.2007.10.002 doi: 10.1016/j.ejor.2007.10.002
[23]	X. Zhou, Z. Sun, C. Wu, Y. Ding, Automatic Label Placement of Point Feature: Using Ant Colony Algorithm Based on Group Clustering, J. Geo-Inform. Sci., 17 (2015), 902–990. https://doi.org/10.3724/SP.J.1047.2015.00902 doi: 10.3724/SP.J.1047.2015.00902
[24]	W. Cao, F. Peng, X. Tong, H. Dai, Y. Zhang, A point-feature label placement algorithm considering spatial distribution and label correlation, Acta Geodaetica et Cartographica Sinica, 51 (2022), 301–311. https://doi.org/10.11947/j.AGCS.2022.20210247 doi: 10.11947/j.AGCS.2022.20210247
[25]	Z. Zhang, J. Yang, A discrete cuckoo search algorithm for traveling salesman problem and its application in cutting path optimization, Comput. Ind. Eng., 169 (2022), 108157. https://doi.org/10.1016/j.cie.2022.108157 doi: 10.1016/j.cie.2022.108157
[26]	J. Zheng, Y. Hong, W. Xu, W. Li, Y. Chen, An effective iterated two-stage heuristic algorithm for the multiple Traveling Salesmen Problem, Comput. Ind. Eng., 143 (2022), 105772. https://doi.org/10.1016/j.cor.2022.105772 doi: 10.1016/j.cor.2022.105772
[27]	M. Huang, F. Wang, S. Wu, The implementation of multiobjective flexible workshop scheduling based on genetic simulated annealing-inspired clustering algorithm, Wirel. Commun. Mob. Comput., 2022 (2022), 1–11. https://doi.org/10.1155/2022/7452638 doi: 10.1155/2022/7452638
[28]	J. Mou, K. Gao, P. Duan, J. Li. A machine learning approach for energy-efficient intelligent transportation scheduling problem in a real-world dynamic circumstances, IEEE Trans. Intell. Transp. Syst., 99 (2022), 1–13.
[29]	Í. Santana, A. Plastino, I. Rosseti, Improving a state-of-the-art heuristic for the minimum latency problem with data mining, Int. Trans. Oper. Res., 29 (2022), 959–986. https://doi.org/10.1111/itor.12774 doi: 10.1111/itor.12774
[30]	D. Martins, G. M. Vianna, I. Rosseti, S. L. Martins, A. Plastino, Making a state-of-the-art heuristic faster with data mining, Ann. Oper. Res., 263 (2018), 141–162. https://doi.org/10.1007/s10479-014-1693-4 doi: 10.1007/s10479-014-1693-4
[31]	M. Guerine, I. Rosseti, A. Plastino, A hybrid data mining heuristic to solve the point-feature cartographic label placement problem, Int. Trans. Oper. Res., 27 (2020), 1189–1209. https://doi.org/10.1111/itor.12666 doi: 10.1111/itor.12666
[32]	G. Luo, B. Xu, The study on automatic name placement around point features based on Voronoi, J. Chang'an University (Earth Science Edition), 2 (2003), 63–65. https://doi.org/10.3969/j.issn.1672-6561.2003.02.016 doi: 10.3969/j.issn.1672-6561.2003.02.016
[33]	L. Li, H. Zhang, H. Zhu, W. Hu, A point-feature labeling algorithm based on movable regions, Geom. Inform. Sci. Wuhan University, 43 (2018), 1129–1137. https://doi.org/10.13203/j.whugis20160289 doi: 10.13203/j.whugis20160289
[34]	J. Qi, Y. Tao, Y. Chang, R. Zhang, Packing R-trees with Space-filling curves: Theoretical optimality, empirical efficiency, and bulk-loading parallelizability, ACM Trans. Database Syst., 45 (2020), 1–47. https://doi.org/10.1145/3397506 doi: 10.1145/3397506
[35]	X. Tong, C. Cheng, R. Wang, L. Ding, Y. Zhang, G. Lai, et al., An efficient integer coding index algorithm for multi-scale time information management, Data Knowl. Eng., 119 (2019), 123–138. https://doi.org/10.1016/j.datak.2019.01.003 doi: 10.1016/j.datak.2019.01.003
[36]	A. Marín, M. Pelegrín, Towards unambiguous map labeling – Integer programming approach and heuristic algorithm, Expert Syst. Appl., 98 (2018), 221–241. https://doi.org/10.1016/j.eswa.2017.11.014 doi: 10.1016/j.eswa.2017.11.014
[37]	T. Strijk, M. V. Kreveld, Practical Extensions of point Labeling in the Slider Model, Geo. Inform., 6 (2002), 181–197. https://doi.org/10.1145/320134.320148 doi: 10.1145/320134.320148
[38]	C. Chee, J. Jaafar, I. A. Aziz, M. H. Hasan, W. Yeoh, Algorithms for frequent itemset mining: A literature review, Artif. Intell. Rev., 52 (2019), 2603–2621. https://doi.org/10.1007/s10462-018-9629-z doi: 10.1007/s10462-018-9629-z
[39]	S. V. Dijk, M. V. Kreveld, T. Strijk, A. Wolff, Towards an evaluation of quality for names placement methods, Int. J. Geogr. Inf. Sci., 16 (2002), 641–661. https://doi.org/10.1080/13658810210138742 doi: 10.1080/13658810210138742
[40]	M. A. Rylov, A, W. Reimer, Improving label placement quality by considering basemap detail with a raster-based approach, GeoInformatica, 19 (2015), 463–486. https://doi.org/10.1007/s10707-014-0214-6 doi: 10.1007/s10707-014-0214-6

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)