Re: Label Point of Polygons

On Sun, Nov 18, 2012 at 2:17 PM, Doug Schepers <schepers@w3.org> 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.
>
> 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.

Thanks for looking into this!

As far as I can tell, this is exactly the solution that I posited at
the meeting (and perhaps others did too?  it was a brainstorm-y time,
I don't recall exactly who had the ideas) - a good "central" point
could be found by expanding the stroke of the shape: the last point in
the fill to not be covered by the stroke is a "central" point.

Rephrased, this is the point farthest away from any edge, which is
equivalent to the center of the maximal inscribed circle.

It's promising that other people have come up with similar solutions
to the problem, and that Voronoi diagrams may be a relatively
efficient solution to the problem.  I haven't dug deeply into the
Voronoi links yet.

~TJ

Received on Sunday, 18 November 2012 22:44:08 UTC