| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Particle-based labeling: Fast point-feature labeling without obscuring other visual features
November/December 2008 (vol. 14 no. 6)
pp. 1237-1244
In many information visualization techniques, labels are an essential part to communicate the visualized data. To preserve the expressiveness of the visual representation, a placed label should neither occlude other labels nor visual representatives (e.g., icons, lines) that communicate crucial information. Optimal, non-overlapping labeling is an NP-hard problem. Thus, only a few approaches achieve a fast non-overlapping labeling in highly interactive scenarios like information visualization. These approaches generally target the point-feature label placement (PFLP) problem, solving only label-label conflicts.
This paper presents a new, fast, solid and flexible 2D labeling approach for the PFLP problem that additionally respects other visual elements and the visual extent of labeled features. The results (number of placed labels, processing time) of our particle-based method compare favorably to those of existing techniques. Although the esthetic quality of non-real-time approaches may not be achieved with our method, it complies with practical demands and thus supports the interactive exploration of information spaces. In contrast to the known adjacent techniques, the flexibility of our technique enables labeling of dense point clouds by the use of nonoccluding
distant labels. Our approach is independent of the underlying visualization technique, which enables us to demonstrate the application of our labeling method within different information visualization scenarios.
[1] C. Ahlberg and B. Shneiderman, Visual information seeking: Tight coupling of dynamic query filters with starfield displays. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (CHI'94), pages 313–317, 1994.
[2] K. Ali, K. Hartmann, and T. Strothotte, Label layout for interactive 3d illustrations. Journal of the 13th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision (WSCG'05), 13 (1): 1–8, 2005.
[3] K. Been, E. Daiches, and C. Yap, Dynamic map labeling. IEEE Transactions on Visualization and Computer Graphics, 12 (5): 773–780, 2006.
[4] B. A. Bell and S. K. Feiner, Dynamic space management for user interfaces. In Proceedings of the 13th annual ACM Symposium on User Interface Software and Technology (UIST '00), pages 238–248, 2000.
[5] B. A. Bell, S. K. Feiner, and T. Höllerer, View management for virtual and augmented reality. In Proceedings of the 14th annual ACM Symposium on User Interface Software and Technology (UIST '01), pages 101–110, 2001.
[6] S. Bruckner and E. Gröller, Volumeshop: An interactive system for direct volume illustration. In Proceedings of IEEE Visualization (VIS'05), pages 671–678, 2005.
[7] J. Christensen, J. Marks, and S. Shieber, An empirical study of algorithms for point-feature label placement. ACM Transactions on Graphics, 14 (3): 203–232, 1995.
[8] J.-D. Fekete and C. Plaisant, Excentric labeling: Dynamic neighborhood labeling for data visualization. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (CHI'99), pages 512–519, 1999.
[9] M. Formann and F. Wagner, A packing problem with applications to lettering of maps. In Proceedings of the 7th Annuual ACM Symposium on Computational Geometry (SCG'91), pages 281–288, 1991.
[10] G. Fuchs, M. Luboschik, K. Hartmann, K. Ali, T. Strothotte, and H. Schumann, Adaptive labeling for interactive mobile information systems. In Proceedings of the 10th International Conference Information Visualization (IV'06), pages 453–459, 2006.
[11] S. A. Hirsch, An algorithm for automatic name placement around point data. The American Cartographer, 9 (1): 5–17, 1982.
[12] E. Imhof, Positioning names on maps. The American Cartographer, 2 (2): 128–144, 1975.
[13] K. G. Kakoulis and I. G. Tollis, On the edge label placement problem. In Proceedings of the Symposium on Graph Drawing (GD'96), pages 241–256, 1996.
[14] W. Li, L. Ritter, M. Agrawala, B. Curless, and D. Salesin, Interactive cutaway illustrations of complex 3d models. ACM Transactions on Graphics, 26 (3): 31, 2007.
[15] J. Marks and S. Shieber, The computational complexity of cartographic label placement. Technical Report TR-05-91, Harvard CS, 1991.
[16] K. Mote, Fast point-feature label placement for dynamic visualizations. Information Visualization, 6 (4): 249–260, 2007.
[17] I. Petzold, Beschriftung von Bildschirmkarten in Echtzeit — Konzept Und Struktur. PhD thesis, University of Bonn, Germany, 2003.
[18] I. Petzold, G. Gröger, and L. Plümer, Fast screen map labeling — data-structures and algorithms. In Proceedings of the 23rd International Cartographic Conference (ICC'03), 2003.
[19] G. Raidl, A genetic algorithm for labeling point features. In Proceedings of the International Conference on Imaging Science, Systems, and Technology, pages 189–196, 1998.
[20] S. Roy, S. Bhattacharjee, S. Das, and S. C. Nandy, A fast algorithm for point labeling problem. In Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG'05), pages 155–158, 2005.
[21] A. Wolff and T. Strijk, Map labeling [website]. http://i11www.iti.unikarlsruhe.de/~awolff map-labeling/, (accessed 8-1-2008).
[22] M. Yamamoto, G. Camara, and L. A. N. Lorena, Tabu search heuristic for point-feature cartographic label placement. GeoInformatica, 6 (1): 77–90, 2002.
[23] M. Yamamoto, G. Camara, and L. A. N. Lorena, Fast point-feature label placement algorithm for real time screen maps. In Proceedings of the Brazilian Symposium on GeoInformatics (GEOINFO'05), 2005.
Index Terms:
Index Terms—interactive labeling, dynamic labeling, automatic label placement, occlusion-free, information visualization
Citation:
Martin Luboschik, Heidrun Schumann, Hilko Cords, "Particle-based labeling: Fast point-feature labeling without obscuring other visual features," IEEE Transactions on Visualization and Computer Graphics, vol. 14, no. 6, pp. 1237-1244, Nov./Dec. 2008, doi:10.1109/TVCG.2008.152
