Labeling the Coast (Part Two)

In the last posting, I came to the conclusion that I need to change my approach to path labels.  Laying out the text of a label to follow a path just doesn't work well, even if the path is considerably relaxed and smoothed, as these coastline labels indicate:

(For testing purposes, I'm putting a label on every coastline.)  With river labels, I avoided this problem by simply not using any label with any sinuosity (curviness), but at this point I need a better solution.

The current algorithm works as shown in this image:

The original path is shown here as the blue line.  From that path, I create a relaxed version with the same endpoints (the gray line).  Then I offset the gray line from the original path (the dashed gray line) and lay out the text along the offset path.

After looking over a lot of maps, I think what looks best is a label along a gentle, symmetrical arc. In this case, I'd like to have something like this:

So I'm going to abandon using the original path completely, and just try to find a suitable arc.  I already know how to generate text on an arc (that's how the region labels are displayed), so the challenge here is to place labels and figure out an arc that looks good along the path.

I'll be honest and admit that I spent a lot of time going down a dead-end path (ha!) involving trying to determine whether the section of path next to a label was generally convex or concave and creating the label accordingly.  Despite quite a bit of effort, I never got that code completely working.  On the third or fourth attempt, I had a (mild) epiphany:  I didn't really need to put so much effort into trying to create a well-fitting label.  That's what I have the simulated annealing algorithm for:  It can try a bunch of different (more or less) random options and settle on the best one.

This actually greatly simplifies my code; to generate a new candidate label I only have to randomly come up with a position along the path, an offset from the path, and an amount of arc.  Then I just let the algorithm try lots of these combinations to find one that works well.  (To be fair, it's not quite that simple.  For simulated annealing, I need a method for finding candidate arcs that keeps them closer and closer to the current arc as the algorithm anneals.  That's a matter of making the new candidates randomly based on the current candidate rather than completely random.)

The only real problem I had with this version was an undetected error in my routine to determine the distance from a point to a polygon.  I also have to tweak the criteria for path labels to make the criteria that tries to snug the label up to the river a little smarter:  It now checks both corners and the midpoint of the label.  With that fixed, here's the first result of this approach:

This looks surprisingly good.  Note that some labels (like "Lost Coast" in the upper left and "R. Chorsulpur" are nearly straight while others (like "R. Murul") are quite curved.  The one obvious problem is that reversed labels (like the middle "Lost Coast") aren't in their bounding boxes.  That's just a matter of reversing the direction of the arc when the label direction is reversed:

There are a couple of odd choices, like "R. Aruls" being curved quite strongly in the "wrong" direction.  The lower-right hand "Lost Coast" label is also on the land side of the coast.  I want to force that to be on the ocean side, but right now the path label algorithm doesn't have the option to force the label to be on a particular side of the path.  I'll get to that eventually.

For the moment I'm going to turn the coastline labels off and focus on just the river labels while I tune the new algorithm.  Here's a map with a number of river labels:

Right now I have the algorithm set to use straight labels with no attempt to place the labels close to the rivers.  The blue line indicates the spots on the river corresponding to the label, and the blue line sets the angle of the label.

Let me now give some weight to being close to the river:

This does a pretty good job of bringing the labels into the rivers.  Now let me allow labels to take on a curve:

And now the labels are generally curved to fit the river.  This works very nicely in most of the cases, but it has the odd side effect of using very curved labels on very curved portions of the river (as in the case of "R. Limdun") for a very small improvement in tightness to the river.  That can be mitigated by giving the labels a preference for flat parts of the rivers:

You can see that (for instance) "R. Onan Gon" has moved onto a much flatter portion of the river. Another adjustment knob is the amount of arc allowed in the labels.  Turning this down also causes the labels to seek out flat parts of the river:

Now all the labels are flat or have a gentle curvature.

Another way to keep labels from being too curved is to create a new criteria that prefers labels with small levels of curvature. This has the advantage that a sharper curve can be used when it enables the label to avoid a bigger problem, e.g., to avoid obscuring another label.  With the weight for this criteria set to be very high, the labels are forced to be close to the target small level of curve:

If the weight for this criteria is turned down, more curved labels can be used in spots where they improve the placement in other ways:

Now let me turn the coastline labels back on to illustrate another aspect of path labels.  Unlike river labels, which can be placed anywhere along the river, the coastline labels try to stay near a particular spot on the coastline.  This is illustrated by the orange line tying the center of the label to its anchor spot:

River labels look fine snugged right up against the river, but it looks a little odd to have the coastline label right up against the coastline.  Instead, we'd like the coastline labels to gravitate towards being a little bit further off the coast.  To that end, I can set the target offset from the path to be (say) half the label height:

Now the Lost Coast label is pushed farther off the coast.

The final (?) problem with coastline labels is illustrated by this map:

Here you can see that one of the coastline labels has been placed on the land side of the coastline.  As I noted way back in my very first post about path labels, some path labels such as borders (and coastlines) should only be placed on one side of the path.  But since I've only had river labels so far it has never been an issue and I haven't implemented it that restriction.

The routine that constructs coastlines is supposed to consistently put the ocean to the left side of the line, so in theory the labels should have negative offsets to be on the ocean side of the coastline.  I can test this theory by forcing only negative offsets:

The seems to have worked -- at least on this map.  So now it's just a matter of building that capability into the algorithm in a less ad-hoc manner.

Here's an interesting case where the code seems to break down, and places a label on the land side of the ocean:

But in fact what's happened here is that the label has been placed on the left side of the bottom part of the inlet (which is part of the sea).  (You can see that the orange line for The Lost Coast label is reaching towards a spot on the bottom coast.)  The algorithm offsets the label towards the sea, but because the sea is so narrow there, the label ends up on the far side of the sea.  To be honest, I'm not sure what to do about this situation, except to hope that it doesn't come up often!

Now that I have placement of these types of labels working, in the next post I'll talk about actually using them.