[R] Concave hull

[Barry Rowlingson]

On Wed, Nov 25, 2009 at 11:39 PM, Remko Duursma <remkoduursma at gmail.com> wrote:
> See the function 'convhulln' in the 'geometry' package. It uses this
> algorithm : http://www.qhull.org/

 That looks like a CONVEX hull, the original poster asked about
CONCAVE hulls (and in all CAPS to emphasise this!).

 I've seen various algorithms for generating 'concave hulls' of point
sets, the one that tops google searches is not available in source
code but there is a web applet and set of java class files which
appear to be based on a patented algorithm.

 There's a lot of discussion on algorithms for this, and some
implementations by processing the point data with GRASS. There main
discussion appears to be to first generate the convex hull and then
replace single edges with two edges based on some minimum or maximum
distance criteria...

 Couldn't find an implementation in R or Python though...

Barry