Add labels that follow street segments

[woodbri@…]

Steve I have copied some of our email exchange to this bug for you because I can
not find another bug for this feature request.

http://lists.xcf.berkeley.edu/lists/gimp-user/2002-December/005209.html
found in
http://www.google.com/search?num=100&hl=en&lr=&newwindow=1&safe=off&q=freetype+%22text+along+path%22&btnG=Search

This is a pretty good algorithm for doing this. It basically follows the 
  algorithm that is in the Postscript "Blue Book". The basic algorithm 
is to get the start point and angle and write one character at a time. 
You then compute the next character start point and angle and repeat. 
You can adjust the inter character spacing as you change segments to 
deal with crowding on acute corners and spreading on obleak corners. If 
you run out of segment, you just continue along an extension of that 
segment.

I think the big problem with this is how to deal with the bounding box 
for the text to deal with collisions. I have thought about this a lot 
and think I would deal with this by creating a list of bboxes for each 
piece of text that represents the individual segments runs of characters 
by combining the character bboxes for a run of characters along a 
straight segment into a seg_bbox for those character that are all 
aligned on a common segment. So a structure like:

struct label_bbox {
   int   cnt_of_segments;
   bbox *seg_bbox;
   bbox  label_bbox;
}

The label_bbox is used to reject it quickly and is just the bbox of all 
the seg_bbox's. If the label_bbox overlaps the the label being check 
against, then you need to all the seg_bbox's in the list against all the 
other seg_bbox's in the other list. Again you can trivially reject any 
single seg_bbox against the other label_bbox.

Just a thought. This would really be a coolness factor for Mapserver! as 
not many other programs can do it. In fact I was surprised that only 
GIMP showed up in the OpenSource world.

Steve Lime responded in part with:

Please keep sending ideas, wait, actually create a feature request so we don't
lose 'em. I can't promise I'll be able to do something with all of them. 

The collision piece doesn't worry me that much. Annotation + a marker already
deals with it since the text and the marker have different bboxes. There's a
special intersection test that deals with these. The hard part is creating the
multiple bboxes. GD's freetype interface doesn't expose individual glyph
metrics- it's the whole string or nothing. You need to know where the pieces fit
next to one another. One the bright side autodesk did hack GD to do this I
believe. They have submitted the changes but I don't know the status of them.
Perhaps in 2.0.34...

-- end of included message --

[dmorissette]

*** Bug 206 has been marked as a duplicate of this bug. ***

[benjcarson@…]

Proposed patch for curved text rendering

[sdlime]

Wow, it's not often you wake up to find major features available as a patch. 
I'll try hooking it up on my end and get back to you. Do you have some output 
samples you could post?

Steve

[benjcarson@…]

Sample output 01

[benjcarson@…]

Sample output 02

[benjcarson@…]

Sample output 03

[dmorissette]

Amazing! Thanks for contributing this Benj!

[sdlime]

Output looks very nice, great work. I'm just starting to look through the patch.
It feels a bit wierd to have the path (label_line) in the label object. I wonder
if a labelcache member is a better place. There's already a shapeObj *poly
member that can hold the character outlines and that's used in the labelcache
processor for collision detection already (populate it and the existing code
should just use them). The label_bbox isn't needed then since the detection
happens on the outlines. This is necessary because rotated labels would take up
to darn much space otherwise.

What about exanding msAddLabel() to take a path argument as well? Then store the
path in the label cache. Then when rendering the cache if a path exists we
compute the character positions (filling out the poly mentioned above) and then
normal cache collision detection would take over. Finally the alternate drawing
routine would we used if the path is not NULL. Buffering would have to be
applied to each character bbox.

Couple of questions:

  - how do you see this being invoked? I don't know if we want to ditch the old
ANGLE AUTO for lines. Perhaps ANGLE FOLLOW?

  - how is the label path generated or is it just the clipped/transformed shape?
If so how are multipart lines handled?

Again, great work. I look forward too using the functionality.

