{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T20:06:07Z","timestamp":1771877167894,"version":"3.50.1"},"reference-count":39,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2016,9,1]],"date-time":"2016-09-01T00:00:00Z","timestamp":1472688000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["41271453"],"award-info":[{"award-number":["41271453"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Automatic point-feature label placement (PFLP) is a fundamental task for map visualization. As the dominant solutions to the PFLP problem, fixed-position and slider models have been widely studied in previous research. However, the candidate labels generated with these models are set to certain fixed positions or a specified track line for sliding. Thus, the whole surrounding space of a point feature is not sufficiently used for labeling. Hence, this paper proposes a novel label model based on the region of movability, which comes from plane collision detection theory. The model defines a complete conflict-free search space for label placement. On the premise of no conflict with the point, line, and area features, the proposed model utilizes the surrounding zone of the point feature to generate candidate label positions. By combining with heuristic search method, the model achieves high-quality label placement. In addition, the flexibility of the proposed model enables placing arbitrarily shaped labels.<\/jats:p>","DOI":"10.3390\/ijgi5090159","type":"journal-article","created":{"date-parts":[[2016,9,1]],"date-time":"2016-09-01T10:04:28Z","timestamp":1472724268000},"page":"159","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["A Labeling Model Based on the Region of Movability for Point-Feature Label Placement"],"prefix":"10.3390","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2034-982X","authenticated-orcid":false,"given":"Lin","family":"Li","sequence":"first","affiliation":[{"name":"School of Resource and Environmental Sciences, Wuhan University, 129 Luoyu Rd., Wuhan 430079, China"},{"name":"Geo Spatial Information Science Collaborative Innovation Center of Wuhan University, 129 Luoyu Rd., Wuhan 430079, China"},{"name":"The Key Laboratory for Geographical Information Systems, Ministry of Education, Wuhan 430079, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1132-7899","authenticated-orcid":false,"given":"Hang","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Resource and Environmental Sciences, Wuhan University, 129 Luoyu Rd., Wuhan 430079, China"}]},{"given":"Haihong","family":"Zhu","sequence":"additional","affiliation":[{"name":"School of Resource and Environmental Sciences, Wuhan University, 129 Luoyu Rd., Wuhan 430079, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6340-7452","authenticated-orcid":false,"given":"Xi","family":"Kuai","sequence":"additional","affiliation":[{"name":"School of Resource and Environmental Sciences, Wuhan University, 129 Luoyu Rd., Wuhan 430079, China"}]},{"given":"Wei","family":"Hu","sequence":"additional","affiliation":[{"name":"School of Resource and Environmental Sciences, Wuhan University, 129 Luoyu Rd., Wuhan 430079, China"}]}],"member":"1968","published-online":{"date-parts":[[2016,9,1]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1559\/152304075784313304","article-title":"Positioning names on maps","volume":"2","author":"Imhof","year":"1975","journal-title":"Am. Cartogr."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Whitesides, S.H. (1998). Graph Drawing, Springer.","DOI":"10.1007\/3-540-37623-2"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1145\/212332.212334","article-title":"An empirical study of algorithms for point-feature label placement","volume":"14","author":"Christensen","year":"1995","journal-title":"ACM Trans. Graph."},{"key":"ref_4","unstructured":"Iturriaga, C., and Lubiw, A. (1997). NP-Hardness of Some Map Labeling Problems, University of Waterloo."},{"key":"ref_5","unstructured":"Marks, J., and Shieber, S.M. (1991). The Computational Complexity of Cartographic Label Placement, Harvard University."},{"key":"ref_6","first-page":"229","article-title":"A lagrangean decomposition for the maximum independent set problem applied to map labeling","volume":"11","author":"Ribeiro","year":"2011","journal-title":"Oper. Res."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"5878","DOI":"10.1016\/j.eswa.2013.04.035","article-title":"Dispersion for the point-feature cartographic label placement problem","volume":"40","author":"Gomes","year":"2013","journal-title":"Expert Syst. Appl."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"802","DOI":"10.1016\/j.ejor.2013.10.021","article-title":"A clustering search metaheuristic for the point-feature cartographic label placement problem","volume":"234","author":"Rabello","year":"2014","journal-title":"Eur. J. Oper. Res."},{"key":"ref_9","unstructured":"Schwartges, N., Haunert, J.H., Wolff, A., and Zwiebler, D. (2014). Connecting a Digital Europe through Location and Place, Springer International Publishing."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/j.jvlc.2006.03.004","article-title":"User hints for map labeling","volume":"19","author":"Eades","year":"2008","journal-title":"J. Vis. Lang. Comput."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0925-7721(99)00005-X","article-title":"Point labeling with sliding labels","volume":"13","author":"Strijk","year":"1999","journal-title":"Comput. Geom. Theory Appl."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1007\/s10107-002-0327-9","article-title":"Optimal labeling of point features in rectangular labeling models","volume":"94","author":"Klau","year":"2003","journal-title":"Math. Program."},{"key":"ref_13","unstructured":"Raidl, G.R. (, January July). A genetic algorithm for labeling point features. Proceedings of the International Conference on Imaging Science, Systems, and Technology, Las Vegas, NV, USA."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1023\/A:1013720231747","article-title":"Tabu search heuristic for point-feature cartographic label placement","volume":"6","author":"Yamamoto","year":"2002","journal-title":"Geoinformatica"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1016\/j.cageo.2007.01.007","article-title":"A greedy randomized adaptive search procedure for the point-feature cartographic label placement","volume":"34","author":"Cravo","year":"2008","journal-title":"Comput. Geosci."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"2129","DOI":"10.1016\/j.cor.2006.09.024","article-title":"Lagrangean relaxation with clusters for point-feature cartographic label placement problems","volume":"35","author":"Ribeiro","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"2164","DOI":"10.1016\/j.cor.2010.03.005","article-title":"A new mathematical model and a lagrangean decomposition for the point-feature cartographic label placement problem","volume":"37","author":"Mauri","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1016\/j.ejor.2007.10.002","article-title":"Popmusic for the point feature label placement problem","volume":"192","author":"Alvim","year":"2009","journal-title":"Eur. J. Oper. Res."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1007\/s00453-001-0009-7","article-title":"Three rules suffice for good label placement","volume":"30","author":"Wagner","year":"2001","journal-title":"Algorithmica"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1237","DOI":"10.1109\/TVCG.2008.152","article-title":"Particle-based labeling: Fast point-feature labeling without obscuring other visual features","volume":"14","author":"Luboschik","year":"2008","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_21","first-page":"835","article-title":"Map label placement for points and curves","volume":"E86A","author":"Kameda","year":"2003","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"ref_22","unstructured":"Ebner, D., Klau, G.W., and Weiskircher, R. (2004). Graph Drawing, Springer."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1559\/152304082783948367","article-title":"An algorithm for automatic name placement around point data","volume":"9","author":"Hirsch","year":"1982","journal-title":"Am. Cartogr."},{"key":"ref_24","unstructured":"Doddi, S., Marathe, M.V., Mirzaian, A., Moret, B.M., and Zhou, B. (1997, January 13\u201323). Map labeling and its generalizations. Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201997), New Orleans, LA, USA."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1023\/A:1015202410664","article-title":"Practical extensions of point labeling in the slider model","volume":"6","author":"Strijk","year":"2002","journal-title":"Geoinformatica"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/s00453-003-1063-0","article-title":"Labeling points with weights","volume":"38","author":"Poon","year":"2004","journal-title":"Algorithmica"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1179\/caj.1972.9.2.99","article-title":"The logic of automated map lettering","volume":"9","author":"Yoeli","year":"1972","journal-title":"Cartogr. J."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/s10707-014-0214-6","article-title":"Improving label placement quality by considering basemap detail with a raster-based approach","volume":"19","author":"Rylov","year":"2014","journal-title":"GeoInformatica"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K. (1985). Stacs 85: 2nd Annual Symposium on Theoretical Aspects of Computer Science Saarbr\u00fccken, January 3\u20135, 1985, Springer.","DOI":"10.1007\/BFb0023988"},{"key":"ref_30","unstructured":"Lin, M., and Gottschalk, S. (September, January 31). Collision detection between geometric models: A survey. Proceedings of the IMA Conference on Mathematics of Surfaces, Birmingham, UK."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Kockara, S., Halic, T., Iqbal, K., Bayrak, C., and Rowe, R. (2007, January 7\u201310). Collision detection: A survey. Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Montreal, QC, Canada.","DOI":"10.1109\/ICSMC.2007.4414258"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1017\/S0263574700009644","article-title":"Separability of pairs of polygons through single translations","volume":"5","author":"Sack","year":"1987","journal-title":"Robotica"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0734-189X(90)90160-W","article-title":"A solution of polygon containment, spatial planning, and other related problems using minkowski operations","volume":"49","author":"Ghosh","year":"1990","journal-title":"Comput. Vis. Graph. Image Process."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/1049-9660(91)90078-4","article-title":"An algebra of polygons through the notion of negative shapes","volume":"54","author":"Ghosh","year":"1991","journal-title":"CVGIP Image Underst."},{"key":"ref_35","first-page":"13","article-title":"A general cartographic labeling algorithm","volume":"33","author":"Edmondson","year":"1996","journal-title":"Cartogr. Int. J. Geogr. Inf. Geovis."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1559\/152304006777323127","article-title":"Placing text and icon labels simultaneously: A real-time method","volume":"33","author":"Zhang","year":"2006","journal-title":"Cartogr. Geogr. Inf. Sci."},{"key":"ref_37","first-page":"228","article-title":"Practical results using simulated annealing for point feature label placement","volume":"24","author":"Zoraster","year":"1997","journal-title":"Cartogr. Geogr. Inf. Syst."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1007\/s00453-001-0104-9","article-title":"A tutorial for designing flexible geometric algorithms","volume":"33","author":"Kapoor","year":"2002","journal-title":"Algorithmica"},{"key":"ref_39","unstructured":"Wolff, A. General Map Labeling. Available online: http:\/\/i11www.iti.uni-karlsruhe.de\/~awolff\/map-labeling\/general\/."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/5\/9\/159\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:29:48Z","timestamp":1760210988000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/5\/9\/159"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,1]]},"references-count":39,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2016,9]]}},"alternative-id":["ijgi5090159"],"URL":"https:\/\/doi.org\/10.3390\/ijgi5090159","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9,1]]}}}