unexpected polygon label placement

image showing FL label

image showing Alaska & northwest Canada

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

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.

image showing where circle method would place label in FL

image showing where circle method would place label in BC

Great! Pass along the code...

Steve

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

Steve

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.

centroid placement code

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 ;).

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

Image showing Monteregie with original BBOX center + scanline algorithms

Reassigned bug to myself

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

Image showing Monteregie region with weighted scanline algorithm

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

Steve

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

> 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.

Setting 5.0 release target milestone

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

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).