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.

Labeling the Coast (Part One)

In the previous two postings I talked about labeling the ocean area of the map.  I have more to say about that, but for now I'm now going to turn my attention to labeling a coastline.  This is inspired by labels like these:

Here the mapmaker names a stretch of coastline with a label that roughly follows the coastline's shape.  Again, I'm not going to concern myself right now about how to come up with good names, but rather how to place them on the map.

Looking at the examples above, the basic idea seems pretty straightforward:  Select the section of coastline to label and then place the label in the water off the coastline along a very smoothed/simplified version of the coastline.

When I select the coastline to label, I'm going to look for a fairly flat section, like the "Dong Leng Tianh" example above.  The reason for this is (spoiler alert) that I also intend to label bays, as in these examples:

How do I tell when a bit of coastline is (relatively) straight?  When I talked about creating river labels, I introduced the notion of sinuosity.  Sinuosity is the ratio of the distance along a path to the distance between the end points of the path.  The higher this ratio, the more curved the path.  A straight line has a sinuosity of 1, because the length of the path is the same as the distance between the end points. A bay, in contrast is more like a semi-circle. What's the sinuosity of a semi-circle?

The distance between the end points of a semi-circle is the diameter D of the circle.  The distance along the semi-circle is half the circumference of the circle, (Pi*D)/2.  So the sinuosity of a semi-circle is Pi/2, or about 1.5.  Therefore a coastline with a sinuosity close to 1.5 is shaped something like a bay (semi-circle), while a sinuosity close to 1 is more like a straight stretch.  So I want to treat coastline labels the same as I do river labels, placing them on the straightest sections of the path (coastline).  In fact, I may be able to treat coastline labels exactly as I do river labels, just substituting the coastline for the river.

One of the example maps I was using for ocean labeling has a fairly straight coastline, so I'll use that as my test map during development:

And after some initial bug fixes and so on, here's a coastline label:

Here I've just arbitrarily placed the label at the middle of the coastline.  The way it has shifted suggests to me that the algorithm is incorrectly trying to place the upper-right hand corner of the label (where the purple dot is) at the center of the path rather than the center of the label.  The same problem is probably active in the river labels as well, although it's less obvious at that scale.

After a lot of debugging -- sometimes when I look at my old code I wonder if I was drunk when I wrote it -- I have something closer to right:

So far I've just been placing the coast label at the middle of the coastline.  That will get a little repetitive, so I can try placing the label randomly along the coastline:

This almost works on this map, but you can see the problem -- I've randomly selected a spot on the coast where the coast is not flat.  (Actually, that's a good location for a bay label!)  What I need to do is pick a random spot on the coastline where the sinuosity is low.  Here's an example where I've picked a spot with lower sinuosity:

