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.)
______________________________________________
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.