[R-sig-Geo] Better label placement for polygons

[Karl Ove Hufthammer]

to. den 19. 07. 2012 klokka 17.16 (+0100) skreiv Barry Rowlingson:
> Nice, is it the same method as this:
> 
> http://proceedings.esri.com/library/userconf/proc01/professional/papers/pap388/p388.htm

No. As I wrote, I was inspired by the above paper, and the algorithms
are similar (i.e., they are both based on using a negative buffer), but
they are not identical. In the above paper, compactness and
rectangularity is used as a stopping criterion, or area size if
compactness and rectangularity is not achieved, while the R code instead
looks at the convex hull of the polygon buffer and checks if this is
contained in the original polygon.

I had originally planned to just increase the buffer width until the
resulting polygon was tiny (i.e., check if gArea(poly.buffer) /
gArea(poly.orig) was very small but positive), and while this often
works, it turned out that it sometimes creates very bad solutions. One
example would be a polygon similar to the the top-left polygon at
  http://huftis.org/kritikk/polygon-labels.png
As we increase the buffer width, the resulting polygon becomes a wide,
narrow rectangle in the left part of the polygon. Now, if the original
polygon is modified to contain a small notch (like this ---^---) at
the top, the rectangle will shrink to a small area positioned *right
below* the notch, i.e., possibly far from the *middle* of the large left
area, which is the natural label position. That’s why I figured it would
be better to instead have as *small* a buffer width as possible that
still satisfies the convex hull criterion. This should always generate
*reasonable* label positions (though there are probably exceptions I
didn’t think of :) ).

-- 
Karl Ove Hufthammer
http://huftis.org/
Jabber: karl at huftis.org