Label Point of Polygons

Hi, folks-

During the SVG WG F2F in Rigi-Kaltbad, Switzerland, while discussing 
various topics around mapping, we had a diversion into some of the 
problems of labeling [1], including the idea of exposing the centroid of 
a polygon via a keyword and/or API, so authors could use it as a label 
point (among other uses).

But, as noted during that meeting, the centroid is not always a good 
label point, because of what I'll call the "Florida Problem": sometimes, 
the centroid of a shape is outside the boundaries of the shape [2].

There are various ways to improve this. One mapping app (Manifold) 
addresses this by having several different "centroids": Centroids; 
Centroids (Box); Centroids (Inner); and Centroids (Weight) [3]. Each has 
benefits and downsides, which means that none is totally suitable for a 
completely automated solution.

But digging a bit more, I found an alternate model that seems fairly 
robust [4]. Basically, if you find the maximal inscribed circle (i.e., 
the largest circle that will fit into the polygon), the centerpoint of 
that circle will have the best chance of being the ideal label point [5][6].

However, this may (or may not) be computationally expensive... a little 
more digging suggested various techniques for doing this [6], including 
using Voronoi tessellation.

I'm not sure of next steps here, but I thought I'd mention what I found 
so far, in case it inspires someone. I do think this is something that 
could be very useful, and not just for mapping.

Thoughts?

[1] http://www.w3.org/2012/09/19-svg-minutes.html#item07
[2] http://www.georeference.org/doc/images/eg_centroids_inner_02.gif
[3] http://www.georeference.org/doc/transform_centroids.htm
[4] http://trac.osgeo.org/mapserver/ticket/606
[5] http://trac.osgeo.org/mapserver/attachment/ticket/606/fl_circle.png
[6] 
http://stackoverflow.com/questions/3953623/is-there-an-simple-algorithm-for-calculating-maximum-inscribed-circle-into-a-con

Regards-
-Doug

Received on Sunday, 18 November 2012 22:17:21 UTC