Again, this almost works, but even on this path with much lower sinuosity the letters in the name end up clashing with each other.  (It looks pretty cool in this case, but that's just luck.)  To be honest, this is partly SVG's responsibility: It just doesn't do a very good job laying out text along a path.  But even when the letters don't clash, I find don't really like the look of text on an arbitrary path:

So I think I need to re-assess how I'm laying out and displaying path labels.  I don't think I need to change everything, but something that allows me to present decent labels along curvy paths would be great.  More on that in the next installment.

Labeling the Ocean (Part Two)

Now that I have ocean labels working on my sample map, it's time to randomly generate a bunch of maps and look for problems.  Such as this:

This map has a lot of water -- enough to qualify to be an ocean -- but it's all spread around the edges and the ocean label doesn't look very good jammed up into the corner like that.  So apparently choosing to label any ocean bigger than 20% of the map isn't a good enough heuristic.  A quick solution to this is to put some minimum on the "distance to land" metric, which is this green circle:

In this case, that green circle is pretty small, so this map wouldn't get a label.  In fact, maybe that metric alone is sufficient for determining when to create an ocean label -- I can drop the 20% ocean minimum, and just label oceans when I find a big enough expanse of open sea.

Here's another problem:

Here there's sufficient space to fit an ocean label, but it's in a spot where there is land on all sides. This would be a nice location for a a label like "The Bay of Azgarth" but it's an odd location for an ocean label. The open spot up in the corner would be a better location.  I think the lesson here is to put the labels where they visually connect with a water edge of the map. The fact that the map ends on water suggests that there is no interesting land beyond that edge, i.e., that it's open ocean in that direction.

One way I can try to address this is to force candidate locations to be near to a map edge, i.e., to force the green circle to touch the edge of the map:

That looks better, but it would be nice to take the corner if it was available, even if that meant the green circle was a little smaller.  I can get this behavior by adding a bonus to spots that touch two map edges at the same time:

The bonus is visible here as the green circle being bigger than it should be (instead of stopping where it touches land, it actually overlaps a bit).  Let's see how this affects my previous test map.  Here's what it looks like without the bonus:

And here it is with the bonus:

The old placement wasn't terrible, but this seems better. Let's try some more maps:

Whoops.  The label is on the wrong side of the arc, and the arc is backwards.  This is more-or-less the same problem I faced with path labels.  The solution is basically to flip everything for certain base angles of the label:

So that fixed the label orientation, but I don't like the base angle of this label.  It does follow the major axis of the ocean (which runs from the upper left corner to the lower right ocean) but it doesn't look right to me.  After some thought, I decided that it might look better for the label to rotate around the center of the map.  This would mean the base angle would be at right angles to the line from the label to the center of the map:

That looks much better to my eye, although the label seems too close to the land.

Continuing onward:

Here's a label on the lower half of the map.  At first glance it looks okay, but then I realized that the curve of the arc should be going away from the center of the map.  It turns out that when labels are on the lower half of the map, I also have to reverse the "sweep" of the elliptical arc so that it bends the other way:

This is a different map, but you can see that the label arc now curves away from the center of the map.

One thing I've noticed looking at these sample maps is that the ocean label always moves a small distance off the original placement:

The simulated annealing algorithm will sometimes leave a label in a non-optimal spot, but this is happening consistently.  My first thought was that one of the simulated annealing criteria for area labels was causing it to move, but turning off the criteria didn't fix the problem.  This makes me suspect the label isn't really starting in the red box where it is supposed to start.  I can check this by peeking at the label right before the first iteration of simulated annealing:

The label should be square in the middle of the red box, so yes, that seems to be the problem.  Either I'm not placing the label where I think I am, or I'm not calculating the bounding box correctly.

After some investigation, the problem seems to be partly operator error on my part and partly a bug/quirk in SVG.  The error on my part is in miscalculating the Y offset for the label; I accidentally had it at twice the necessary value.  That's easily corrected, but the label is still in the wrong place in the X direction (along the arc):

I'm centering the label on the arc by setting the label's anchor to the middle of the label, and then placing the label at 50% of the way along the arc.  This should be correct, but something about the combination seems to be broken.  I can apply a manual adjustment:

This adjustment changes a little bit with the length of the label, so this won't be as accurate for a different length label, but this isn't brain surgery, so I picked a reasonable value and left it at that.

Let me go back now to the placement of the labels.  Here's an example map with a reasonable ocean and a label placed:

I think this label would look better if it were pushed out more towards the edge of the map, to better associate the label with the (unseen) ocean beyond the edge of the map.  Since I know the whole circle is only sea, I know there won't be a collision problem.  If I push it out too far and off the map, simulated annealing will pull it back in.

To do this, I'll shift the starting point of the label out along the line from center of the map to the original placement.  (Since the center of the map is (0, 0), this vector is easy to calculate from the original starting position.)  Then I can move the label outward along that vector some percentage of the radius of the green circle -- say 50% to place the label halfway between the center of the green circle and the edge of the green circle.  Here's what that looks like:

I think that looks much better.  Here's what it looks like on another test map, without the debugging clutter:

If the label is longer, it can move off the map when shifted out from the center, but the simulated annealing (label placement) pulls it back onto the map:

You can see that the red box indicating the original label placement goes off-screen.  The criteria for area labels puts a heavy penalty on going off-screen, so the algorithm finds a spot that is on-screen and as close as possible to the original placement, so essentially tight into that corner.

Generally speaking this seems to work pretty well.  Here's an example map I'm not so sure about:

I don't much like nearly-vertical labels, although this is not so different from similar labels in some of my reference maps, e.g. "Western Sea" on this map:

The problem might be that the label on my map doesn't run parallel to to the shore.  I'm going to working on creating labels parallel to the shore shortly, so maybe I'll revisit this example then.

Labeling the Ocean (Part One)

One thing I haven't done yet with oceans is give them names.  But almost every fantasy map gives names to the oceans:  "The Southern Ocean", "The Sea of Songs", "Silver Sea" and so on.  I'm not going to worry at this point about coming up with good names for the oceans; just with the mechanics of putting a name onto the map.

One challenge is figuring out what exactly to name.  For example, look at this map:

There's a large expanse of water in this map that seems like a good candidate for a name, but there's also some water at the top of the map that might or might not be part of the same water.

Or consider the water areas in this map:

It's hard to say whether any of those are "oceans" or lakes or separate or connected.

I've considered different ways of deciding what water to label as ocean.  One pretty good heuristic is whether water covers most of a map edge, or two adjacent edges:

In this case, it seems pretty reasonable to label the upper left as an ocean.  But in general, that situation doesn't happen that often with my maps, so I'm going to use a simpler metric:  Contiguous water that covers more than (say) 25% of the map will get a label.

These ocean labels are a kind of area label -- that is, they don't label a point or a path but an area of the map.  Up until this point, the only kind of area labels I've had were region labels, so my code has been specialized for that case.  In particular, the area labels code was putting all area labels on an arc and associating them with a map region.  That will have to change, but there's some work to do first.

The first thing I have to do is create polygons for all the separate water areas on the map.  That's straightforward, since I already have a routine that partitions the map based upon a condition.  If I make the condition "height less than zero" I get back a list of all the ocean areas on the map.  (This doesn't include rivers or lakes -- they are treated differently.)  Then it's simply a matter of iterating through the "oceans" and labeling any that are big enough.  Here's an example on a map with a single large ocean area:

