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

[Stephen Woodbridge]

Seems like someone has done some work on this for OpenStreetMap
http://wiki.openstreetmap.org/wiki/User:Esscue/Labelling

On 3/5/2012 5:31 PM, Stephen Woodbridge wrote:
> 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
> _______________________________________________
> mapserver-dev mailing list
> mapserver-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/mapserver-dev