Bad 'angle follow' case -- possibly a use for splining

[tbonfort]

Reporter: crschmidt Date: 2007/08/10 - 02:48 http://boston.freemap.in/bugs/2221/poor_follow.png Uses:

http://boston.freemap.in/bugs/2221/poor-follow.map

All data in:

http://boston.freemap.in/bugs/2221/

Command used:

shp2img -m poor-follow.map -o poor_follow.png -e 232376.94043 900487.441406 232524.42627 900634.927246 -l roads_3_1

Discussion on IRC:

20:24:28 < hobu> Someone needs to do some splining
20:24:29 < crschmidt> Should I bother to file it as a bug?
20:25:06 < hobu> You could file an enhancement for 5.2 that says, 'we should improve ANGLE FOLLOW to support simple interpolation methods like splining for degenerative cases"
20:25:24 < hobu> It's way too big to be dealt with in the throws of our 5.0 release right now though
20:25:40 < crschmidt> understood
20:25:46 < crschmidt> Just wasn't sure if it was worth filing at all
20:26:19 < hobu> Another thing about the splining is we could maybe take advantage of it for feature rendering as well
20:26:38 < hobu> something those paleogeographers do from time to time ;)
<crschmidt> what is that?
<crschmidt> straightening out of too-curvy borders?
<hobu>  smoothen disjointed ones. They add map noise for very little information
* crschmidt nods
<crschmidt> something like what a simplification algorithm would do
<crschmidt> only automatic/built into the rendering?
<hobu>  right, except not one that has to preserve topological relationships
<hobu>  http://en.wikipedia.org/wiki/B-spline
<hobu>  Would be a simple approach
<hobu>  Maybe you'd tell the mapserver renderer, 'hey, use 6-8 consequtive vertices to calculate your splines, if the incident angle is less than x degrees"
<hobu>  or something like that ;)
<hobu>  It'd be spendy, for sure
<hobu>  and not very useful for Manhattan grid systems :)

[tbonfort]

Author: sdlime Date: 2008/05/16 - 05:44 I know I won't get to this in the next couple of weeks unless I or someone else has an epiphany of sorts. It would be excellent to fix but it's not one that can be banged out in a few hours.

Steve

[tbonfort]

Author: sdlime Date: 2009/09/02 - 05:38 Daniel/Alan: This is a bug I was wondering if Alan could take a look at for 5.6. Chris' links don't work anymore although I still have a copy of his mapfile and data if you'd like. The problem is basically curved labels in tight spaces. In these instances characters can overlap. I'll forward some discussion I had with Steve W. on the subject. I did spend some time on the problem but didn't get far. The curved label placement code is not easy to understand (at least for me).

Steve

[tbonfort]

Author: aboudreault Date: 2009/09/02 - 15:28 Steve, I'll take a look at this bug as soon as I can. Please, forward me the discussion you Had with Steve W. and the mapfile/data to reproduce the bug.

[tbonfort]

Author: sdlime Date: 2009/09/07 - 16:51 For completeness here's a very short thread Steve W. and I had... Steve

---

Stephen Lime wrote:

Hi Steve: Since you were behind some of the thinking about the original path following labels I figured I'd ping you for ideas on how to deal with the overlap problem on tight curves. I've attached a test image that shows the problem but I'm sure you've seen it yourself. I figure there are a couple of strategies: 1) somehow increase smoothing 2) somehow adjust between character spacing 3) move the location of the label anchor point 4) punt This of course all depends on being able to detect overlap and I'm not sure that can be done reliably using character bounding boxes. It's quite common for those to overlap but the characters don't. Thomas, I cc'd you since AGG might present alternatives to the current process... Steve

There are a few ideas for dealing with this:

1) change the spacing algorithm if the curvature (3rd derivative) is greater then some constant or use a proportion of the curvature as a factor in the spacing algorithm. This would act to dynamically increase the spacing in tight curvature areas. It also depends if the text is being draw on the inside of the curve or the outside of the curve. You might want to close up the spacing is it is on the outside.

2) I would not throw out the bbox tests, you might not want to use them all the time, but they might help in these tight situations if you can easily determine when to use them and when not.

