Mapping Hacks

8

|

Chapter 1, Mapping Your Life

#2 Route Planning Online

HACK

Route Calculation

Road-network data that is used for route calculations is a subset of the data

offered by commercial mapping data providers such as AND, GDT,

NAVTEQ, and TeleAtlas. These data sets not only include representational

information—the road class (to determine line width and line color), the

road name, and house number ranges (for labeling)—but also navigational

information.

To calculate the shortest or quickest route between two points, routing soft-

ware borrows from graph theory and relies on (a variation of) the Dijkstra or

A* algorithm. These algorithms take into account only the connectivity

between navigable features and the difficulty (or impedance) factor of each

navigable feature. When calculating the shortest route between two points

over a network, the length of the navigable features is used as the imped-

ance factor. When calculating the quickest route, the impedance factor

incorporates both feature length and travel speed; the length of the naviga-

ble features is combined with their travel speeds to approximate the travel

time for each feature.

There are various characteristics of each navigable feature that determine the

connectivity between them. The primary attribute is network topology.

Most mapping data sets are topological data sets: the geometry of the net-

work consists of nodes and lines. Each intersection ...