Steve

[sdlime]

Output looks very nice, great work. I'm just starting to look through the patch.
It feels a bit wierd to have the path (label_line) in the label object. I wonder
if a labelcache member is a better place. There's already a shapeObj *poly
member that can hold the character outlines and that's used in the labelcache
processor for collision detection already (populate it and the existing code
should just use them). The label_bbox isn't needed then since the detection
happens on the outlines. This is necessary because rotated labels would take up
to darn much space otherwise.

What about exanding msAddLabel() to take a path argument as well? Then store the
path in the label cache. Then when rendering the cache if a path exists we
compute the character positions (filling out the poly mentioned above) and then
normal cache collision detection would take over. Finally the alternate drawing
routine would we used if the path is not NULL. Buffering would have to be
applied to each character bbox.

Couple of questions:

  - how do you see this being invoked? I don't know if we want to ditch the old
ANGLE AUTO for lines. Perhaps ANGLE FOLLOW?

  - how is the label path generated or is it just the clipped/transformed shape?
If so how are multipart lines handled?

Again, great work. I look forward to using the functionality.

Steve

[sdlime]

Benj: I'm getting a better picture of how this works. 

We definitely need to get things into the cache. I would suggest having
msPolylineLabelPoints() return the label points (as lineObj) and character boxes
(as multipart shapeObj) and then have those passed into msAddLabel(). We could
shorten that parameter list to msAddLabel() a bit by passing a reference to the
shapeObj being labeled (it holds classindex, shapeindex, tileindex and the
text). Still more questions...

The actual angle of any character doesn't seem to be computed until
msDrawTextLineGD is called. That makes the character boxes computed in
msPolylineLabelPoints less useful (or not at all?) for collision avoidance (what
do those boxes represent?). I think we really need the rotated character
boundaries earlier. I'm wondering if much of msDrawTextLineGD and
msPolylineLabelPoints could be combined.  msDrawTextLineGD could go away then,
using repeated calls to msDrawTextGD instead to render each character (from the
labelcache). The draw back is that performance drops since you have to place and
rotate characters for labels that might not get drawn. 

Steve

[benjcarson@…]

Thanks for the kind words folks.  I should be thanking you for MapServer; so thanks!

First a couple of answers:  (I had this half-composed before your latest
comment, Steve, so I aplogise if this is a tad redundant.)

> how is the label path generated or is it just the clipped/transformed shape?
> If so how are multipart lines handled?

The label path is basically calculated as follows:
  
  Given shape p, string str:
  1. Let max_line_length = length of the longest line in shape p.
  2. Let text_length = length of str in pixels
  3. Let text_start_length = (max_line_length - text_length) / 2.  
     This means we center the text along the longest continuous line of p.
  4. Scan from the beginning of the longest line for text_start_length units.
  5. Let j be the line segment where we stop (and where the text begins)
  6. Let distance_along_segment = the distance along j where the first character
     will be placed.
  7. Let t = distance_along_segment / length(j)
  8. Let k = 0
  9. For each character c in str:
    a. Find (x,y) using t and:
         x = t(x[j] - x[j-1]) + x[j-1]
         y = t(y[j] - y[j-1]) + y[j-1]
       Let label_line[k] = (x,y)
    b. Let char_length = length of c in pixels
    c. distance_along_segment += char_length
    d. if distance_along_segment > length(j)
         distance_along_segment -= length(j)
         j = next segment
    e. t = distance_along_segment / length(j)
    f. k++

So, the label_line is a series of points that lie on the longest line in a given
multiline, spaced apart by the width of each character.  

In addtion to the above there is a trick to handle ligatures (e.g. AV takes less
space than just 'A' and 'V'), some code to reverse the label line if it goes
from right to left (which could be improved), and another bit to handle
extrapolation of the first and last segments.  Otherwise, it's basically the
algorithm above.

> - how do you see this being invoked? I don't know if we want to ditch the old
> ANGLE AUTO for lines. Perhaps ANGLE FOLLOW?

