Simulated Annealing

In the last post, I described Dragons Abound's force layout algorithm for placing labels on the map.  That approach has a significant drawback:  it often gets labels stuck in bad places with no way to recover.  In computing terms, this is called a local minima and various approaches have been devised to help algorithms avoid these traps.

One approach is called simulated annealing.  Simulated annealing is a method for searching a solution space for the best solution.  Imagine that we're searching for the lowest spot on this line:

There are a lot of "low spots" on that line where we could look to either side and figure that we were at the lowest possible spot.  These are the "local minima".  To keep from getting trapped in these spots, simulated annealing starts out with a high "temperature".  This temperature corresponds to how far away from the current point we can look for a better solution.  So when the temperature is high, the next point we look at can jump over nearby peaks to land on the far side, even if it where it lands is worse than where it started.  As the annealing process continues, this temperature is slowly lowered, so that the search settles into the best solution.

(These illustrations are borrowed from this paper.)

Simulated annealing isn't guaranteed to find the best solution, but it does a better job of getting out of local minima than algorithms like force layout.  For that reason, it is a popular approach to label placement.

d3js doesn't have a simulated annealing component built in (as it does with force layout) but Evan Wang from UCB has written a simulated annealing plug-in for d3js.  To be honest, the plug-in isn't very good. It doesn't handle a lot of the cases that Dragons Abound requires, and in places the code is either wrong, doesn't work, or doesn't fit with my existing code.  So I have to rewrite most of it.  But even so, having a code example is very helpful for understanding the algorithm and makes it much easier to build a working solution.

Simulated annealing is driven by the "energy function", which defines what the system is trying to minimize.  For city labels, I've defined the energy function to try to minimize the following things (in rough order of importance):

1. Going outside the map area. 
2. Distance of the label from its anchor point.
3. Overlap between labels.
4. Overlap between labels and map features. 
5. Label placement penalty.

Most of these are self-explanatory, but the last bears a quick explanation.  For labels like city labels, where the label provides the name for a feature at a point on the map, Imhof defined the best locations (with respect to the anchor point) as being (in order):  to the upper right, to the lower right, to the upper left and lastly the lower left.  So the last element of the energy function tries to get labels into the best relative position to the anchor point.

Here's an initial look at placing labels using simulated annealing:

In this case, I'm only placing city labels and the only map feature they're trying to avoid are the city symbols themselves.  The red box shows the initial placement of the labels and the purple box shows the placement after a thousand iterations of simulated annealing.  Green boxes show map features that the labels are trying to avoid. As you can see, all the labels in this map ended up in the prime label position to the upper right of the their anchor points.  All they had to do was avoid overlapping the city symbols, and annealing found good solutions for every city.

It's fairly easy to figure out when two axis-aligned rectangles are overlapping.  It's much harder to tell when two arbitrary polygons are overlapping.  So to make things easy, Dragons Abound treats all the map features that have to be avoided as rectangles (this will soon change :-).  That's why cities in the previous map have green rectangles instead of green circles.  (Actually, circular overlap is pretty easy to compute also, but it simplifies the code to treat everything as a rectangle.)  A number of these labels on the previous map overlap the coasts, so let's add the coast as map features to avoid.  The coast is a long wiggly line.  It is turned into rectangles by breaking it up into line segments and drawing a bounding box around each segment:

You can see the green bounding boxes along the coast to indicate that those boxes are now being avoided.  As a result a number of the labels have moved around.  In the middle bottom of the map, you can see that the label for "Kyup Lyak" (which was called "Katemsin Wip" in the previous map) has moved to the lower-right of the city to avoid overlapping the coast to the upper-right of the city.  The label of "Lynkryun" has a more difficult time avoiding the coast and ends up in a more undesirable spot to the upper-left of the city.

Adding the rest of the map features to avoid and labels to be placed is just more of the same.   Here's an excerpt of the same map with everything included:

You can see how labels are close to their symbols and don't cross any map features.  (Forests and mountains are ignored.)  In particular here you can see that 'Wukyip' doesn't get stuck down below the city symbol as it did with the force-layout version.

It's also worth noting that the simulated annealing approach is much faster.  The total run time for the above map with force layout was 335 seconds; with simulated annealing it was 185 seconds.

When I implement a new feature, I like to try out a bunch of different maps and see if there are problems to be addressed.  Here's an example of a problem I found doing this:

In the upper-middle part of the map you can see where two labels run into each other.  Interestingly, these labels don't overlap -- the simulated annealing managed to find positions where they're exactly adjacent to each other.  While they don't technically overlap, this is still a visual problem.

I solved this by adding a little padding to the end of the labels, so that even if two labels end up in this position, they'll have a visual break between them.  In the case of this map, the additional margin pushes one of the labels down into the ocean.

Another problem I ran into was that large labels (particularly the region labels) would sometimes wander so far off the map that they could never get back.  The reason this happened was that the distance a label can move in each iteration of the simulated annealing is based on its size.  Really large labels (and I'm still using Martin O'Leary's language generator, which occasionally comes up with very long names) could move quite a ways when the simulated annealing temperature was hot -- too far to get back as the temperature cooled down.  The solution to this was just to cap the maximum move for any label to a value that couldn't take it so far off the screen that it couldn't recover.

Next time, I'll look at some optimizations to the basic algorithm.