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.