Hack 6. Make Route Maps Easier to Read

Trade in complex, hard-to-read maps produced by most online route-finding services for the clean, schematic maps of driving directions made with MSN's LineDrive.

Online route-finding services have, in some ways, revolutionized the task of plotting travel routes. Rather than bothering would-be hosts to tediouslyand perhaps inaccuratelydescribe driving directions to their location by phone or email, the savvy Internet-connected automobile driver can simply say, "I'll just look it up on [insert your favorite online map service here]. Forty-five minutes, you say? See you then!" The sheer practical utility of such a tool has been the main driving force behind the development of most online, consumer-oriented mapping services.

The reality, however, is a bit uglier. Often, the maps produced by online route-finding services leave a bit to be desired. Figure 1-13 shows the map generated by MSN Maps & Directions (formerly MapBlast) to depict a driving route between the White House in Washington, DC, and Times Square in New York City. Although this map illustrates the broad sweep of the ideal course across the American landscape, it omits all of the actual details you need in order to avoid getting lost between points A and B. For that, you need to rely on the textual directions printed below the map, but these directions lose the whole sense of spatial illustration embodied by maps in general, and, what's more, the fine print can be awfully hard to read in a bouncing automobile.

Figure 1-13. A typical map of the route from the White House to Times Square

Two students from Stanford University, Maneesh Agrawala and Chris Stolte, noticed that hand-drawn route maps focus primarily on the names of roads, turning points, and the general direction of turns, while simplifying, distorting, or simply omitting other details, such as the length and shapes of roads and the exact angles of turns. Indeed, professional cartographers make use of these same techniques, collectively referred to as cartographic generalization, to make printed maps clearer and to emphasize their most important aspects. By contrast, online maps preserve every detail of a route, usually at the wrong scale, which means that shorter stretches at the beginning and end of a route often disappear relative to longer stretches in the middle. Furthermore, online map services, following the conventional "road atlas" paradigm, proceed to stuff the map full of all sorts of other details that might be relevant when planning a route, but that only get in the way when simply trying to follow a route. The result is worse than useless, because the driver of an automobile is often the navigator as well, and any map that requires more than a glance to extract crucial information can be a driving hazard.

1.7.1. Making a LineDrive Map

To that end, Agrawala and Stolte set out to devise a means by which a computer might automatically generate route maps in the style of hand-drawn driving directions, for maximum readability. The result is LineDrive, a service that they developed in conjunction with MapBlast, one of the Web's first consumer-oriented route-finding services. Vicinity, the company that made MapBlast, was subsequently bought by Microsoft and turned into MSN Maps & Directions, but the site still lives at http://www.mapblast.com/, and it still offers the LineDrive routing service for both North America and most of Europe.

Creating your own LineDrive driving directions map is simple. Just visit http://www.mapblast.com/, and click "Directions" on the navigation bar. Enter an origin and a destination in the form, and be sure to select "LineDrive" as the map style in the radio-button group on the right. Then click "Get Directions," and you're done! Figure 1-14 shows LineDrive's version of the same route from Washington, DC, to New York City.

Figure 1-14. A LineDrive map of the route from the White House to Times Square

In contrast to the conventional map shown in Figure 1-13, the LineDrive map compresses the 112 miles of the trip spent on the New Jersey Turnpike down to the same length on the map as the 4 miles along US 50 in Maryland or half a mile down 15th St NW in Washington, because all a driver needs to do along each of those road segments is to stay on the road! At the same time, each and every turn required to get from one place to the other is recorded on the LineDrive map, from going round the block with the flow of traffic when leaving the White House, to taking I-295 across the Delaware Memorial Bridge to bypass Philadelphia. The presence of Philadelphia as a thing to bypass is omitted by this map, as are many other irrelevant geographic facts, for the precise reason that you don't actually need to know that Philadelphia exists in order to travel from Washington to New Yorkyou just need to follow the directions on the map. With the elimination of border controls under the Schengen Treaty, European driving maps don't even show national bordersjust distances, turns, and route numbers!

1.7.2. How LineDrive Works

LineDrive uses the same route-finding backend as MSN's standard route maps. However, instead of rendering the usual set of cartographic layers and highlighting the route on top, LineDrive starts by collecting all of the geographic data representing the route and then subjects it to a sequence of generalization techniques, as mentioned earlier. First, it simplifies the shape of each road segment as much as possible, taking care not to add false road intersections, remove actual ones, or distort turn angles too much.

Next, the simplified road segments are laid out on the map, through an iterative search process called simulated annealing. At each step, a road segment is randomly selected and its length is scaled by a random amount, or its orientation on the map is adjusted in a random direction, and then the whole route is scaled down to fit within the target viewing window. The new layout is then tested by a scoring function that evaluates the visual acceptability of the layout and assigns a heuristic value representing its "goodness" in terms of several perceptual criteria, such as minimum and relative road lengths, general accuracy of turn directions, and preservation of the original route orientation.

The new layout is then either accepted or rejected based on its relationship to the score of the previous layout and a temperature value, which decreases with each iteration. This "temperature" value allows the iterative process to occasionally accept a worse layout early on in the process, which avoids the "local minimum" problem that plagues other kinds of search algorithms, wherein a search settles on a mediocre solution early on and ignores the presence of better overall solutions. As the temperature settles, the search algorithm homes in on progressively better layouts until the final one is selected. The way in which the simulated annealing algorithm slowly "cools off" the map layout parameters is analogous to a metallurgical process called annealing, in which internal stresses are removed from a piece of worked metal by heating it and cooling it slowly, to encourage crystalline structures to reform.

A similar process is then used to place the road labels on the map, select additional contextual clues (i.e., cross streets and landmarks) to display, and to adjust the decorations used to identify turning points, road types, and so on. The finished map is then delivered to the user. If you're curious about the specific details of the algorithms used by LineDrive, we strongly encourage you to read Agrawala and Stolte's original paper, entitled "Rendering Effective Route Maps: Improving Usability Through Generalization," which you can find on the Web at http://graphics.stanford.edu/papers/routemaps/.