“Rendering effective route maps: improving usability through generalization” by Agrawala and Stolte

Route maps, which depict a path from one location to another, have emerged as one of the most popular applications on the Web. Current computer-generated route maps, however, are often very difficult to use. In this paper we present a set of cartographic generalization techniques specifically designed to improve the usability of route maps. Our generalization techniques are based both on cognitive psychology research studying how route maps are used and on an analysis of the generalizations commonly found in handdrawn route maps. We describe algorithmic implementations of these generalization techniques within LineDrive, a real-time system for automatically designing and rendering route maps. Feedback from over 2200 users indicates that almost all believe LineDrive maps are preferable to using standard computer-generated route maps alone.

1. M. Agrawala. Visualizing Route Maps. PhD thesis, Stanford University, 2001.]]
2. T. Barkowsky, L. J. Latecki, and K. Richter. Schematizing maps: Simplification of geographic shape by discrete curve evolution. In C. Habel C. Freska, W. Brauer and K.F. Wender, editors, Spatial Cognition II, pages 41-53. Springer- Verlag, 2000.]]
3. T. Beier and S. Neely. Feature-based image metamorphosis. Computer Graphics (Proceedings of SIGGRAPH 92), 26(2):35-42, July 1992.]]
4. B. P. Buttenfield and R. B. McMaster, editors. Map Generalization: Making rules for knowledge representation. Longman Scientific, 1991.]]
5. M. de Berg, M. van Krevald, M. Overmars, and O. Schwarzkopf, editors. Computational Geometry: Algorithms and Applications. Springer, 1997.]]
6. M. Denis. The description of routes: A cognitive approach to the production of spatial discourse. Cahiers de Psychologie Cognitive, 16(4):409-458, 1997.]]
7. M. Denis, F. Pazzaglia, C. Cornoldi, and L. Bertolo. Spatial discourse and navigation: An analysis of route directions in the city of Venice. Applied Cognitive Psychology, 13(2):145-174, 1999.]]
8. D. H. Douglas and T. K. Peucker. 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, 1973.]]
9. S. Edmondson, J. Christensen, J. Marks, and S. Shieber. A general cartographic labeling algorithm. Cartographica, 33(4):12-23, 1997.]]
10. G. Farin. Curves and Surfaces for Computer-Aided Geometric Design. Academic Press Ltd., 1988.]]
11. S. Gottschalk, M. Lin, and D. Manocha. OBB-tree: A hierarchical structure for rapid interference detection. Proceedings of SIGGRAPH 96, pages 171-180, August 1996.]]
12. J. Hershberger and J. Snoeyink. Speeding up the Douglas-Peucker linesimplification algorithm. In 5th Intl. Symp. on Spatial Data Handling, pages 134-143, 1992.]]
13. N. Holmes. The Best in Diagrammatic Graphics. Quarto Publishing, 1993.]]
14. E. Imhof. Cartographic Relief Presentation. Berlin: de Gruyter, 1982.]]
15. V. L. Interrante. Illustrating surface shape in volume data via principal directiondriven 3d line integral convolution. Proceedings of SIGGRAPH 97, pages 109- 116, August 1997.]]
16. A. M. MacEachren. How Maps Work. The Guilford Press, 1995.]]
17. J. Mackinlay. Automating the design of graphical presentations of relational information. ACM Transactions on Graphics, 5(2):110-141, 1986.]]
18. L. Markosian, M. A. Kowalski, S. J. Trychin, L. D. Bourdev, D. Goldstein, and J. F. Hughes. Real-time nonphotorealistic rendering. Proceedings of SIGGRAPH 97, pages 415-420, August 1997.]]
19. J. Marks and S. Shieber. The computational complexity of cartographic label placement. Technical Report ITR-05-91, Center for Research in Computing Techniology, Harvard University, March 1991.]]
20. Z. Michalewicz and D. B. Fogel, editors. How to Solve It: Modern Hueristics. Springer, 2000.]]
21. M. Monmonier. Mapping It Out. The University of Chicago Press, 1995.]]
22. U. Ramer. An iterative apprach for polygonal approximation of planar closed curves. Computer Graphics and Image Processing, 1:244-256, 1972.]]
23. D. D. Seligmann and S. Feiner. Automated generation of intent-based 3D illustrations. Computer Graphics (Proceedings of SIGGRAPH 91), 25(4):123-132, July 1991.]]
24. T. Strothotte, B. Preim, A. Raab, J. Schumann, and D. R. Forsey. How to render frames and influence people. Computer Graphics Forum, 13(3):455-466, 1994.]]
25. E. Tufte. Envisioning Information. Conneticut: Graphics Press, 1990.]]
26. B. Tversky. Distortions in memory for maps. Cognitive Psychology, 13(3):407- 433, 1981.]]
27. B. Tversky. Distortions in cognitive maps. Geoforum, 23(2):131-138, 1992.]]
28. B. Tversky and P. Lee. Pictorial and verbal tools for conveying routes. In C. Freska and D. M. Mark, editors, COSIT, pages 51-64, 1999.]]
29. S. Zoraster. Practical results using simulated annealing for point feature label placement. Cartography and GIS, 24(4):228-238, 1997.]]