W3C home > Mailing lists > Public > www-svg@w3.org > November 2012

Label Point of Polygons

From: Doug Schepers <schepers@w3.org>
Date: Sun, 18 Nov 2012 17:17:13 -0500
Message-ID: <50A95E69.2070507@w3.org>
To: SVG public list <www-svg@w3.org>
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 GMT

This archive was generated by hypermail 2.3.1 : Friday, 8 March 2013 15:54:52 GMT