[R] Concave hull

[Corrado Topi]

Dear David and other concave-hull-ists,

yes, I meant concave hulls indeed. I know about the algorithm mentioed 
(www.concavehull.com) but it is not open source, so you cannot integrate it 
in R, and it is apparently patented, so even if you find the description 
you cannot apply it to implement a solution (even if patenting algorithms 
is at least questionable and has a rather patchy validity).

Some questions / comments which applies to David's approach but in general 
even to convex hulls (question 2):

1) How do you extend it to n dimensions (in R)? 2) How do you do "set 
calculus" (horrible expression to mean: union, intersection, difference, 
and particularly membership, and so on ) on these hulls (in R)?

Finally, I am at the moment using a gis to do it, but I did not find any 
command for concave hulls in grass. There is a rather long a convoluted way 
of doing them, but nearly impossible to automatise (see 
http://grass.osgeo.org/wiki/Create_concave_hull). Looking for the 
capability of extending it to the n-dimensional case does not sound right, 
because gis is thought for working in 2d/3d.


Best,


On Nov 26 2009, David Winsemius wrote:

>
>On Nov 25, 2009, at 7:51 PM, David Winsemius wrote:
>
>> Drats; Forgot the plot:
>>
>> xx <- runif(100, -1, 1)
>> yy <- abs(xx)+rnorm(100,0,.2); plot(xx,yy, xlim=c( min(xx)-sd(xx),  
>> max(xx)+sd(xx)), ylim =c( min(yy)-sd(yy), max(yy)+sd(yy)))
>>
>> dens2 <- kde2d(xx, yy, lims=c(min(xx)-sd(xx), max(xx)+sd(xx),  
>> min(yy)-sd(yy), max(yy)+sd(yy) )  )
>> contour(dens2, add=TRUE)
>>> #  You can pick a single contour if you like:
>>>
>> contour(dens2, level=0.05, col="red", add=TRUE)
>> contour(dens2, level=0.10, col="blue", add=TRUE)
>
>And as a further note you can drop the bandwidth and lower the density  
>level to get a tighter fit:
>
>xx <- runif(10000, -1, 1)
>yy <- abs(xx)+rnorm(10000   ,0,.2); plot(xx,yy, xlim=c( min(xx)- 
>sd(xx), max(xx)+sd(xx)), ylim =c( min(yy)-sd(yy), max(yy)+sd(yy)),  
>cex=.2)
>
>dens2 <- kde2d(xx, yy, lims=c(min(xx)-sd(xx), max(xx)+sd(xx), min(yy)- 
>sd(yy), max(yy)+sd(yy) ) , h=c(bandwidth.nrd(xx)/4, bandwidth.nrd(xx)/ 
>4) )
>contour(dens2, add=TRUE)
>#  You can pick a single contour if you like:
>
>contour(dens2, level=0.05, col="red", add=TRUE)
>contour(dens2, level=0.10, col="blue", add=TRUE)
>
>contour(dens2, level=0.005, col="red", add=TRUE)
>
>
>(More bat-like.)
>
>

-- 
Corrado Topi

Global Climate Change & Biodiversity Indicators
Area 18,Department of Biology
University of York, York, YO10 5YW, UK
Phone: + 44 (0) 1904 328645, E-mail: ct529 at york.ac.uk