The basic functionality seems to be working.  The label got drawn in the same style as the region labels; I can correct that by creating a new "ocean" label style:

One problem here is that (like the region labels) I'm placing the label at the "visual center" of the ocean polygon.  But oceans (as in this map) can have islands which create holes in the polygon.  So the visual center of the ocean might be quite close to land in the form of an island.  And I really want the label for the ocean to be out in the middle of the ocean as far from land (or the map edges) as possible.  What I really want is something like "the interior point of the polygon with the greatest minimum distance to an edge."

For a point inside a simple polygon, it's not too hard to find out how far the point is from the polygon.  You iterate through all the edges of the polygon, calculate the distance to each line segment, and then take the minimum of those values.  It gets more difficult when you have a complex polygon with "holes" in it.  Then you need to figure out whether a point is really inside the polygon, or inside a hole -- in which case it is outside of the polygon.  And then you need to calculate the distances to all the segments including the holes.  Furthermore, when my program subsets the map and generates polygons, it doesn't actually figure out which ones are holes inside of other ones.  (Although that's probably something I should add!)   So there's some bookkeeping to keeping track of all this, but eventually I have something that I think works.

The red dot on this map is the calculated "most interior" point:

It looks about right to my eye.  But as you can see, the label placing algorithm has moved the label away from that location. That doesn't seem right.

In theory, area labels should only move to improve one of these items:

1. To stay within the area
2. To stay away from the edges of the area
3. To avoid overlap with another label
4. To avoid overlap with a feature
5. To stay on the screen.

The initial placement should be good for all these items, so it's a little surprising to see it move. Presumably there's a problem with one of these items, so I can try turning them off one at a time to see which one is causing the move.  Here's what happens when I turn off #1:

Hmm.  Turning that off did cause the label to end up in a different place, but it's a different wrong place.  Maybe one of the other items is also bad?  Turning the other items off moves the label around in unpredictable ways, and eventually I realize that what's going on here is a bit more subtle.

Dragons Abound uses simulated annealing to place labels.  In each step of simulated annealing, a new candidate position for a label is generated, and if the new position is better, the label will move to the new position.  Importantly, sometimes the label will move even if the new position is the same or worse.  (This is the part of the algorithm that helps escape local minima.)  What's happening here is that there are many positions for the ocean label that are all equally good.  Basically any spot in the ocean that doesn't overlap another label or the land gets the same score.  So there's a good chance over many iterations that the label will bounce off to one of these other locations, essentially randomly.

The solution is to add a very small attraction to the label's starting point.  I can make this part of item #2 -- essentially making the labels gravitate towards the "center" of the area rather than away from the edges.  Now the positions near the starting point will be slightly better than those away, so all other things being equal, the label should end up close to the starting point:

As you can see, that worked nicely.

Now that placement is working, I want to consider how to style the label.  There are several styles I see commonly used for ocean labels on fantasy maps.  The most common style is to lay out the ocean name as a single line of text, but angle it to follow the coastline or major axis of the ocean, as in these examples:

A common variant of this is to lay out the text on a slightly curved line:

Another common style is to place the name in a block, as in these examples:

I'll start by looking at laying out the ocean name as a single line of text.  The curved line part is not so hard -- I'm already doing that for area labels, so I can re-use that code with somewhat less curve:

I don't think I've written about how the curved labels are implemented, but it isn't difficult.  SVG provides a capability to place text along a path.  The curved labels in Dragons Abound are placed on an elliptical path.  The hardest part is figuring out the appropriate size of the ellipse!

The next part is to angle the text to lie along the "major axis" of the ocean.  My simple approach to this will be to find the two points in the ocean that are the farthest apart and call the line between them the major axis of the ocean:

That's not unreasonable, but it's not where I'd put the line; I'd use something more like this:

But why I prefer that I can't clearly explain.  Obviously this is a difficult problem, but for the moment I'll continue with the simple solution.  (Although as you'll see later, I eventually do something different.)

For the next step, I want to rotate the elliptical arc that the label is placed upon by the angle of the major axis.  This isn't too difficult; I already have routines to rotate points by an angle, so the first step is to rotate the start and end points of the arc around the center point by the angle of the major axis.  But then I also have to rotate the ellipse itself.  Fortunately, that's built into the SVG routine for making elliptical arcs, so I just have to feed in the same angle of rotation to the arc routine.

That gives me this:

Here I've drawn in the end points and the arc, so you can see the label is now laid out on an arc along the major axis of the ocean.

The purple box around the label is the bounding box -- the area the label occupies.  I've turned on the bounding box here to illustrate a potential drawback of this approach -- because the label is rotated onto a diagonal, the bounding box for the label is much bigger than the label.  This is somewhat less relevant when labeling the ocean (since there's likely to be lots of empty space, and in fact this label doesn't move during label placement) but it would be better if I had some closer approximation of the text to use.

Since the curve of this label is pretty shallow, I'm going to use the rotated bounding box for the straight text as a better approximation.  Since my other area labels don't do this, this turns out to be a little bit of a pain, but in the end the code is probably the better for it -- I've generalized out some of the relevant parts of the label code.  Here's the new bounding box:

You can see the red (original) and purple (final) bounding boxes for the ocean label.  I've also added in the green circle to show how the label is situated at maximum distance from the land (and map edges).

Now that I have the implementation working on my sample map, it's time to randomly generate a bunch of maps and look for problems.  I'll start that in my next posting.