|Maneesh Agrawala||Computer Graphics Laboratory , Stanford University|
|| Computer Graphics
Laboratory , Stanford University
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.
SummaryRecently, route maps in the form of driving directions have become widely available through the Web. In contrast to hand-designed route maps, these computer-generated route maps are often more precise and contain more information. Yet these maps are more difficult to use. The main shortcoming of current systems for automatically generating route maps is that they do not distinguish between essential and extraneous information, and as a result, cannot apply the generalizations used in hand-designed maps to emphasize the information needed to follow the route.
Figure 1 shows several problems arising from the lack of differentiation between necessary and unnecessary information. The primary problem is that current computer-mapping systems maintain a constant scale factor for the entire map. For many routes, the lengths of roads can vary over several orders of magnitude, from tens of feet within a neighborhood to hundreds of miles along a highway. When a constant scale factor is used for these routes, it forces the shorter roads to shrink to a point and essentially vanish. This can be particularly problematic near the origin and destination of the route where many quick turns are often required to enter or exit a neighborhood. Even though precisely scaled roads might help navigators judge how far they must travel along a road, it is far more important that all roads and turning points are visible. Handdrawn maps make this distinction and exaggerate the lengths of shorter roads to ensure they are visible.
Another problem with computer-generated maps is that they are often cluttered with information irrelevant to navigation. This extraneous information, such as the names and locations of cities, parks, and roads far away from the route, often hides or masks information that is essential for following the route. The clutter makes the maps very difficult to read, especially while driving. Handdrawn maps usually include only the most essential information and are very simple and clean. This can be seen in figure 1(middle) where even the shape of the roads has been distorted and simplified to improve the readability of the map. Furthermore, distorting the lengths of shorter roads and removing unnecessary information makes it possible to include and emphasize helpful navigational aids such as major cross-streets or landmarks before the turns.
This paper presents two main contributions in the area of automatic route map design:
Route Map Generalization Techniques We have developed a set of generalization techniques specifically designed to improve route map usability. Our techniques are based on cognitive psychology research which has shown that an effective route map must clearly communicate all the turning points on the route, and that precisely depicting the exact length, angle, and shape of each road is much less important. We consider how these techniques are applied in handdrawn maps and show that by carefully distorting road lengths and angles and simplifying road shape, it is possible to clearly and concisely present all the turning points along the route.
Automatic Route Map Design System We describe LineDrive, an automatic system for designing and rendering route maps. LineDrive takes advantage of our route map generalization techniques to produce maps that are much more usable than those produced by standard computer-based map rendering systems. By introducing the flexibility to distort road lengths, angles and shape, we create a large space of possible map designs. LineDrive performs a focused randomized search over this space to quickly find a near-optimal layout for the roads, labels, and context information. An example of a LineDrive map is shown in figure 1(right).
Paper (Siggraph 2001):
A Design and Implementation for Effective Computer-Generated Route Maps