Path Labels (Part One)

In previous posts I've talked about how Dragons Abound places point labels and area labels.  In this posting I'm going to talk about how Dragons Abound handles path labels.  These are considerably more complex.

A path label is a label that is attached to a path like a river or border.  Here's an example of some river labels in the current implementation:

Currently the labeling of rivers is a bit of kludge (i.e., a complete kludge) that happens separately before all the other labeling.  The algorithm looks along the river for a spot long enough to accommodate the label and not too curvy.  If there's a city or another river joining this river, the algorithm skips over that obstruction and starts looking again.  If it eventually finds a suitable spot, it makes a copy of the river (path) where it wants to place the label, relaxes the copied path (so it's less curvy than the river) and then writes the label along that path with an offset so that it isn't directly on top of the river.  Somewhere in there it also has to figure out whether to flip the label so that it doesn't end up reading left-to-right.  (In the above map, you can see that "R. Geheyusckuta" has been flipped.)

Generally speaking, this works fairly well but has some drawbacks.  The algorithm is conservative, so when it places a river label it usually looks okay, but it means a lot of rivers go unlabeled.  And since river labels are placed before all other labels and treated as obstacles, they sometimes prevent good placement of other labels.  Finally, the algorithm is specific to rivers, and doesn't work for labeling other paths.  For these reasons, I'd like to build general path labels into the simulated annealing algorithm, and let them get positioned in concert with all the other labels.  Much of what I have written for the existing river labels algorithm will still be applicable.  The simulated annealing will find a location for the label, but the rest of displaying the label on the map will be very similar to the current algorithm.  (I hope!)

To add path labels to the simulated annealing algorithm I need two elements: (1) a way to find new candidate locations, and (2) the criteria for judging how good a location would be for the label.

A candidate location for a path label starts by selecting a location on the path.  Just to get the code going, I started by selecting the start of the river and anchoring the labels there.

(I've turned off the forests to make the labels more visible.)  That seems to be working, so now I'll extend that to anchor the label at a random point along the length of the river, like this:

This is actually a little harder to do than you might imagine, because I have the path as a series of line segments.  So picking a random point along there involves something like picking a random line segment -- weighted by the length of the segment -- and then picking a random point within the segment.  Fortunately, there turns out to be an easier approach.

Since I've drawn the path, I can make use of some of the browser-provided methods for dealing with SVG paths.  It turns out that the browser provides a method for measuring down the length of a path and finding the screen point at that location.  So I can generate a candidate point by generating a random number between 0 and the length of the path and then using the SVG method to find the point at that distance.  This point represents the start of the label.  Here's what it looks like to generate random start points this way and anchor the labels there:

So now I have a method that can generate a new candidate position for the start of the label somewhere along the river.  However, recall that in simulated annealing there's a "temperature" that drops as the algorithm progresses.  As the temperature drops, new candidate positions should jump around less -- that is, they should progressively be restricted to being closer and closer to the current position.  I accommodate this by picking points in a window around the current position, rather than randomly along the whole length of the river.  As the temperature drops, I make the window smaller and smaller.

In the picture above, the labels are horizontal like the city and area labels.  But for path labels, I don't want them to be horizontal, but to follow the path.  To get started implementing that, I need the point on the path where the label would end if it was lying along the path.  In other words, if the label has a length 'l', I now want to look along the path until I find a point that is at least 'l' distance away from the start point:

The closest this point can be (if the path in-between is a straight line) is an additional distance "l" down the path.  If the path is not perfectly straight, then it's actually further along the path.  In that case, I step along the path in small increments until I hit the first point that is "l" or further away from the start point.

(Mentally you may be objecting that this isn't exactly right if the label follows the path.  True, but (1) it's not going to exactly follow the path, and (2) the layout is only going to approximate following the path during placement, as I'll explain below.  If you weren't thinking that, then never mind.)

This is what it looks like after finding the end point and laying the label out along that line:

So far so good.  (You might note that "R. Kurha" at the bottom of the map would need reversing to read left-to-right but I'm not dealing with that yet.)

One problem at this point is that the label is on top of the river.  To address that, I will offset the label from the path so that it parallels the path.  This is a little tricky, because the path isn't a straight line.  So I calculate the normal to the line between the start and end points.  This is another reason to find the end point -- it lets me approximate the normal to the path over the length of the label.

In this picture, the dotted arrow represents the normal to the path.  Now I select an offset distance from the path.  That becomes the corner of the label, which is aligned parallel to the path:

If I allow negative offets, that throws the label on the other side of the path.

In this case, the placement on this side is pretty poor because it overlaps the river.  But during the candidate location phase I just want to find a new location, not judge whether it is good or bad.

River labels can be on either side of the river, but some kinds of path labels need to be on one side of the path or the other (border labels being an example).  So when I create a path label to place, I need to note whether the offset can be positive or negative or both.

Here's what the example map looks like with some (random) path offset added in:

The long label at the top isn't much offset; the one at the bottom is more reasonable.  That top label is in a bad position, but remember that this part of the algorithm is just generating candidate locations.  The second part will judge how good they are, and throw out offsets that overlap the river and so on.

Again, for simulated annealing this offset needs to settle down as the temperature drops.  So I make the new offset be based upon the current offset, and as the temperature drops this is made to be closer and closer to the current offset.

Speaking of overlapping the river and other problems, how will I detect those?  To start with, I'm going to need the "bounding box" of the label.  I put bounding box in quotes there because bounding boxes are typically aligned with the coordinate system, and in this case I actually want the bounding box aligned with the angle of the label.

To create this angled bounding box, I measure the regular bounding box when the label is horizontal, and then I rotate this through the same angle as the label.  Here are the bounding boxes in purple:

There's something a little odd going on with these bounding boxes, because they're too tall.  I'm not exactly sure what's causing that.  It shouldn't have much impact on the algorithm, so it goes on the TODO list for later contemplation.

Incidentally, if you're wondering how long it takes me to implement this stuff, the above was all written during a DC to LA plane flight -- maybe 3.5 hours of coding altogether... I fell asleep at one point.

As I hinted at above, I'm not going to do the full-blown path-following labels during the simulated annealing.  (It turns out I'm lying about this and I do eventually get to something that's pretty close to full-blown path-following, as you'll see in a later posting.)  I'm going to use the angled and offset bounding boxes instead.  The simulated annealing algorithm will place those boxes to determine the label placement.  In the next posting, I'll discuss how the simulated annealing algorithm judges the value of a candidate label location.