I agree that ANGLE AUTO should be kept.  ANGLE FOLLOW works for me, or ANGLE
PER_CHAR or similar.  An ANGLE option would probably be best since this feature
would exclude ANGLE AUTO or any other ANGLE setting for that matter.

> It feels a bit wierd to have the path (label_line) in the label object. I wonder
> if a labelcache member is a better place. There's already a shapeObj *poly
> member that can hold the character outlines and that's used in the labelcache
> processor for collision detection already (populate it and the existing code
> should just use them). The label_bbox isn't needed then since the detection
> happens on the outlines. This is necessary because rotated labels would take up
> to darn much space otherwise.

Yeah, labelObj probably isn't the best place for the label_line.  Storing it in
the label cache would be more consistent since, as you  mention, there is
already some geometry information stored there.  The *poly member can then be
used to store the bounding box of the entire label line as it does for normal
labels.  msAddLabel() could then be extended to take the label line to be stored
in the labelcacheMemberObj.

> What about exanding msAddLabel() to take a path argument as well? Then store the
> path in the label cache. Then when rendering the cache if a path exists we
> compute the character positions (filling out the poly mentioned above) and then
> normal cache collision detection would take over. Finally the alternate drawing
> routine would we used if the path is not NULL. Buffering would have to be
> applied to each character bbox.


Right now, the label line is being calculated from a call in msDrawShape(). 
This means that the label_line is calculated before the call to msAddLabel(), so
it would be straightforward to pass it along there.  This means though that the
line is already calculated by the time we get to msDrawLabelCacheGD().  Maybe
this isn't a good thing?  Instead, we could extract the appropriate line from
the shape in msDrawShape() and store that in the cache.  Then we could run the
label line algorithm on the cached line later.


> We definitely need to get things into the cache. I would suggest having
> msPolylineLabelPoints() return the label points (as lineObj) and character boxes
> (as multipart shapeObj) and then have those passed into msAddLabel(). We could
> shorten that parameter list to msAddLabel() a bit by passing a reference to the
> shapeObj being labeled (it holds classindex, shapeindex, tileindex and the
> text). Still more questions...

Well, I guess you answered my question ;)  Okay, I'll store the label line in
the cache.

> The actual angle of any character doesn't seem to be computed until
> msDrawTextLineGD is called. That makes the character boxes computed in
> msPolylineLabelPoints less useful (or not at all?) for collision avoidance (what
> do those boxes represent?). I think we really need the rotated character
> boundaries earlier. I'm wondering if much of msDrawTextLineGD and
> msPolylineLabelPoints could be combined.  msDrawTextLineGD could go away then,
> using repeated calls to msDrawTextGD instead to render each character (from the
> labelcache). The draw back is that performance drops since you have to place and
> rotate characters for labels that might not get drawn. 

Well, the character bboxes are really used just for the widths of each
character.  I need the width of each character in order to create the label line
and to rotate and translate the character properly in msDrawTextLineGD(), so I
figured storing them saves recalculating them and may (or may not) be useful in
collision detection.  It would be easy enough to put the angle calculation into
msPolylineLabelPoints() since all the information is available.

It just occured to me that in addition to using the bbox of the entire label
line, it might be possible to simply use the label line itself + a buffer
approximating the bboxes of all characters on the line?  I would think that an
intersection test between the line and the other labels would be more efficient
than checking each bbox.  We know the size of the text, so we could add a buffer
of half that size around the label.  Maybe this is impossible though.

So, how to proceed?  Should I put everything in msPolyineLabelPoints() and cache
the whole shebang?


Benj

[sdlime]

I wanted to save one more thought before I crash... I'll try to merge with
Benj's last post later. I'm thinking:

1) create a new labelPathObj that looks like:

struct {
  multipointObj *path;
  shapeObj *bounds;
  double *angles;
} labelPathObj;

