# 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 UTC

This archive was generated by hypermail 2.3.1 : Wednesday, 8 March 2017 09:47:30 UTC