# How are labels dynamically placed on a line or polygon?

I was wondering if anyone knew the math involved, or resources for learning the math involved, in finding the ideal position, scale, and rotation of a label for a line or polygon on a map?

The most I've got so far is finding the centroid for a polygon (though it's not ideal for concave polygons).

-
I guess it is best to do this manually. – Jonas Jul 23 '10 at 16:12
Related resource: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.8844 The Computational Complexity of Cartographic Label Placement. Citation includes other associated references. – glennon Jul 30 '10 at 0:11

Centroid is never the answer but it is a good initial guess. The algorithms which are easiest to implement that solve similar problems usually operate by trying a few reproducible pseudorandom positions and scoring them somehow, keeping the best spots. For further reading I would start by reading up on bin packing algorithms and take it from there.

-

A research paper that addresses this hard issue: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4015429

-

Maybe the documentation of the PAL labeling library is a good start for further research. I especially recommend "From Point Feature Label Placement to Map Labelling".

-

Labeling is a nasty endeavor.

At a small scale: you have label overlap problems, so which one do you remove or should all be shown.

At a large scale: if you have a large polygon, where do you display the label. Do you display it multiple times.

-

I've seen maps where they just calculate a bounding box for a complex polygon and place the label in the center of that.

For simple lines, usually it's just the middle of the two endpoints.

I guess it really just depends on what you expect your data to be and how important the location of the label is.

-
What's up with the downvote? A comment might be useful. – Jon Bringhurst Jul 29 '10 at 23:46

You can inspect the code in GeoTools and GeoServer if you grok java - it is a constantly evolving problem as people keep coming up with new corner cases that need fixing.

-