[R] Concave hull

[Duncan Murdoch]

On 26/11/2009 4:02 AM, Corrado Topi wrote:
> 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.

I don't see a clear definition of what a concave hull should be, but the 
following version of the algorithm above looks automatisable, if slow on 
big sets:

Generate all pairwise distances, and generate the undirected graph 
formed of edges below a certain length threshold.

Take each connected component of that graph, and discard any internal 
points and edges.  (An "internal edge" is one whose midpoint is in the 
interior of a polygon formed by other edges in the graph.  I'd build it 
up by starting with an arbitrary pair of points and growing from there.)

Duncan Murdoch

> 
> 
> 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.)
>>
>>
>