#606 closed defect (fixed)
unexpected polygon label placement
Reported by: | Owned by: | dmorissette | |
---|---|---|---|
Priority: | high | Milestone: | 5.4 release |
Component: | MapServer C Library | Version: | 4.1 |
Severity: | normal | Keywords: | |
Cc: | warnock@… |
Description (last modified by )
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.
Attachments (9)
Change History (30)
by , 20 years ago
Attachment: | cc_labels.png added |
---|
comment:1 by , 20 years ago
Cc: | added |
---|---|
Component: | Build Problems → MapServer C Library |
comment:2 by , 20 years ago
Status: | new → assigned |
---|
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
comment:3 by , 20 years ago
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.
by , 20 years ago
Attachment: | fl_circle.png added |
---|
image showing where circle method would place label in FL
by , 20 years ago
Attachment: | bc_circle.png added |
---|
image showing where circle method would place label in BC
comment:6 by , 20 years ago
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.
comment:7 by , 19 years ago
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 ;).
comment:8 by , 19 years ago
Cc: | added |
---|
comment:9 by , 19 years ago
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
by , 17 years ago
Attachment: | bug606.gif added |
---|
Image showing Monteregie with original BBOX center + scanline algorithms
comment:10 by , 17 years ago
Cc: | added |
---|---|
Owner: | changed from | to
Status: | assigned → new |
Reassigned bug to myself
by , 17 years ago
Attachment: | bug606b.gif added |
---|
Image showing Monteregie region with original scanline algo (BBOX center disabled)
by , 17 years ago
Attachment: | bug606c.gif added |
---|
Image showing Monteregie region with weighted scanline algorithm
comment:11 by , 17 years ago
Can we come up with a better way to determine in the bbox result should be used? Steve
by , 17 years ago
Attachment: | bug606.patch added |
---|
mapprimitive.c patch to disable BBOX center and add weight to scanline algorithm
comment:12 by , 17 years ago
Status: | new → assigned |
---|
> 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.
comment:14 by , 17 years ago
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
comment:15 by , 17 years ago
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).
comment:16 by , 17 years ago
Description: | modified (diff) |
---|---|
Milestone: | 5.0 release → 5.2 release |
comment:17 by , 16 years ago
Milestone: | 5.2 release → 5.4 release |
---|
comment:18 by , 15 years ago
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?
comment:19 by , 15 years ago
Resolution: | → fixed |
---|---|
Status: | assigned → closed |
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
comment:20 by , 15 years ago
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?
comment:21 by , 15 years ago
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
image showing FL label