| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Dynamic Map Labeling
September-October 2006 (vol. 12 no. 5)
pp. 773-780
We address the problem of filtering, selecting and placing labels on a dynamic map, which is characterized by continuous zooming and panning capabilities. This consists of two interrelated issues. The first is to avoid label popping and other artifacts that cause confusion and interrupt navigation, and the second is to label at interactive speed. In most formulations the static map labeling problem is $NP$-hard, and a fast approximation might have $O(n \log n)$ complexity. Even this is too slow during interaction, when the number of labels shown can be several orders of magnitude less than the number in the map. In this paper we introduce a set of desiderata for ``consistent'' dynamic map labeling, which has qualities desirable for navigation. We develop a new framework for dynamic labeling that achieves the desiderata and allows for fast interactive display by moving all of the selection and placement decisions into the preprocessing phase. This framework is general enough to accommodate a variety of selection and placement algorithms. It does not appear possible to achieve our desiderata using previous frameworks. Prior to this paper, there were no formal models of dynamic maps or of dynamic labels; our paper introduces both. We formulate a general optimization problem for dynamic map labeling and give a solution to a simple version of the problem. The simple version is based on label priorities and a versatile and intuitive class of dynamic label placements we call ``invariant point placements''. Despite these restrictions, our approach gives a useful and practical solution. Our implementation is incorporated into the G-Vis system which is a full-detail dynamic map of the continental USA. This demo is available through any browser.
[1] 773 J. Ahn and H. Freeman, A program for automatic name placement. In Proc. Symposium on Automated Cartography (Auto-Carto), volume 6, pages 444–453, 1983.[2] K. Ali, K. Hartmann, and T. Strothotte, Label layout for interactive 3d illustrations. The Journal of WSCG, 13, 2005.[3] R. Azuma and C. Furmanski, Evaluating label placement for augmented reality view management. In Proceedings of IEEE/ACM International Symposium on Mixed and Augmented Reality (ISMAR 2003), pages 66–75, 2003.[4] G. D. Battista, P. Eades, R. Tamassia, and I. Tollis, Algorithms for drawing graphs: an annotated bibliography, 1994.[5] K. Been, Responsive Thinwire Visualization of Large Geographic Datasets. Ph.d. thesis, New York University, Department of Computer Science, Courant Institute, Sept. 2002. Download from http://cs.nyu.edu/visual/home/pub.[6] M. A. Bekos, M. Kaufmann, A. Symvonis, and A. Wolff, Boundary labeling: Models and efficient algorithms for rectangular maps. In Proc. 12th Int. Symposium on Graph Drawing (GD'04), 2004. In Lecture Notes in Computer Science, pp. 49–59, 2005.[7] B. Bell, S. Feiner, and T. Höllerer, View management for virtual and augmented reality. In ACM Symp. on User Interface Software and Technology (UIST 2001), pages 101–110, 2001.[8] J. Christensen, J. Marks, and S. Shieber, An empirical study of algorithms for point-feature label placement. ACM Trans. on Graphics, 14 (3): 203–232, 1995.[9] S. Edmondson, J. Christensen, J. Marks, and S. Shieber, A general cartographic labeling algorithm. Cartographica, 33 (4): 13–23, 1997.[10] J. Fekete and C. Plaisant, Excentric labeling: Dynamic neighborhood labeling for data visualization. In Proc. ACM CHI'99, pages 512–519, 1999.[11] M. Formann and F. Wagner, A packing problem with applications to lettering of maps. In ACM Symp. on Comp. Geometry, volume 7, pages 281–288, 1991.[12] H. Freeman, AUTONAP — an expert system for automatic map name placement. In Proc. 1st International Symp. on Spatial Data Handling, pages 544–569, 1984. Universität Zürich-Irchel.[13] G-Vis Dynamic Labeling Demo, 2002. URL http://sage.mc.yu.edu/gvis.[14] S. A. Hirsch, An algorithm for automatic name placement around point data. The American Cartographer, 9 (1): 5–17, 1982.[15] E. Imhoff, Positioning names on maps. The American Cartographer, 2 (2): 128–144, 1975.[16] K. G. Kakoulis and I. G. Tollis, A unified approach to automatic label placement. Int'l. J. Comput. Geometry and Appl., 13 (1): 23–60, 2003.[17] J. Marks and S. Shieber, The computational complexity of cartographic label placement. Technical Report TR-05-91, Harvard CS, 1991.[18] I. Petzold, Textplazierung in dynamisch erzeugten Karten. Diploma-thesis, Institute for Computer Science, Bonn, 1996.[19] I. Petzold, Beschriftung von Bildschirmkarten in Echtzeit — Konzept und Struktur. Ph.d. thesis, Institute of Cartographcy and Geoinformation, University of Bonn, 2003.[20] I. Petzold, G. Gröger, and L. Plümer, Fast screen map labeling — data-structures and algorithms. In Proc. 21th International Cartographic Conferences (ICC'03), pages 288–298, 2003.[21] I. Petzold, L. Plümer, and M. Heber, Label placement for dynamically generated screen maps. In Proc. 19th International Cartographic Conferences (ICC'99), pages 893–903, 1999. Ottawa, Canada.[22] S.-H. Poon and C.-S. Shin, Adaptive zooming in point set labeling. In Proceedings 15th International Symposium on Fundamentals of Computation Theory (FCT 2005), pages 233–244, 2005.[23] W. Schnyder, Embedding planar graphs on the grid. In Proc. 1st ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 138–148, 1990.[24] J. Tatemura, Dynamic label sampling on fisheye maps for information exploration. In Advanced Visual Interfaces 2000, pages 238–241, 2000.[25] Topologically integrated geographic encoding and referencing system (tiger) homepage, 1995. US Census Bureau. URL http://www.census.gov/ftp/pub/geo/wwwtiger /.[26] M. van Kreveld, R. van Oostrum, and J. Snoeyink, Efficient settlement selection for interactive display. In Proceedings AutoCarto 13: ACSM/ASPRS'97 Technical Papers, pages 287–296, 1997.[27] M. J. van Kreveld, J. Nievergelt, T. Roos, and P. Widmayer, editors. Algorithmic Foundations of Geographical Information Systems, volume 1340. Springer, 1997. CISM Advanced School on the Algorithmic Foundations of Geographical Information Systems, Udine, Italy, Sep16–20, 1996.[28] R. W. van Oostrum, Geometric Algorithms for Geographic Information Systems. PhD thesis, Universiteit Utrecht, 1999.[29] F. Wagner and A. Wolff, A practical map labeling algorithm. Comput. Geometry: Theory and Appl., 7: 387–404, 1997.[30] A. Wolff, The map-labeling bibliography, 2005. http://illwww.ira.uka.de/~awolff/map-labeling/ bibliography.[31] C. Yap, K. Been, and Z. Du, Responsive thinwire visualization: Application to large geographic datasets. In E. et al., editor, Proc. SPIE Symp. on Visualization and Data Analysis 2002, volume 4665, pages 1–12, 2002.19–25 Jan, 2002, San Jose, California.[32] P. Yoeli, The logic of automated map lettering. The Cartographic Journal, 9 (2): 99–108, 1972.
Index Terms:
Map labeling, dynamic maps, human-computer interface, label placement, label selection, label filtering, label consistency, computational cartography, GIS, HCI, realtime, preprocessing.
Citation:
Ken Been, Eli Daiches, Chee Yap, "Dynamic Map Labeling," IEEE Transactions on Visualization and Computer Graphics, vol. 12, no. 5, pp. 773-780, Sept. 2006, doi:10.1109/TVCG.2006.136
