[mapserver-dev] Potential GSoC idea was: (Fwd: Re: [mapserver-users] force labels to fit in polygons)

[Stephen Woodbridge]

An interesting potential GSoC project might be something along the line 
of offline label placement optimization. An idea would be to take a 
mapfile and zoom scale then compute the potential label points, bboxs, 
placement options and analyze them for optimal placement and then to 
create a label layer for that scale. To make the task scalable, it could 
be done in tiles.

Anyway, there are probably plenty of scholarly papers on the subject.
https://www.google.com/#q=optimal+label+placement+maps

So my thought is that while the problem is NP hard like TSP, that there 
are good general solutions to TSP that do not provide the best result 
but are provide good results in fast times. One of these algorithms is 
simulated annealing. This works by taking a initial solution, then 
looking for collisions and changing the label point associated with the 
colliding labels. It them scores the solution, makes some random changes 
cleans up the collisions again and compares the new score to the 
previous iteration and if it is better keeps it, and repeats if it is 
worse it resets back to the better solution and does another iteration. 
It does this for some N iterations or until it can not improve on the 
solution.

Interestingly, this [1] paper discusses simulated annealing as part of a 
solution.

Regardless, something like this might be an interesting GSoC project. It 
might be fast enough to run in mapserver may as part of mapcache when 
rendering tiles.

Just an idea,
   -Steve

[1] http://www.eecs.harvard.edu/shieber/Biblio/Papers/tog-final.pdf

-------- Original Message --------
Subject: Re: [mapserver-users] force labels to fit in polygons
Date: Mon, 05 Mar 2012 16:50:42 -0500
From: Stephen Woodbridge <woodbri at swoodbridge.com>
To: mapserver-users at lists.osgeo.org

On 3/5/2012 4:44 PM, Mark Volz wrote:
> Hello,
> Is there a way to force labels to fit inside of a polygon, even if a
> polygon is irregularly shaped? I noticed that with POSITION AUTO labels
> are falling outside of my soils boundary.

The short answer is no. It is an interesting problem, but it does not
have a guaranteed result as the label might be too big to fit
regardless. I am not even sure of the algorithm should be for something
like this. There are a lot of parameters like:

font
font size
wrapping the text
changing the angle
finding the longest line, arc or smooth polyline that fits withing the
polygon and then have the text follow that line

These are all computationally expensive to do on the fly while
rendering. Ideally these should be worked out in advance then you can
supply the attributes to the label via binding columns in the data.

-SteveW
_______________________________________________
mapserver-users mailing list
mapserver-users at lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/mapserver-users