Re: Label Point of Polygons

On 18-11-12 23:17, Doug Schepers wrote:
> ...
> 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.
> ...

For people working on discrete grids I would suggest a different method.
There are very efficient algorithms for computing the Euclidean distance
transform on a binary image (think coverage image of the polygon). The
spot you're looking for would be the maximum value in the distance
transform. This would mean no messing with tricky Voronoi stuff, just
walk over the image two times or so, and you've got it.

In fact, there is even a good chance that the above scheme could be
modified to give the best position to fit a certain bounding box. If
you're interested I can take a closer look. (This is very much related
to mathematical morphology, which is what my PhD is about.)

The main problem with this approach in general is that there might not
be one unique point that is the "best". Even worse, whether you're using
a distance transform or a Voronoi diagram, due to numerical problems
different implementations might find different "best" points. A simple
example of a shape that would be problematic is a rotated rectangle. In
principle, there should be a whole line of "best" points, but due to
slightly different rasterizations and/or numerics in computing the
locations of the best point(s), different implementations could easily
find different (sets of) best points.

Received on Monday, 19 November 2012 08:40:01 UTC