2) do some merging of msPolylineLabelPoints and msDrawTextLineGD, where the
former does the bulk of the work and the latter is primarily a wrapper for
msDrawTextGD. msPolylineLabelPoints produces a labelPathObj (or NULL if we
should fall back on a single label point/angle), and msDrawTextGD consumes one
of those along with the other stuff needed by msDrawTextGD.

3) we add a labelPathObj to the labelCacheMemberObj and pass the labelPathObj
generated by msPolylineLabelPoints into msAddLabel

4) the bounds that is part of the labelPathObj can probably be simplfied into a
single feature by connecting the dots from the corners of each character box
(start at the first character, UL corner and work around counter clockwise).

5) ANGLE FOLLOW implies ANGLE AUTO. That is, if we don't need to follow a path
(e.g. there's one straight segement) then we'd fall back on the current mechanism.

I think all the code is there, just needs a bit of reshuffling.

Reopening...

Steve

[benjcarson@…]

Steve, that sounds good.  I'll give it another go tomorrow.  Sorry for the mixup
with the status there, I had inadvertently changed it when I made that last comment.


Benj

[dmorissette]

Guys, I just realized that before going too far with patches there should be a
RFC for this, documenting the way this will work for users, etc. That's a big
enough enhancement to warrant that.

[benjcarson@…]

Proposed patch for curved text, v2

[benjcarson@…]

v2 Sample output

[woodbri@…]

Benj, Looking very good. I think you need to add a simple check on the rightside
up-ness. For longer curved labels, see Strathearn Crescent NW (right side center
of image), Legislative Building Rd NW (bottom left quardrant) and even 104 St NW
just NE of that should all probably be flipped upside down.

I think a simple algorithm that will scan an polyline and indicate which way is
up for the text. It would be something like this:

foreach segment as s
  v = (0,0,1) X s
  sum (length of s) * sign(Y(v))
end
if sum < 0 then up is -v else up is v

If you apply it to only the sub-segments you think the label will cover you will
get a better answer. This uses simple vector algebra to sum up each segment and
assign a directionality code to it. if the bulk of the distance is pointing
downward then we want to flip it. Let me know if you need help with the code for
this.

[sdlime]

Benj: Looks great. Let me take a look at the more recent patch and then I can
take a crack at the RFC. I'll run it by you for edits...

Steve

[sdlime]

The CVS machine is just back up- power failure. With it down yesterday I didn't 
have a clean build to apply the patch again. Will look at tonite if possible 
and develop the RFC from there.

Steve

[benjcarson@…]

Proposed patch for curved text, v3

[benjcarson@…]

v3 Sample output 1

[benjcarson@…]

v3 Sample output 2

[bill@…]

Here is an independant sample using the patch as of 2/16/06

[benjcarson@…]

Additional minor fixes to previous patch (3 lines of changes)

[sdlime]

I have applied the latest patch to CVS...

Steve

[pspencer@…]

sample of misplaced labels and one kerning problem

[pspencer@…]

some more placement problem ...

[pspencer@…]

some (hopefully useful) feedback in attachments 460 and 461.  I'm seeing quite a few labels offset 
parallel to the feature that the label should be on.  The distance of the offset varies quite widely.  It 
seems to apply only to labels that wouldn't be curved except for one possible difference.

Another effect that is disconcerting is on curves over about 30 degrees, the kerning is insufficient to 
separate the characters and they end up being placed on top of each other.  This effect is worse on 
steeper angles.  This does occur on very shallow angles sometimes (see Victoria Ave and West morland 
Dr in 461).

The final note I would like to make is that there seems to be (sometimes minor) jitter in the baseline 
positioning of the text which results in poor looking text.  I'm not sure what can be done about this, 
but it seems that it should be possible to look at adjacent characters and avoid changing the baseline if 
the following character would be placed at the same position as the preceding character.  Um not sure 
if that makes sense.

[benjcarson@…]

Patch for incorrect label offset

[benjcarson@…]

A brief discussion off-list with Steve Woodbrige identified the issues raised
here by Paul Spencer.  I think I've fixed the offset issue with the previous
patch.  The kerning and jittering issues remain.  Here's my response to Steve's
questions regarding the kerning problems:

"As for improving the kerning between characters, I think the right way to do it
would be to lay out the whole label at once and extract the offsets of each
character.  That would let FreeType (via GD) handle all the kerning pairs
properly for the particular font (and it might even be a little faster, come to
think of it).  Doing this would require using the gdImageStringFTEx()[1]
function however, which currently is not exposed by msGetLabelSize().  Pulling
the offsets out of gdImageStringFTEx() is also a bit of a pain because they are
returned as space-separated numbers in a char* of all things."

Before I go messing up msGetLabelSize(), I'd like to discuss this solution, and
to see if there might be a better way.

The baseline jitter might be fixed by applying a line smoothing algorithm to the
label path.  Some quick googling turned up "McMaster's Slide Averaging
Algorithm" [2] that looks pretty straightforward to implement (it basically 
averages adjacent points).  I may take a crack at it and see if it offers any
improvement.

