A Point-Feature Labeling Algorithm Based on Movable Regions

LI Lin; ZHANG Hang; ZHU Haihong; HU Wei

doi:10.13203/j.whugis20160289

Volume 43 Issue 8

Aug. 2018

Turn off MathJax

Article Contents

Abstract

References

Geomatics and Information Science of Wuhan University > 2018 > 43(8): 1129-1137. > DOI: 10.13203/j.whugis20160289

LI Lin, ZHANG Hang, ZHU Haihong, HU Wei. A Point-Feature Labeling Algorithm Based on Movable Regions[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1129-1137. DOI: 10.13203/j.whugis20160289

Citation:

PDF (4948 KB)

A Point-Feature Labeling Algorithm Based on Movable Regions

1.
School of Resource and Environmental Sciences, Wuhan University, Wuhan 430079, China

Funds:

The National Natural Science Foundation of China 41271453

the Fundamental Research Funds for the Central Universities 2012205020211

More Information

Author Bio:
LI Lin, PhD, professor, specializes in computer aided cartography, spatial data model, geographic ontology, and geovisuali-zation. E-mail: lilin@whu.edu.cn
Received Date: October 30, 2016
Published Date: August 04, 2018

Graphical Abstract

Abstract

Abstract

As the basis of point-feature label placement, the candidate label position directly affects the implementation and quality of labeling algorithms. However, fixed-position model and slider model are mainly used in previous researches, which restrict the further improvement of labeling results when considering the conflicts with point, line, and area background features. In this context, the candidate label region model based on the plane collision detection theory is proposed to accomplish conflict-free labeling by utilizing the surrounding zone of point feature. Compared with other studies, this algorithm makes a greatly improvement in label quantity and quality to meet the demand of map production.
- collision test,
- candidate label region,
- quality evaluation,
- label order

FullText(HTML)

References (28)

References

[1]	Iturriaga C, Lubiw A. NP-hardness of Some Map Labeling Problems[M]. Waterloo:University of Waterloo, Canada, 1997
[2]	Marks J, Shieber S M. The Computational Comple-xity of Cartographic Label Placement[OL]. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.8844,1991
[3]	吴长彬, 闾国年, 刘昱君.基于规则库和网格算法的土地利用现状图自动数字注记[J].测绘学报, 2008, 37(2):250-255 http://industry.wanfangdata.com.cn/dl/Detail/Periodical?id=Periodical_chxb200802021 Wu Changbin, Lv Guonian, Liu Yujun. Automated Numeric Placement for Land Utilization Map Based on Rule Data Base and Grid Algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(2):250-255 http://industry.wanfangdata.com.cn/dl/Detail/Periodical?id=Periodical_chxb200802021
[4]	张志军, 李霖, 于忠海, 等.散列式面状注记自动配置技术研究[J].武汉大学学报·信息科学版, 2011, 36(6):739-742 http://ch.whu.edu.cn/CN/abstract/abstract568.shtml Zhang Zhijun, Li Lin, Yu Zhonghai, et al. Auto-Labeling of Hash Anea Features[J]. Geomatics and Information Science of Wuhan University, 2011, 36(6):739-742 http://ch.whu.edu.cn/CN/abstract/abstract568.shtml
[5]	王昭, 吴中恒, 费立凡, 等.基于几何信息熵的面状要素注记配置[J].测绘学报, 2015, 38(2):183-188 doi: 10.11947/j.AGCS.2015.20130737 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 doi: 10.11947/j.AGCS.2015.20130737
[6]	Edmondson S, Christensen J, Marks J, et al. A Gene-ral Cartographic Labeling Algorithm[J]. Cartographica the International Journal for Geographic Information & Geovisualization, 2010, 33(4):13-24 https://sdm.lbl.gov/~kewu/ps/LBNL-59102.pdf
[7]	Wolff A, Strijk T. The Map-Labeling Bibliography[OL]. http://i11www.ira.uka.de/map-labeling/bibliography,2005
[8]	Do Nascimento H A D, Eades P. User Hints for Map Labeling[J]. Journal of Visual Languages and Computing, 2008, 19(1):39-74 doi: 10.1016/j.jvlc.2006.03.004
[9]	Klau G W, Mutzel P. Optimal Labeling of Point Features in Rectangular Labeling Models[J]. Mathematical Programming, 2003, 94(2-3):435-458 doi: 10.1007/s10107-002-0327-9
[10]	van Kreveld M, Strijk T, Wolff A. Point Labeling with Sliding Labels[J]. Computational Geometry-Theory and Applications, 1999, 13(1):21-47 doi: 10.1016/S0925-7721(99)00005-X
[11]	Rylov M A, Reimer A W. Improving Label Placement Quality by Considering Basemap Detail with a Raster-Based Approach[J]. GeoInformatica, 2014, 19(3):463-486 doi: 10.1007/s10707-014-0214-6
[12]	Rabello R L, Mauri G R, Ribeiro G M, et al. A Clustering Search Metaheuristic for the Point-Feature Cartographic Label Placement Problem[J]. European Journal of Operational Research, 2014, 234(3):802-808 doi: 10.1016/j.ejor.2013.10.021
[13]	Christensen J, Marks J, Shieber S. An Empirical Study of Algorithms for Point-Feature Label Placement[J]. ACM Transactions on Graphics, 1995, 14(3):203-232 doi: 10.1145/212332.212334
[14]	Raidl G R. A Genetic Algorithm for Labeling Point Features[OL]. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.3527,1998
[15]	Yamamoto M, Camara G, Lorena L A N. Tabu Search Heuristic for Point-Feature Cartographic Label Placement[J]. GeoInformatica, 2002, 6(1):77-90 doi: 10.1023/A:1013720231747
[16]	Schreyer M, Raidl G R. Letting Ants Labeling Point Features[C]. The 2002 Congress on Evolutionary Computation, Honolulu, USA, 2002
[17]	Ribeiro G M, Lorena L A N. Heuristics for Cartographic Label Placement Problems[J]. Computers & Geosciences, 2006, 32(6):739-748 doi: 10.1016/j.cageo.2005.10.004
[18]	Strijk T, van Kreveld M. Practical Extensions of Point Labeling in the Slider Model[J]. GeoInformatica, 2002, 6(2):181-197 doi: 10.1023/A:1015202410664
[19]	Schwartges N, Haunert J H, Wolff A, et al. Point Labeling with Sliding Labels in Interactive Maps[C]. 17th AGILE Conference on Geographic Information Science, Castellon, 2014
[20]	Rylov M A, Reimer A W. Improving Label Placement Quality by Considering Basemap Detail with a Raster-Based Approach[J]. GeoInformatica, 2015, 19(3):463-486 doi: 10.1007/s10707-014-0214-6
[21]	王志强, 洪嘉振, 杨辉.碰撞检测问题研究综述[J].软件学报, 1999, 10(5):545-551 http://www.cqvip.com/QK/91690X/200332/8605025.html Wang Zhiqiang, Hong Jiazhen, Yang Hui. A Survey of Collision Detection Problem[J]. Journal of Software, 1999, 10(5):545-551 http://www.cqvip.com/QK/91690X/200332/8605025.html
[22]	吴华意.平面内多边形沿曲线定姿态刚体移动时的碰撞判定算法研究[J].计算机学报, 1999, 22(12):1332-1334 doi: 10.3321/j.issn:0254-4164.1999.12.020 Wu Huayi. Research on Algorithm for Collision Test of Polygon[J]. Chinese Journal of Compu-ters, 1999, 22(12):1332-1334 doi: 10.3321/j.issn:0254-4164.1999.12.020
[23]	李庆华.确定凸多边形可碰撞区域的快速算法[J].中国科学(A辑), 1992, 22(7):753-762 http://www.cnki.com.cn/Article/CJFDTOTAL-GCTX200002008.htm Li Qinghua. Rapid Algorithm Deciding Possible Collision Zone of Convex Polygons[J]. Science in China (A), 1992, 22(7):753-762 http://www.cnki.com.cn/Article/CJFDTOTAL-GCTX200002008.htm
[24]	Ghosh P K. A Solution of Polygon Containment, Spatial Planning, and Other Related Problems Using Minkowski Operations[J]. Computer Vision, Graphics, and Image Processing, 1990, 49(1):1-35 doi: 10.1016/0734-189X(90)90160-W
[25]	Ghosh P K. An Algebra of Polygons Through the Notion of Negative Shapes[J]. CVGIP:Image Understanding, 1991, 54(1):119-144 doi: 10.1016/1049-9660(91)90078-4
[26]	Yoeli P. The Logic of Automated Map Lettering[J]. The Cartographic Journal, 1972, 9(2):99-108 doi: 10.1179/caj.1972.9.2.99
[27]	Imhof E. Positioning Names on Maps[J]. The American Cartographer, 1975, 2(2):128-144 doi: 10.1559/152304075784313304
[28]	van Dijk S, van Kreveld M, Strijk T, et al. Towards an Evaluation of Quality for Names Placement Methods[J]. International Journal of Geographi-cal Information Science, 2002, 16(7):641-661 doi: 10.1080/13658810210138742

Cited By

Get Citation

PDF

XML

Article views PDF downloads

A Point-Feature Labeling Algorithm Based on Movable Regions

Abstract

References

Catalog

Related

Export File

Citation

Format

Content