Rendering effective route maps: improving usability through generalization

ABSTRACT

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.

REFERENCES

• 1: Maneesh Agrawala , Pat Hanrahan, Visualizing route maps, 2002
• 2: Thomas Barkowsky , Longin Jan Latecki , Kai-Florian Richter, Schematizing Maps: Simplification of Geographic Shape by Discrete Curve Evolution, Spatial Cognition II, Integrating Abstract Theories, Empirical Studies, Formal Methods, and Practical Applications, p.41-53, January 2000
• 3: Thaddeus Beier , Shawn Neely, Feature-based image metamorphosis, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.35-42, July 1992
• 4: B. P. Buttenfield and R. B. McMaster, editors. Map Generalization: Making rules for knowledge representation. Longman Scientific, 1991.
• 5: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 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: Gerald Farin, Curves and surfaces for computer aided geometric design: a practical guide, Academic Press Professional, Inc., San Diego, CA, 1988
• 11: S. Gottschalk , M. C. Lin , D. Manocha, OBBTree: a hierarchical structure for rapid interference detection, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.171-180, August 1996 [doi>10.1145/237170.237244]
• 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: Victoria Interrante, Illustrating surface shape in volume data via principal direction-driven 3D line integral convolution, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.109-116, August 1997 [doi>10.1145/258734.258796]
• 16: A. M. MacEachren. How Maps Work. The Guilford Press, 1995.
• 17: Jock Mackinlay, Automating the design of graphical presentations of relational information, ACM Transactions on Graphics (TOG), v.5 n.2, p.110-141, April 1986 [doi>10.1145/22949.22950]
• 18: Lee Markosian , Michael A. Kowalski , Daniel Goldstein , Samuel J. Trychin , John F. Hughes , Lubomir D. Bourdev, Real-time nonphotorealistic rendering, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.415-420, August 1997 [doi>10.1145/258734.258894]
• 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: Zbigniew Michalewicz , David B. Fogel, How to solve it: modern heuristics, Springer-Verlag New York, Inc., New York, NY, 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: Dorée Duncan Seligmann , Steven Feiner, Automated generation of intent-based 3D Illustrations, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, p.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: Edward Tufte, Envisioning information, Graphics Press, Cheshire, CT, 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: Barbara Tversky , Paul U. Lee, Pictorial and Verbal Tools for Conveying Routes, Proceedings of the International Conference on Spatial Information Theory: Cognitive and Computational Foundations of Geographic Information Science, p.51-64, August 25-29, 1999
• 29: S. Zoraster. Practical results using simulated annealing for point feature label placement. Cartography and GIS, 24(4):228-238, 1997.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Design, Performance, Theory

Keywords:
WWW applications, human factors, information visualization, non-realistic rendering