Path Labels (Part Four)

Last time I left off with path labels in this state:

Let me catalog some of the problems and work on addressing them.

1. The label for "R. Zhochuchuchu" is on a nice straight part of the river, but it's all the way to the end, which looks awkward since there's clearly room for it to be more centered on the river.
2. The labels for "R. Chutfkur" and "R. Torzhozhida" are overlapping on the rivers they label.
3. The labels for "R. Torzhozhida" and "R. Kurha" are upside-down.
4. The labels on concave paths (e.g., "R. Chutfkur" and "R. Torzhozhida") look awkward.
5. The placement for "R. Torzhozhida" is probably too curved for reasonable labeling.

So, plenty of room for improvement!  :-)

---

Centering labels on the river should be fairly straightforward.  I need to add a new criteria to the simulated annealing that prefers labels to be close to the middle of the path they are labeling.  This should be strong enough to force the label onto a (somewhat) more curvy path, but not strong enough to force a label to overlap with another feature.

If you compare this map with the one above, you'll see that "R. Zhochuchuchu" is much more centered.  The other labels only shift slightly because they were already pretty close to the middle of the river paths.  However, "R. Zhochuchuchu" now overlaps another river.  :-(  Well, that was already issue #2...

---

There are a couple of reasons why a path label might overlap another feature.  One possibility is that the bounding box approximation I use when placing labels isn't accurate -- that is, it doesn't overlap the feature while the actual label does.  I can check that by turning on the diagnostic display of that box (it's the purple):

I could tell by visual inspection that the "R. Zhochuchuchu" bounding box was overlapping, but you can also see that "R.Chultkur" is overlapping some green boxes as well.

So the overlap is real.  It could be that the algorithm is not detecting the overlaps correctly, or it could be that it detects the overlaps but still thinks that's the best placement.  Giving very high weights to the overlaps (so that the algorithm tries much hard to avoid overlaps) will tell us which is which:

So this has fixed the "R. Zhochuchuchu" overlap problem, but it looks like "R.Chultkur" might still be overlapping.  Hard to say.  One nice thing about SVG is that zoom actually works:

You can see that simulated annealing has actually found a placement where the purple box just barely *doesn't* overlap any of the green boxes.  It's kind of impressive, really.

However, because the purple bounding box is only an approximation, the final label can end up overlapping the river anyway:

Which is unfortunate.

I could deal with this by padding the offset between the label and the river, but there's actually another more serious problem with the bounding box approximation.  Suppose we consider putting the "R. Torzhozhidal" label on the other side of the river.  I've drawn in the approximate bounding box that would result:

You can see that because the river is convex between the two anchor spots for the bounding box, the bounding box will inevitably overlap the river, unless the offset from the river is very large:

And that placement will get a largely penalty for being so far away from the river.  This means that labels are rarely placed on the convex side of a river.  The solution to these problems is to use some better approximation of the bounding box.

---

So how do we do that?

First, it's obvious that we can't actually use a box -- we need a shape that is close to the curve to which the final text will be fit, so that it will bend around obstacles appropriately.  Let's assume I want to fit text to the portion of the path below between the white markers.

It seems like I could start by duplicating the path between the two points and offset it to where I want to place the text.

Assuming I want the new path to be X units away from the existing path, how should I offset it?  The right answer is probably complex, but reasonable approach might be to establish a normal to the line between the two endpoints on the original path and offset the new path in that direction X units.

Here the black arrows represent an X unit distance along the normal to the dotted line.  Next, I create another copy of the path and offset it in the same direction the maximum height of the text.

Finally, I connect the endpoints of the two copied paths.

And that is the bounding box for text placed along the river at that location with X offset.  (With some allowances for descenders in the text and so on.)

This isn't exactly right, because SVG seems to place each glyph (letter) in the text at the normal to the path at the point where the letter is drawn, but it will at any rate be a much better approximation than the rectangular bounding box.  After fixing a few dumb bugs, here's what I have:

(I've added the green dot with the purple outline to indicate the midpoint of the river.)

It doesn't look like the labels are being placed correctly, but the purple bounding looks pretty good.  The labels are all on the bottom line of the bounding box, which means I need to offset the text by the measured size (as I figured out back in Part Three).

So now the text is at least centered in the bounding box, although it looks like some other problems are back.  One step forward, two steps back. :-)

One problem is that the center of the bounding box -- which is used to gravitate the label towards the center of the river -- is no longer being computed correctly.  The center of a curved arbitrary bounding box is probably a problematic notion, but at any rate the spot I want to use is halfway between the middle points of the top and bottom sides of the bounding box.

The (semi-visible) purple dot in the middle of the bounding box marks the center of the bounding box; you can see that the top label has been pulled closer to the middle of the river (the green dot with the purple border).  However, the labels are now overlapping the river and other features again.  Well, one step forward, two steps back... again.  :-)

The problem here turns out to be somewhat unexpected:  due to a bug in the code that places the labels, they weren't allowed to be very far from the river (you can see in the above screenshot that the purple box always lies almost exactly on the red path).  Loosening that up improves things:

Here you can see how the bounding box is no longer overlapping the green boxes -- although it is just barely kissing in spots. Now let's look at reversing labels like "R. Kurha" so that they run the other direction.  This turns out to be a little more difficult when I'm laying text along a path.

---

When my path labels were just regular text, I could flip them around to the other orientation by rotating the text 180 degrees and then moving it to the other end of the bounding box, something like this:

Unfortunately, that won't work for path labels.  When you lay out text on a path, the direction of the text matches the direction of the path.  If you want the text to run the other direction, you need a path that runs in the other direction.

(In either case, you can move the text to the other side of the path by using an offset but that doesn't chance the direction or orientation of the text.)

It's possible to reverse an SVG path, but the easier solution in this case is just to create paths in both directions for the river so that I can switch labels from one to the other as necessary.  However, the starting point isn't the same; when I reverse the path I have swap the starting point to the other end of the bounding polygon.  I also have to adjust the offset to pull the label back onto the same side as the bounding polygon.

Here you can see that "R. Kurha" and "R.Torzhozhidal" have been reversed to read the opposite direction.  Also, you can see that the long label starts outside of the bounding box -- I think that's because SVG sets text using the normal to the path at each character, and in this case that's quite a bit different from the normal I'm using to construct the bounding box.  Fixing that would be painful, so I'm going to let it go unless I see it causing significant problems down the line.

---

The last problem I want to address is when -- despite the best efforts of the algorithm -- a label ends up on an overly curved portion of a river, as with "R.Torzhozhidal" above.  This almost always happens because there simply isn't a less curvy spot available.  Here's another example from a different part of the same map:

"R.Zhochumottor" is in the best spot for labeling, but the river is just too curvy for the label to look good.

There are several ways this could be addressed.  Probably the best is to somehow simplify the river path and reduce the curve.  Or rather than trying to follow the path, labels could use generic shallow arcs situated to best follow the path.  For now, I'm going to take an easier way out:  I'll simply drop any labels that are too curvy.  Since rivers are often unlabeled anyway, this should look fine.

---

So let's take a step back and see where we are:

Overall, this label placement looks very good. Almost every label is in a near-optimal position. I see only one obvious problem:  That "R. Chukor" and "R.Tertitdul" fall on mountains and are hard to read as a result. I'll address that next time.