[1] http://www.boutell.com/gd/manual2.0.33.html#gdImageStringFTEx
[2] http://motiondraw.com/md/as_samples/t/LineGeneralization/demo.html
    http://www.sli.unimelb.edu.au/gisweb/LGmodule/LGSmoothing.htm

[sdlime]

Applied latest patch to CVS HEAD...

Steve

[benjcarson@…]

Patch for label path smoothing and kerning improvements

[pspencer@…]

I've applied the latest patch and I gotta say it looks impressive.  There still seem to be some problems with 
characters running into each when the angle change between characters is larger, but in the general case 
it looks awesome.  I'll try to grab a couple of shots of where I think it could still be improved slightly.

One thing that I thought of was perhaps the inter-character spacing needs to be expanded when the angle 
change is above about 20 degrees.  Not sure if it is possible to do this with the code, but I think it would 
improve this last problem.

[sdlime]

I have applied the latest patch to CVS HEAD. Test away...

Steve

[pspencer@…]

an example some remaining issues on tight curves

[sdlime]

I'm getting segfaults with the patch applied with CVS. I assume all was well 
before hand but I can't be sure without rolling back. Anyone else? Note this is 
without using ANGLE FOLLOW...

Steve

[benjcarson@…]

Heh, whoops:

Line 456 of maplabel.c:

-#elseqq
+#else

My apologies.

[pspencer@…]

Steve, its working for me with both normal and follow labels as far as I can tell (linux box)

[sdlime]

Benj: That fixed it. I do use bitmap fonts in certain places. This is the first 
time I've enabled this on a semi-production application. A couple things I've 
noticed:

  - like Steve said, mindistance doesn't have any effect
  - I do occationally see collisions
  - the density of labels drops a ton, too much in my opinion, between ANGLE 
AUTO and ANGLE FOLLOW (will attach images)
  - I think we really need multiple positions UC, CC and LC. Otherwise you are 
forced to label things right on top of features, obscuring them. That's ok for 
thick roads but not for single width line work (think streams...)

Steve 

[sdlime]

ANGLE FOLLOW with sparse labels

[sdlime]

ANGLE AUTO with denser labels (although uglier)

[woodbri@…]

Steve didn't you have a trick that allowed you to plot the bbox for the labels.
I think that might help with the spare label problem.

With the issue of offsets above/below the line the math is reasonable straight
forward, except at the endpoints. On acute angles you need to trim the path back
to the intersection of the adjacent offsets and in some cases you have to
totally eliminate some segments like in a like shaped like \_/ where you offset
to the interior of the curve. If the offset is great enough the bottom segment
can get eliminated. Then on obtuse angles you need to add additional segments
like in the case of \/ where the offset is on the outside of the curve, you need
to add segments in an arc to connect the two offset line.

The GEOS buffer command already does this, but is expensive and generates the
path all the way around the line like turning the line into a sausage. I think
we should look at the sparseness issue and mindistance first. Then is we have
time tackle the offset problem because this is non-trivial.

