From: Jasper van de Gronde <th.v.d.gronde@hccnet.nl>

Date: Mon, 19 Nov 2012 09:39:30 +0100

Message-ID: <50A9F042.2030601@hccnet.nl>

To: www-svg@w3.org

Date: Mon, 19 Nov 2012 09:39:30 +0100

Message-ID: <50A9F042.2030601@hccnet.nl>

To: www-svg@w3.org

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

*
This archive was generated by hypermail 2.3.1
: Wednesday, 7 January 2015 15:29:52 UTC
*