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

RE: Label Point of Polygons

From: David Dailey <ddailey@zoominternet.net>
Date: Sun, 18 Nov 2012 21:36:46 -0500
To: "'Doug Schepers'" <schepers@w3.org>, "'SVG public list'" <www-svg@w3.org>
Message-ID: <000301cdc5fe$b8608230$29218690$@net>
One of my co-authors, Leonard Zusne, wrote a book in the 1960's on the Perception of Form. In it is described the sum of the collective scientific research at the time on the psychophysics vis a vis polygons. There are many ways of characterizing a polygon.

One is much like Fourier analysis -- instead of representing a bivariate function as a summation of sinusoidals, or a curve as its generating function, one represents a two D curve as the summation of its moments. The first central moment, or the center of mass is sort of like a mean. It represents a center of gravity. The second central moment is sort of like a variance. The relationship between these moments and the familiar moments of statistics (mean, variance, skewness, kurtosis, etc.) is pleasant.

Furthermore it was found that in addition to the known physical benefits of the first central moment (the centroid: rotation about the centroid makes sense in many physical models of the universe) these moments also were found to have predictive quality in terms of defining human perception.

Yes there are a zillion ways of talking about centers of sets (consider all the ways that graph theory does it), but the centroid holds a special place in the hearts of physics and the mind. Why not just do it?

David

-----Original Message-----
From: Doug Schepers [mailto:schepers@w3.org] 
Sent: Sunday, November 18, 2012 5:17 PM
To: SVG public list
Subject: Label Point of Polygons

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 Monday, 19 November 2012 02:37:39 GMT

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