Labels Postscript (Part Seven)

This is a bit of a miscellaneous grab-bag of topics left over from the previous labels posts.

---

One problem I still see occasionally on crowded maps is overlapping labels, usually a region label with a city label, as in this example:

The probable cause is treating all overlaps as equal.  A major overlap of a region label with a city label is just as bad as an overlap of a region label with a tiny bit of coastline.  To improve this, I can calculate the area of overlap and weight the penalty accordingly, so that the simulated annealing tries hard to avoid major overlaps and will trade a couple of minor overlaps for a major overlap.

The area of overlap for two axis-aligned bounding boxes is trivial to calculate.  The area of overlap of two general polygons is more complex.  This page has an explanation of one commonly used method; the summary is that you break the polygon into some convenient triangles and sum the areas of the triangles.  If you're doing lots of these calculations, there are more efficient implementations.

After implementing area-of-overlap weighting, the map looks like this:

The algorithm has resolved most of the overlaps.  Some collision is inevitable in the lower left example; the algorithm has found a solution that has only overlaps along the coastline.  Although the closeness of the two labels is not visually appealing, the algorithm doesn't care because there isn't any actual overlap; they're just butted together.

---

Simulated annealing -- the algorithm I'm using to place the labels -- is an iterative algorithm.  The longer it runs, the better chance it has to find a good solution.  (Although since simulated annealing is purposely designed to sometimes go "backwards" to get out of a local minima, there's always a chance that running the algorithm longer finds a worse solution.)  On the other hand, I don't want to sit around forever waiting for label placement.  So it's useful to experiment a little to see how the number of iterations affects the quality of the solution.

Here's the map I'm using for this little experiment, showing the initial placement of all the labels:

All the city labels are dropped right on top of the city symbols, and the region labels are at an initial guess location.  (The river labels aren't showing quite yet.)

Initially I'll try running the algorithm for only 100 iterations, a very short time:

Even this small amount of effort produces "pretty good" results.  Most city labels are fairly close to their anchors without overlapping anything else.  The two obvious problems are that a city label is sticking off the edge of the map, and the "Kusilsik" region label is overlapping a border.

At 1000 iterations:

Most of the city labels are now optimal.  "Kusilsik" has been moved off the border, but now sticks outside the map borders, as does the city name "Mumatkus" above it.   "Nustatnuniak" overlaps a border, but if you examine that area of the map it's apparent that is actually a pretty good placement -- there just isn't room to place that label there without overlapping or going off the map.

At 2000 iterations:

At this point, the algorithm has traded off the various problems in the previous map for only one problem:  the "Smultulup" label goes off the edge of the map.

At 4000 iterations:

At this point the algorithm has found a fairly optimal solution.  All the city labels are well-placed near their anchor points, the region labels are entirely within their regions and without overlap.  A human labeler might choose to put "Smamat Tusul" to the upper right of the city symbol, letting it overlap the coast line in a few places and run out to sea.  The algorithm prefers to avoid most overlap and put the label in the less optimal upper left position.

An interesting thing happens when the algorithm runs for 8000 iterations:

This time the algorithm has settled on the same (sub-optimal) solution it found after 2000 iterations. This illustrates the point I made earlier:  Since the simulated annealing algorithm is designed to "jump out" of local minima, that sometimes leads it to abandon a good solution for a worse solution.

The algorithm outputs the final score of the label placement, so I can plot how the algorithm thinks the label placement improves by iterations:

This makes it pretty clear that most of the improvement happens pretty quickly.  For most purposes, a fairly small number of iterations (~1000) produces an acceptable result with very little time spent.

---

One of the goals of Dragons Abound is to create maps that look hand-crafted. Previously I wrote about making lines that look hand-drawn.  An obvious way to make text look hand-drawn is to use a handwriting font, as I do when I generate "D&D" style maps that are supposed to look like something a Dungeon Master would draw up for his campaign:

However, the handwriting fonts don't work very well on a map that's supposed to look like it is from an old book.  Instead, I use older fonts like IM Fell to create some of that "old book" atmosphere. Another little tweak I can add to help recreate that old book feeling is the occasional typesetting error.  Today's computer generated type never has a setting error, but back in the old days of Linotype and older mechanical type setting, you'd get the occasional error where a letter was too low, too high or even a little rotated.

This turns out to be pretty easy to recreate in SVG, because SVG has the capability to rotate and offset individual letters within text.  So it's just a matter of going through each label with a small chance to tweak each letter within the label.  Here's an example:

I've exaggerated this a bit to make the effect obvious, but you can see how the "n" in "Un Ime" has been rotated.

Offsets are a little trickier:

In this example the "S" in "Nun So" has been offset upwards, but you see that the "o" is also offset. Why's that?  It turns out that when you apply an offset this way in SVG, it becomes the new baseline for subsequent characters.  (Rotation doesn't work this way; it only affects a single character.)  So to get a typesetting error look, I need to un-apply the offset on the next character:

Here you can see the "N" and the "i" in "Nueppiuhhaup" have been offset upwards, and then cancelled on the next character.

It's easy to go overboard with this effect.  It's best to use it very sparingly and with small offsets to create an almost-subliminal feeling of handcraft.  See if you can spot the typesetting errors :-)