Path Labels (Part Three)

I left off last time with the path labels placed on the rivers but not yet curved to match the rivers.  I also noticed a problem with the bounding boxes for my labels:

You can see that the city and river labels are positioned on the bottom of the purple bounding boxes instead of being centered.  And labels that have descenders (like "Sottolkgol") stick out below the bottom of the bounding box.  There problems are less obvious in the curved region labels, but they are also not centered in their bounding boxes.

I wrote previously about some bounding box problems related to using web fonts, but this problem persisted even when I switched to a built-in font, so it's not related to that problem.  After some investigation, I realized that I had some confusion over the coordinates for the text item and the bounding box.  There are three different coordinate systems I need to track:

The black circle represents the coordinates of where I drew the text on the screen.  With left-justified text, this is the left-most point on the text baseline.  The green circle represents the origin of the bounding box around the text.  This is below the black circle because (1) the text has a descender that goes below the baseline, and (2) SVG seems to add some margin on the top and the bottom of text (but not on the left and right?).  Finally, the red circle represents the center point of the bounding box.  I use this as the location of the label.

The only way to figure out the origin (green circle) and size of the bounding box is to draw the text on the screen and use the browser to measure the text.  So when I first place a label on the screen I have to measure the bounding box in order to calculate the relationship between the black, green and red circles.  Fortunately this works the same for both regular text and text which has been placed on a path (which is how I created the arced region labels).

It took me way too long to wrap my head around the various coordinate systems and get the math right.  (It doesn't help that the Y axis in SVG is upside-down.)  It was even worse for the path labels which are rotated from horizontal.  (And I had a bug in the river label code that took a day to find.)

But eventually I got all the math worked out and the correct bounding boxes for the text.  Along the way I uncovered a couple of errors in the handling of the labels by the simulated annealing so I fixed those as well.

You can see that the labels are now properly within their bounding boxes and that the red circle is at the center of the bounding box.  The label placement is also much better as a result.

In retrospect this seems like a bit of dumb problem, but you guys seem to like to see my mistakes as much as my successes :-).

Before I work on curving the river labels to match the river, I'll mention a couple of unique challenges in doing the river labels.

First, typically not all rivers on maps are labeled:

In this example, the "Darkmere" river is labeled in the upper left, but the small river near the center of the map and the river through the hills on the right of the map are not labeled.  That's true on real maps as well, as shown in this excerpt of a map of Mississippi:

In fact, if you happen across a map where every river is labeled, it looks very odd:

I suppose that cartographers pick which rivers to label based on various factors -- the larger rivers, the longer rivers, or rivers that are important for other reasons.  For Dragons Abound I'm choosing to label only the rivers that are substantially longer than the river name.  "Substantially" is a matter of taste, but in practice a number in the range 1.25x to 1.75x seems to give the right proportion to my eye.  (One odd thing is that the place name generator from Martin O'Leary -- which I still use -- tends to generate a lot of long names.)  Given the way the drainage model works, these are also usually the biggest rivers:

You can see a number of unlabeled rivers in this example.

Another interesting aspect of river labels (and path labels in general) is that they're often repeated on long paths.  Imhof also suggests repeating river labels above and below major forks, where the river name may change, as in this example from his paper:

Here the "Albula" label is repeated downriver because otherwise it would be unclear what the name of the river there was.

It turns out the map scale in Dragons Abound makes rivers long enough to require multiple labels pretty rare.  At a simple level, adding multiple labels isn't terribly difficult -- I just put two labels on the river, and because the simulated annealing algorithm tries to avoid overlapping labels, they get pushed apart:

But as this example shows, just avoiding overlap doesn't lead to a pleasing arrangement of labels.  A better implementation would add a criteria that tries to keep the labels farther apart.  Or a more sophisticated approach would try to keep the labels on different sides of river junctions.  At any rate, for the moment I'm using a single label.  When I get that working well I'll look for maps with long rivers and see if it is worthwhile to implement multiple labels.

Now let me turn to the problem of curving the river labels to match the rivers.  It's a little harder to find good examples of this in amateur maps, because it requires laying out text on a path, which some graphics tools don't support and is at any rate difficult to make look professional.  You can see one example in how "Landwasser" is written in the Imhof example above, and here's another example from this map:

Laying out text along a path in SVG is actually straightforward; you create a piece of text as usual, and then you attach it to a path via a TextPath element.

(Blogger seems to have some problems with embedded SVG, so I used an image instead.)

You can control where the text falls along the path using the "startOffset" parameter, which works pretty much exactly how you'd imagine.  So it's pretty simple to drop text on a path:

But as you can see there are some problems with that approach.  The most obvious being that even though I've made some effort to select "straight" parts of the river for labeling, it still doesn't work very well.  The way to fix that is to smooth out the river (or really, the path along which I am placing the label).

I have two ways to smooth out a path.  One method works by dropping some of the points in the path, and the other works by average each point with it's neighbors.  Both of these help, but dropping points is the most important factor -- here's an example showing the smoothed rivers in red:

This does a pretty good job of creating smooth paths, but dropping arbitrary points can sometimes lead to poor results.  The "R. Kurha" river on the left edge of the map illustrates the problem -- between the label and the city of Holdal the red line is just about the inverse of the blue line.

The problem of reducing the number of points in a path while trying to keep the correct shape is called line simplification.  There are a number of algorithms for doing this.  I'm going to look at one called Visvalingam’s algorithm, primarily because Mike Bostock uses it on this page, and I can use his Javascript to help understand how to implement it.

If you look at Mike's page, there's a good explanation of how Visvalingam's algorithm works.  To steal an illustration from his page, you can visualize the areas between successive pieces of the line as triangles:

The algorithm simplifies the line by repeatedly removing the middle point of the smallest triangles.  This has the effect of creating least visible impact at each step.

It's pretty amazing how effective this algorithm is at reducing the number of points in the path while still maintaining nearly the original shape.  Here's a map that compares the original rivers to rivers with 50% of the points removed:

You can see some differences in the paths, but it's pretty minimal.  To get to a path that's more suitable for drawing labels, I have to remove about 85% of the points:

Averaging each point with it's neighbors also helps smooth out the paths:

These paths look fairly reasonable for laying out text, so let's try dropping in the labels:

There are still some problems here, but you can see that this is starting to look like a reasonable approach for labeling paths.  I'll continue next time addressing some of the obvious (and not so obvious) problems.