Path Labels (Part Two)

In the previous post, I talked about adding path labels to Dragons Abound and described the first part of that -- the part of the simulated annealing algorithm that found new candidate positions for path labels.  In this posting I'll talk about the second part, which is how to evaluate a candidate position.

For point labels -- like the name of a city -- I used the following criteria to evaluate a candidate position:

1. Going outside the map area. 
2. Distance of the label from its anchor point.
3. Overlap between labels.
4. Overlap between labels and map features. 
5. Label placement penalty.

#2 and #5 don't make sense for path labels, but otherwise this is a good start.  Other criteria I think I should consider include how far a label is offset from the path (closer is better) and how curvy the path is where the label is placed (smoother is better).

1. Going outside the map area. 
2. Overlap between labels.
3. Overlap between labels and map features. 
4. Offset distance.
5. Curviness of path.
   

Implementing #1 is the same as with the other label types so I'll skip talking about that.  #2 and #3 are a little different.

Previously, all the labels and features in Dragons Abound were horizontally aligned:

This makes detecting overlaps fairly trivial.  However, path labels are not aligned horizontally:

So the simple intersection is not going to work.

Determining whether two arbitrary polygons intersect is a non-trivial problem.  Certainly one I don't want to solve myself, but no need, there are plenty of implementations to choose from.  I ended up using an implementation of Greiner-Horman from Alexander Milevski.  I chose this implementation because it was fast, small and did what I needed, but he also has a more full-feature implementation of Martinez-Rueda polygon clipping that I can switch to if necessary.  (And I might, because that supports polygon offsets, which might have some uses in map creation.)

So to implement the overlap conditions for path labels, I have to replace the simple intersection with the more complex Greiner-Horman intersection.  This is pretty straightforward.  Wiring it all up to work with the simulated annealing algorithm is a little more work (mostly because I decide to refactor the whole thing about halfway through), but eventually I have that portion of the evaluation working, and it produces this:

Here you can see the upper label has been moved off the river (where it overlaps with the features comprising the river).

The next step is to assess the offset distance.  Initially I thought that trying to minimize the offset distance was the right idea, but it turns out that jams all the labels right up against the river.  It's better to reward a label that's close but not too close -- say a half label height or so away from the river.  That results in something like this:

Here I've shown two red spots where the label is anchored to the river, and you can see that the labels are about a half a label height away from those anchors.  But notice that the path (river) for the upper label has a bend so that even though the anchors are properly positioned, the label almost touches the river near the "Z".  That will hopefully be fixed when I curve the label to match the river.

Speaking of curves, the last criteria I want to implement is the curviness of the path, so that labels prefer to be on straight sections of the path.  How do you measure curviness?  I chose to use a simple metric:  the ratio of the length of the path between the two red dots to the straight-line distance between the two red dots.  That turns out to be sinuosity.  So I'll turn that on:

You can see the upper label has shifted quite a bit upstream to get on a nearly flat part of the river.  The lower label move is more subtle, but by shifting just a bit downstream it found a much flatter part of the river.

The last thing I'm going to implement in this posting is label flipping.  You'll notice that the lower label in the above screen shots looks awkward because the angle puts the text upside down to the reader.  The solution is to notice when this happens and flip the label end-for-end so that it reads the other direction:

You can see the label is now easier to read.  Unfortunately, this reveals a couple of issues.  First, the label is overlapping another river, which it shouldn't do.  More subtly, the top of the bounding box is now towards the anchor point instead of the bottom.  The problem is that I also flipped the bounding box when I flipped the label.  If you'll forgive a crude cut & paste job, this shows the original label and the flipped label:

The original bounding box didn't intersect with anything and was a good distance from the river.  What I want to do is flip the label within the bounding box:

Well, this sort of worked.  The label is now a reasonable distance from the river.  But for some reason it is now overlapping with the region name.

To make a long (debugging) story short, there are a number of problems here.  The most relevant is that I hadn't gone back to the code for the area and point labels and updated them to check for overlaps with the path labels.  So the "helchza" area label was ignoring the "R. Kurha" river label.  Oops.  Then to make matters worse, I had a silly error in how I was constructing the polygons for that check, so I was essentially only checking the diagonal rather than the whole polygon.  Those things are easily fixed.

I also noticed a problem with the bounding boxes for rivers.  To make the labels avoid overlapping the rivers, the rivers are turned into a series of fixed bounding boxes that are checked for overlap.  But it turns out the bounding box for the very end of the river was missing:

This is a type of "fencepost error" where you don't handle the start or end of a sequence correctly.  It's a very common error where you have to use both the "i"th element and the "i+1"th element to process the sequence.  And indeed, to turn a path into a sequence of bounding boxes I operate two elements at a time.  Or at least I did at one point -- a change in the path data structure made that unnecessary, but the code hadn't been updated.  That was quickly fixed:

With all those fixes in place, the river label placement looks pretty good:

You can see the labels are on reasonably straight sections of river and placed out of the way of other labels and features, and "R. Kurha" has been flipped to read correctly.

It looks like I still have some problems with the bounding boxes on my labels and I still need to curve the river labels to match the rivers.  Those things next time.