Mapping Hacks

Will the Kids Barf? #7

Chapter 1, Mapping Your Life

|

25

HACK

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 iter-

ative search process called simulated annealing. At each step, a road seg-

ment 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 accept-

ability of the layout and assigns a heuristic value representing its “good-

ness” 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 ...