3) If we had the raster based label collision detection that I described for the label cache processing, that could easily be applied here on a char by char basis to detect these collisions. Granted it would not be blinding fast, but combined with a turn it on when tight and off when not switch, like above, I think it would be fast enough and it would generate good results. It would also work for the multiple character cases (as opposed to only the adjacent character case. ie: if you have a long label that loops back on itself, and there are collision between the 3,4 char and the 10,11,12 chars, then you would detect this and could add spacing to avoid this.

As I mention in the original post about the raster based collision detection, that if you had a path, that you could iterate the label positioning along the path to find a clear space for it. I guess the question becomes how often would you do this and how expensive would it be, so it is probably out of scope without some experimentation.

I would love it if you or Thomas were interested in work on the raster based collision detection and label case processing.

I hope this helps. I would be happy to discuss any path you might want to pursue to mitigate this issue.

-Steve (Woodbridge)

[tbonfort]

Author: aboudreault Date: 2009/09/18 - 16:00 May anyone attach a small data set to reproduce that bug?

[tbonfort]

Author: sdlime Date: 2009/09/18 - 21:03 My bad, I have one and will pass it along as soon as I get home...

Steve

[tbonfort]

Author: aboudreault Date: 2009/09/28 - 18:30 Last week, I investigate in that ticket. I thought that it would be possible to modify the current label path algorithm and adjust the letterspacing in case of collision. I successfully detected all chars that were in collision with the previous char. Unfortunately, I cannot detect collisions at any place in the algorithm, and where I can.... I cannot change the letterspacing (Because the label points are already all calculated). The only thing I could do now, would be to detect if the label contains collisions, and recall the entire label path algorithm with an extra letterspacing in pourcentage per example. Since there are a lot of collisions, I don't think this would be a good option. I'm a little bit confused about what could I try now. I'm wondering if someone else could suggest me something.

[tbonfort]

Author: sdlime Date: 2009/09/28 - 18:57 Perhaps we could offer a few configurable options?

1 - bail if collision is detected, skip this label (that fixes the problem!) 2 - redo label with new letter spacing (only do this n times before bailing) 3 - adjust letter spacing within a label, that is move the next character so there's no collision and then return the letter spacing to normal for subsequent chars (I'd be curious how that looks visually) 4 - redo label with a new starting position and same letter spacing (again, only do this n times, kinda like auto placement for labels around points)

What about modifying the feature being labeled, smooth it, perhaps by dropping vertices?

I've added Steve W. since he'll probably have better ideas...

Steve

[tbonfort]

Author: aboudreault Date: 2009/09/28 - 19:44 Replying to [comment:10 sdlime]:

Perhaps we could offer a few configurable options?

1 - bail if collision is detected, skip this label (that fixes the problem!)[[BR]][[BR]]

Too many labels would be skipped. In some case, even a small angle can provoke a collision, maybe on only 1 char, but there is a collision.

2 - redo label with new letter spacing (only do this n times before bailing) [[BR]]

My concern is: applying a non-dynamic letterspacing to a label could be very not nice visually, because there are often char collisions.

3 - adjust letter spacing within a label, that is move the next character so there's no collision and then return the letter spacing to normal for subsequent chars (I'd be curious how that looks visually)[[BR]]

That's what I was trying to do and haven't been able to do so in the algorithm.

4 - redo label with a new starting position and same letter spacing (again, only do this n times, kinda like auto placement for labels around points)

What about modifying the feature being labeled, smooth it, perhaps by dropping vertices?

I have no idea what would be the result of that... I thinkg a b-spline could fix properly the char collisions in some cases... but in not all. (Depends of the angle). It would be something to experiment.

I've added Steve W. since he'll probably have better ideas...

Steve

[tbonfort]

Author: woodbri Date: 2009/09/28 - 21:02 A couple of points that come to mind.

• we should anticipate the we will always have cases that will have collisions and should have a strategy(s) for dealing with that. These might be:
  • bail on the label,
  • redo with new label point,
  • redo with new spacing fator,
  • others
• and we should anticipate the some labels will never look good because some roads represent the degenerate corner case
• I think the algorithm that seems to make sense to me is if the current character collides with the previous add spacing up to some max amount. If the max is hit then redo the last character and increase its spacing by 40-50% and then continue. The ideas is to push the previous character along the curve and hopefully the next will fit better. If it fails a second time, follow the collision strategy whatever that might be.
• splines could be used to smooth out a twisty road, but the label would then only approximate the path of the road and a long name might obliterate the street under the label. I guess I would like to see how it looks. Does anyone know of another product that uses splines, it seems like a lot of work for something that may/may not look good.
• since we have OpenGL and other ports in the works, I guess I would ask is these have spline support for labels and it would be more trivial to prototype splines in one of the sandboxes?

[tbonfort]

Author: dmorissette Date: 2009/09/28 - 21:15 Alan already tried implementing your 3rd suggestion (if char collides, add spacing until it fits or you hit some predefined max), but given the way the rest of the algorithm works, it's not possible/simple to change the algorithm to do that (a line smoothing kernel is applied in the loop and that complicates things). We'd need advice from tbonfort before changing things this way.

[tbonfort]

Author: aboudreault Date: 2009/09/29 - 00:03 tbonfort told me that he didn't play in that part of the code, so cannot say any quick advice. I will continue to work on this tomorrow and see if I couldn't optimize the label path redo with a few conditions or something.[[BR]] Thanks for your suggestions.

[tbonfort]

Author: sdlime Date: 2009/09/29 - 00:22 Correct, Thomas had nothing to do with this code. It was "donated" by a now unreachable developer. The smoothing kernel is the biggest mystery to me, I'm not sure how or why it works.