Benj, your work is very impressive! Well done!

[benjcarson@…]

Small patch to fix MINDISTANCE

[benjcarson@…]

Labels are suppressed by the algorithm in a couple of cases:

1) If the length of the longest line in the feature is less than min_length.
2) If the feature is degenerate (only one point).
3) If the length of the label is more than 1.5 times the length of the feature.
4) If the angle between two subsequent characters is more than about 80% of 180
degrees.

Checks 1) and 2) are the same as checks in the ANGLE AUTO case so they shouldn't
be the cause of the label sparseness issue.

Check 3) might be the culprit.  It can be bypassed if FORCE is set to true. 
Perhaps try that and see if it increases the number of labels drawn.  I added
this condition because long extrapolated labels didn't look so good.  The
(hardcoded) value of 1.5 was somewhat arbitrary, based on my test cases.  We
could expose the value to users, but I think it would probably be better to find
a value that worked well in the general case.  It's on line 1294 of
mapprimitive.c if you want to play with it and see how it affects the output.

Check 4) attempts to prevent labels from curling overtop of themselves.  It's
not a general self-intersection test (which I figured would be a little too
intensive) but it does eliminate many cases where labels do overlap themselves
(e.g. in a small cul-de-sac).  Again, the value of 80% of 180 was arbitrary and
worked well for me in my test cases, but it can be adjusted if need be.

Anyway, give the latest patch a whirl and let me know how your tests work out.


Benj

[woodbri@…]

Zip file with shapefile of two lines with same name for mindistance test.

[benjcarson@…]

Perfect, thanks Steve.  It looks to me like the latest patch solves the
MINDISTANCE issue.

Thanks,


Benj

[sdlime]

I've applied and committed the latest patch. I need to look at code to comment
more on mindistance and on the collisions I'm seeing. If you want to see a good
bit of data with following on try:

  http://maps.dnr.state.mn.us/landview/experimental/landview.html

Zoom in way tight (set scale to 5000 and click go) in the Twin Cities area
(smaller counties in east central Minnesota) and turn on the road and lakes
layers and look for areas around lakes. We can create a test case for almost any
view. Just note the URL at the bottom of the page. It's URL for the map
displayed in the interface. For example, here's one that shows several collisions:

http://maps.dnr.state.mn.us/cgi-bin/mapserv410?mode=map&map=/usr/local/www/docs_maps/landview/experimental/landview.map&mapext=475740.1319189872+4973313.451250679+476869.02019827644+4974160.117460146&mapsize=640+480&layers=roads+lakes

I can make the streets layer and the lakes layer available for download.

Steve

[benjcarson@…]

I'm not able to reproduce any collisions.  Steve, could you send me the roads
layer and the mapfile you're using for the last example with the collisions?  

Did the last patch fix the mindistance issue for you?

Thanks,


Benj

[sdlime]

Benj: You can download the city streets shapefile at (yes, we named the server 
after you):

  ftp://carson.dnr.state.mn.us/pub/deli/d2162386733064.zip

and the mapfile is at:

  http://maps.dnr.state.mn.us/landview/experimental/landview.map

It's the city streets layers (1 for roadwork and 1 for annotation) that you 
need. Just trim out everything else (sorry about the length). I can't get to 
the font I'm using at the moment but could send that later if necessary.

As for mindistance. Sort of better, but labels still look too close but it's 
not a huge problem.

Steve

[benjcarson@…]

Fix for ANGLE FOLLOW on annotation layers

[sdlime]

I have commited the most recent patch. Perhaps we should close this bug out and
start filling individual bugs now.

Steve

[benjcarson@…]

Opening separate bugs sounds good to me.  This one is getting a little long... 
Please CC me on any new bugs.  Thanks.


Benj

[sdlime]

Marking as closed now, great work Benj! The latest patch does indeed solve the 
collision issues I was seeing so I think all is well.

Steve