unexpected polygon label placement

[dgadoury@…]

When labeling polygons, labels are often placed in unexpected locations
including on the edge or even completely outside the polygon. I will attach two
images to demonstrate.

The first shows Flodida and bordering states, and the FL label falls on the
FL/AL border. AL is not labeled at all even though there would be room for a
label if the FL label was better placed. In this case the label POSITION was set
to CC.

The second image shows Alaska and northwest Canada. The label POSITION in this
case is AUTO and it results in the BC label falling completely outside its
polygon. None of the labels are really where I would want or expect them to be.

From a cartographic viewpoint this is a serious problem.

Chosing a different POSITION may help in this case, but in other areas of the
map it would create new problems. What is really needed is a an assurance that
labels will at least fall completely within the polygon they are associated with.

[dgadoury@…]

image showing FL label

[dgadoury@…]

image showing Alaska & northwest Canada

[sdlime]

Dean: MapServer uses a sampling technique to locate a label point within a 
concave polygon. It's sort of like the scanline conversion algorithm used to 
fill polygons. Polygon label generation works like so:

First, try the center of the polygon bbox, if in the polygon return it. If 
outside then try sampling. Sampling uses scan lines and saves the mid-point of 
the longest scanline. At least that's supposed to be how it works. In the 
Alaska/NW Canada image the NT label is placed based on the bbox, and the BC 
label placed based on the scanline. The Florida map suffers from the scanline 
method, the sampling interval is probably too large. This can be changed in the 
source code.

The fix? Probably involves dumping the bbox, or at least making the test more 
rigorous than simply "in". The scanline conversion method should try to 
maximize distance from the edges of the bbox.

There's not enough time to address for 4.2 but I could have a go for 4.3/4.4 
(which should be release before MUM2).

Steve

[dgadoury@…]

I spoke with one of my instructors from Carleton U about label placement in
polygons and he mentioned two other methods. He offered qbasic code if it would
help.

The first is: Calculate the MBR, find the midpoint in Y, then draw a horizontal
line at that Y from the right side of the polygon to the left. The midpoint in X
of that line should be a reasonably selected centroid or label point. 
* This would work nicely for Florida but not for BC, so I guess this method is
no better than the current method. Both will produce both good and bad results
depending on the shape of the polygon.

Other methods try to fit the largest inscribed circle within the polygon, and
the centre of that circle would be the label point. I don't know the nuts and
bolts of how this would work, and it could be computationally expensive or even
impossible, but it sounds like it might produce good results. I did a quick
semi-freehand rendering of where labels would be placed in Florida and BC using
this kind of a method and the results are good. See the attachments.

[dgadoury@…]

image showing where circle method would place label in FL

[dgadoury@…]

image showing where circle method would place label in BC

[sdlime]

Great! Pass along the code...

Steve

[sdlime]

Dean: Just a reminder to attach the basic code to the bug.

Steve

[dgadoury@…]

Sorry, I missed the last comment. I have emailed Steve Prashker requesting any
code he can supply and as soon as I receive anything I'll attach it here.

[dgadoury@…]

centroid placement code

[dgadoury@…]

Any new ideas or proposals to solve this issue?  

Whenever we try to label polygons and run into this issue we have a tough
decision to make.  We either have to drop the labeling of polygons and give up
some potentially cool styling and info, or We have to live with unruly labels 
(there are just too many features on earth that don't work with the way
MapServer handles polygon labeling ;).

[sdlime]

One additional idea might be to use GEOS to compute centroids for polygons. I'd 
have to do some checking on if it has any options that would be particularly 
helpful for placing labels. It would be expensive and would probably be tunable.

Yet another option is playing with the parameters (e.g. density of polygon 
sampling) that are used when generating a label point. It's possible that 
simply tuning those parameters a bit more might really help. I can point 
someone to the DEFINEs if necessary.

Steve

[dmorissette]

Image showing Monteregie with original BBOX center + scanline algorithms

[dmorissette]

Reassigned bug to myself

[dmorissette]

Image showing Monteregie region with original scanline algo (BBOX center disabled)

[dmorissette]

Image showing Monteregie region with weighted scanline algorithm

[sdlime]

Can we come up with a better way to determine in the bbox result should be used?

Steve

[dmorissette]

mapprimitive.c patch to disable BBOX center and add weight to scanline algorithm

[dmorissette]

> Can we come up with a better way to determine in the bbox result should be used?

One idea I had was to calculate the BBOX of the label inside
msPolygonLabelPoint() and test that all 4 corners lie inside the polygon. That
would at least solve the issues with the labels that overlap with the edges of
their polygon. However that leaves two questions unanswered:

1- Is the point-in-polygon calculation expensive? i.e. if we call that 4 times
then do we rule out any benefit over going straight to the scanline algorithm?

2- The scanline algorithm is almost always going to give better looking results
than the BBOX center even if there is no overlap wth the edge of the polygon. IS
this algorithm that expensive (do we know)? Should we at a minimum offer a
mapfile option to allow users to request the use of the scanline algorithm in
all cases (and bypass the BBOX) if they are willing to swallow the little
performance hit.

[dmorissette]

Setting 5.0 release target milestone

[sdlime]

In the samples the original scanline method (w/BBOX disabled) look better than 
the weighted scanline, are the names reversed?

What about running some timings on label placement simply using the scanline 
method versus the 4.10 method? I would think the scanline method is pretty fast.

Steve

[dmorissette]

No, I don't think they are reversed. Attachment 599 is the image with the
original scanline (w/BBOX disabled), it has two labels that are clipped a the
top of the image. This was fixed in attachment 600 by the weighted scanline
method... the only issue with the weighted scanline is that the Montreal label
is shifted up a little bit, a side-effect of the weighted scanline method.
However it still seems to me that the weighted scanline gives a better result.

Note that the issue with the original scanline resultinng in the two clipped
labels in attachment 599 is not really fixed by the weighted method. We'd really
need to find out why the first scanline is so close to the edge of the image and
fix that, in which case the need for the weighted scanline may be less important
(but probably still benefecial).

[kyngchaos]

A forgotten (mentioned in the original bug report) aspect here of polygon label positioning that's always bothered me - AUTO position for polygons uses the same selection and order of positions as points: only the outer positions. Auto polygon placement should start with CC, then proceed to try the outer positions.

Right now, MS_CC is after the outer positions in MS_POSITIONS_ENUM, which would make this a little messy, but it's doable. But I see that the order of MS_POSITIONS_ENUM really only currently matters for those outer positions, so maybe MS_CC could be moved to the beginning of the enum?

[sdlime]

I fixed this a few months ago in the trunk so this will be in 5.4. If position is AUTO then we get:

Polygons: CC, UC, LC, CL, CR
Lines: UC, LC, CC
Points: UL, LR, UR, LL, CR, CL, UC, LC

Marking this one as fixed.

Steve

[kyngchaos]

Cool.

Any reason for leaving out UR, UL, LR, LL from polygons?

Also, I hope I didn't cause you to close it early - is the CC polygon case (scanline) tested and working?

[sdlime]

The diagonal positions just didn't look great in my testing while the main compass directions weren't too bad. We may allow user specified positions at some point.

The algorithm for polygons was rewritten in early fall and now uses a center of gravity computation along with a few other tricks. The placement is much improved and even a bit faster than before. Ok to close.

Steve