Steve

[tbonfort]

Author: aboudreault Date: 2009/10/05 - 20:32 After further investigation, I haven't been able to get nice results. For a few cases, the results was correct.... but others was terrible. What I tried to do: modify the '''current algorithm''' and adjust the letter spacing depending on chars collisions. Here's the problem I noticed with that option:

• Since the algorithm doesn't allow to adjust the letterspacing dynamically, We need to redo totally the label path algorithm with adjusted settings.
• A shapeObj have to be constructed and msIntersectPolygon called to properly detect chars collisions.
• Adjusting the letterspacing is not really safe. The char, which letterspacing have been modified, can now be positioned on the next segment if it doesn't fit on the original one. That do produces bad results because if a char positioning changes... that means that mostly all others chars moved too and their letterspacing may have to be recalculated.

I haven't done any performance tests, but seeing how many collision tests and algorithm redo are done (in the log file), I think this option is not the right approach.[[BR]]

In the hope that my understanding of the label placement algorithm is good enough, I don't think we can get very nice results without drastically affect the performance by trying to modify the current algo with ''minor'' changes. That said, since I do not want to do ''major'' changes in the algorithm and break 5.6, I would say the the algorithm should be reviewed and maybe totally modified in the future (6.0 ?). What's your thought?

[tbonfort]

Author: woodbri Date: 2009/10/05 - 20:52 Alan,

You assessment sounds reasonable to me. Since you are probably the "expert" at the moment on that algorithm, I would certainly support your recommendation that we protect 5.6 release and put the algorithm up for review in a future rev.

If we could convert the polyline to a bezier spline that has a tightness that makes if replicate the polyline, it might significantly simplify the placement of the chars as the segments would all appear to be on a single spline segment and you could avoid the complications of backtracking over multiple segments. The biggest issue with bezier splines and b-splines is that they require a lot of numerical lifting and it might be slow(-ish).

[tbonfort]

Author: woodbri Date: 2009/10/05 - 21:09 Actually I misspoke above I meant to say NURBS not Bezier curves. See http://en.wikipedia.org/wiki/NURBS and I one degrees NURB is a polyline.

[tbonfort]

Author: dmorissette Date: 2009/10/05 - 23:14 I agree that we should revisit this in 6.0, and possibly significantly rework the algorithm at that time. However we need to keep performance in mind, or at a minimum have a lite option for those concerned with performance.

[tbonfort]

Author: woodbri Date: 2010/08/16 - 16:49 It looks like geoserver detects the collision and just bails on that label. This has the advantage that another label in close proximity to what would have been a bad label is not bumped by that and a good label is placed near by.

I think this is a good approach to start with. And alternative would be to move along the polyline line and look for a straighter segment that is long enough to handle the label length.

[tbonfort]

Author: aboudreault Date: 2010/08/16 - 16:56 Jeff, could you attach a test case that produce the image you sent earlier?

[tbonfort]

Author: jmckenna Date: 2010/08/16 - 19:02 Test case for angle follow with contours: http://download.osgeo.org/mapserver/tickets/ticket2221.zip (500 KB)

[tbonfort]

Author: jmckenna Date: 2010/08/20 - 19:10 Alan did you try my test case?

[tbonfort]

Author: aboudreault Date: 2010/08/20 - 19:38 yes jeff, thanks! I've began a few collisions tests and will see what's happen.

[tbonfort]

Author: dmorissette Date: 2010/08/25 - 22:12 Looking at the attachment poor-follow-with-nodes.gif I don't understand why/how the "W" and the "a" can overlap so much since they are at about the same angle. The source data was missing from the 2221.demo.tar.gz attachment so I tried to get the original data to reproduce this (crschmidt pointed out it came from http://www.mass.gov/mgis/ftpeotroads.htm)

I downloaded the data from MassGIS (EOTROADS.EXE), since it's a 500MB shapefile, I extracted the relevant subset corresponding to the bbox of the testcase and repackaged the it as 2221.demo.v2.tar.gz which I will attach in a minute.

Then I tried the shp2img command quoted in the opening comment of this ticket and get a different result which I will attach as poor_follow2.png. Notice the street at the location of the "Wa" of Waverly in poor-follow-with-nodes.gif has a rounded corner, but in poor_follow2.png we have the intersection of two straight lines (not rounded), one corresponding to Henry Street (left) and the other Waverly Street (right). So it seems that the vector data differs and we have no way to reproduce the original issue. If someone still has it then please share it.

[tbonfort]

Author: dmorissette Date: 2010/08/25 - 22:27 Since this ticket (#2221) is about improving labels using line smoothing (using b-spline or other methods), I created a new ticket #3523 about the option that was discussed here of adding the ability to skip labels in which characters overlap too much (such as when labeling contours).

[tbonfort]

Author: aboudreault Date: 2011/02/23 - 21:14 The RFC-60 adds the ability to skip angle follow labels with too much character overlap. See ticket #3523.