“Automatic generation of destination maps”
Conference:
Type(s):
Title:
- Automatic generation of destination maps
Session/Category Title: Image & video applications
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Destination maps are navigational aids designed to show anyone within a region how to reach a location (the destination). Hand-designed destination maps include only the most important roads in the region and are non-uniformly scaled to ensure that all of the important roads from the highways to the residential streets are visible. We present the first automated system for creating such destination maps based on the design principles used by mapmakers. Our system includes novel algorithms for selecting the important roads based on mental representations of road networks, and for laying out the roads based on a non-linear optimization procedure. The final layouts are labeled and rendered in a variety of styles ranging from informal to more formal map styles. The system has been used to generate over 57,000 destination maps by thousands of users. We report feedback from both a formal and informal user study, as well as provide quantitative measures of success.
References:
1. Agrawala, M., and Stolte, C. 2001. Rendering effective route maps: improving usability through generalization. Proceedings of SIGGRAPH 2001, 241–249. Google ScholarDigital Library
2. Allen, G. L. 2000. Principles and practices for communicating route knowledge. Applied Cognitive Psychology 14, 4.Google ScholarCross Ref
3. Allgower, E. L., and Georg, K. 1990. Numerical continuation methods: an introduction. Springer-Verlag New York, Inc., New York, NY, USA. Google ScholarDigital Library
4. Avelar, S., and Müller, M. 2000. Generating topologically correct schematic maps. Proc. 9th International Symposium on Spatial Data Handling, 4–28.Google Scholar
5. Barkowsky, T., Latecki, L. J., and Richter, K.-F. 2000. Schematizing maps: Simplification of geographic shape by discrete curve evolution. In Spatial Cognition II, Springer-Verlag, C. H. C. Freska, W. Brauer and K. Wender, Eds., 41–53. Google ScholarDigital Library
6. Bast, H., Funke, S., Sanders, P., and Schultes, D. 2007. Fast routing in road networks with transit nodes. Science 316, 5824 (April), 566.Google ScholarCross Ref
7. Böttger, J., Brandes, U., Deussen, O., and Ziezold, H. 2008. Map warping for the annotaion of metro maps. Computer Graphics and Applications, 56–65. Google ScholarDigital Library
8. Brassel, K., and Weibel, R. 1988. A review and conceptual framework of automated map generalization. International Journal of GIS 2, 3, 229–244.Google Scholar
9. Buttenfield, B. P., and McMaster, R. B., Eds. 1991. Map Generalization: Making rules for knowledge representation. Longman Scientific.Google Scholar
10. Cabello, S., De Berg, M., Van Dijk, S., Van Kreveld, M., and Strijk, T. 2001. Schematization of road networks. In Proc. Symp. on Comp. Geom., 33–39. Google ScholarDigital Library
11. Car, A., and Frank, A. 1993. Hierarchical street networks as a conceptual model for efficient way finding. In Proc. EGIS, 134–139.Google Scholar
12. Carpendale, M., Cowperthwaite, D., and Fracchia, F. 1995. Three-dimensional pliable surfaces: For effective presentation of visual information. In Proc. UIST, 217–226. Google ScholarDigital Library
13. Casakin, H., Barkowsky, T., Klippel, A., and Freksa, C. 2000. Schematic maps as wayfinding aids. Lecture Notes in Computer Science 1849, 54–71. Google ScholarDigital Library
14. Chase, W. G. 1983. Spatial representations of taxi drivers. In Acquisition of Symbolic Skills, New York: Plenum Press, D. R. Rogers and J. A. Sloboda, Eds., 391–405.Google Scholar
15. Christensen, J., Marks, J., and Shieber, S. 1995. An empirical study of algorithms for point-feature label placement. ACM Transactions on Graphics (TOG) 14, 3, 203–232. Google ScholarDigital Library
16. de Berg, M., Cheong, O., van Kreveld, M., and Overmars, M. 2008. Computational Geometry: Algorithms and Applications. Springer-Verlag, March. Google ScholarCross Ref
17. Denis, M. 1997. The description of routes: A cognitive approach to the production of spatial discourse. Cahiers de Psychologie Cognitive 16, 4, 409–458.Google Scholar
18. Di Battista, G., Eades, P., Tamassia, R., and Tollis, I. 1998. Graph drawing: algorithms for the visualization of graphs. Prentice Hall PTR Upper Saddle River, NJ, USA. Google ScholarDigital Library
19. Douglas, D., and Peucker, T. 1973. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Cartographer 10, 2, 112–122.Google ScholarCross Ref
20. Golledge, R. 1999. Wayfinding behavior: Cognitive mapping and other spatial processes. Johns Hopkins Univ Press.Google Scholar
21. Grabler, F., Agrawala, M., Sumner, R. W., and Pauly, M. 2008. Automatic generation of tourist maps. ACM Trans. Graph. (Proc. SIGGRAPH) 27, 3 (Aug.), 100:1–100:11. Google ScholarDigital Library
22. Harrie, L. 2001. An optimisation approach to cartographic generalisation. Dept. of Technology and Society, Lund Institute of Technology, Lund University.Google Scholar
23. Jiang, B., and Claramunt, C. 2004. Topological analysis of urban street networks. Environment and Planning B 31, 1, 151–162.Google ScholarCross Ref
24. Keahey, T., and Robertson, E. 1996. Techniques for nonlinear magnification transformations. Proc. IEEE Info. Vis., 38–45. Google ScholarDigital Library
25. Lee, S.-Y., Chwa, K.-Y., Shin, S. Y., and Wolberg, G. 1995. Image metamorphosis using snakes and free-form deformations. Proceedings of SIGGRAPH 1995. Google ScholarDigital Library
26. MacEachren, A. M. 1995. How Maps Work. The Guilford Press.Google Scholar
27. Mackaness, W., and Beard, K. 1993. Use of graph theory to support map generalization. Proc. CAGIS 20, 4, 210–221.Google Scholar
28. Merrick, D., and Gudmundsson, J. 2006. Increasing the readability of graph drawings with centrality-based scaling. In Proc. APVis, Australian Computer Society, Inc., 67–76. Google ScholarDigital Library
29. Patel, K., Chen, M., Smith, I., and Landay, J. 2006. Personalizing routes. In Proc. UIST, 187–190. Google ScholarDigital Library
30. Ramer, U. 1972. An iterative procedure for the polygonal approximation of plane curves. Computer Graphics and Image Processing 1, 2, 244–256.Google ScholarCross Ref
31. Raubal, M., and Winter, S. 2002. Enriching Wayfinding Instructions with Local Landmarks. GIScience: Second International Conference 2478, 243–259. Google ScholarDigital Library
32. Sanders, P., and Schultes, D. 2007. Engineering fast route planning algorithms. Lecture Notes in Computer Science 4525, 23. Google ScholarDigital Library
33. Stevens, A., and Coupe, P. 1978. Distortions in judged spatial relations. Cognitive Psychology 10, 3, 422–437.Google ScholarCross Ref
34. Stott, J. M., and Rodgers, P. 2004. Metro map layout using multicriteria optimization. In Proc. Int. Conf. on Info. Vis., 355–362. Google ScholarDigital Library
35. Thomson, R., and Richardson, D. 1995. A graph theory approach to road network generalisation. In Proc. ICC 17, 3–9.Google Scholar
36. Tversky, B., and Lee, P. 1999. Pictorial and verbal tools for conveying routes. In COSIT, C. Freska and D. M. Mark, Eds., 51–64. Google ScholarDigital Library
37. Tversky, B. 1981. Distortions in memory for maps. Cognitive Psychology 13, 3, 407–433.Google ScholarCross Ref
38. Winter, S. 2002. Modeling costs of turns in route planning. GeoInformatica 6, 4, 345–361. Google ScholarDigital Library
39. Wolff, A., 2009. The map-labeling bibliography. http://i11www.iti.uni-karlsruhe.de/~awolff map-labeling/bibliography/.Google Scholar
