

Dear friends,
Do you know how to calculate the CONCAVE hull of a set of points (2
dimensional or ndimensional)? is that possible in R? (With a "smoothing"
parameter of course).
Best,

Corrado Topi
Global Climate Change & Biodiversity Indicators
Area 18,Department of Biology
University of York, York, YO10 5YW, UK
Phone: + 44 (0) 1904 328645, Email: [hidden email]
______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/rhelpPLEASE do read the posting guide http://www.Rproject.org/postingguide.htmland provide commented, minimal, selfcontained, reproducible code.


See the function 'convhulln' in the 'geometry' package. It uses this
algorithm : http://www.qhull.org/remko

Remko Duursma
PostDoctoral Fellow
Centre for Plants and the Environment
University of Western Sydney
Hawkesbury Campus
Richmond NSW 2753
Dept of Biological Science
Macquarie University
North Ryde NSW 2109
Australia
Mobile: +61 (0)422 096908
www.remkoduursma.com
On Thu, Nov 26, 2009 at 3:37 AM, Corrado < [hidden email]> wrote:
> Dear friends,
>
> Do you know how to calculate the CONCAVE hull of a set of points (2
> dimensional or ndimensional)? is that possible in R? (With a "smoothing"
> parameter of course).
>
> Best,
> 
> Corrado Topi
>
> Global Climate Change & Biodiversity Indicators
> Area 18,Department of Biology
> University of York, York, YO10 5YW, UK
> Phone: + 44 (0) 1904 328645, Email: [hidden email]
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/rhelp> PLEASE do read the posting guide http://www.Rproject.org/postingguide.html> and provide commented, minimal, selfcontained, reproducible code.
>
______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/rhelpPLEASE do read the posting guide http://www.Rproject.org/postingguide.htmland provide commented, minimal, selfcontained, reproducible code.


On Wed, Nov 25, 2009 at 11:39 PM, Remko Duursma < [hidden email]> 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
______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/rhelpPLEASE do read the posting guide http://www.Rproject.org/postingguide.htmland provide commented, minimal, selfcontained, reproducible code.


Oh right.... I think I did not catch that *because of* the caps. Sorry.
r

Remko Duursma
PostDoctoral Fellow
Centre for Plants and the Environment
University of Western Sydney
Hawkesbury Campus
Richmond NSW 2753
Dept of Biological Science
Macquarie University
North Ryde NSW 2109
Australia
Mobile: +61 (0)422 096908
www.remkoduursma.com
On Thu, Nov 26, 2009 at 10:51 AM, Barry Rowlingson
< [hidden email]> wrote:
> On Wed, Nov 25, 2009 at 11:39 PM, Remko Duursma < [hidden email]> 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
>
______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/rhelpPLEASE do read the posting guide http://www.Rproject.org/postingguide.htmland provide commented, minimal, selfcontained, reproducible code.


This is not a true convave hull, but a 2D density is something similar
and perhaps more "statistical":
library(MASS)
xx < runif(100, 0, 1)
xx < runif(100, 1, 1)
yy < abs(xx)+rnorm(100,0,.2)
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)
Happy Valentine's

David
On Nov 25, 2009, at 11:37 AM, Corrado wrote:
> Dear friends,
>
> Do you know how to calculate the CONCAVE hull of a set of points (2
> dimensional or ndimensional)? is that possible in R? (With a
> "smoothing"
> parameter of course).
>
> Best,
> 
> Corrado Topi
>
> Global Climate Change & Biodiversity Indicators
> Area 18,Department of Biology
> University of York, York, YO10 5YW, UK
> Phone: + 44 (0) 1904 328645, Email: [hidden email]
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/rhelp> PLEASE do read the posting guide http://www.Rproject.org/postingguide.html> and provide commented, minimal, selfcontained, reproducible code.
David Winsemius, MD
Heritage Laboratories
West Hartford, CT
______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/rhelpPLEASE do read the posting guide http://www.Rproject.org/postingguide.htmland provide commented, minimal, selfcontained, reproducible code.


Drats; Forgot the plot:
xx < runif(100, 0, 1)
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)
On Nov 25, 2009, at 7:46 PM, David Winsemius wrote:
> This is not a true convave hull, but a 2D density is something
> similar and perhaps more "statistical":
>
> library(MASS)
> xx < runif(100, 0, 1)
> xx < runif(100, 1, 1)
> yy < abs(xx)+rnorm(100,0,.2)
> 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)
>
>
> Happy Valentine's
> 
> David
>
> On Nov 25, 2009, at 11:37 AM, Corrado wrote:
>
>> Dear friends,
>>
>> Do you know how to calculate the CONCAVE hull of a set of points (2
>> dimensional or ndimensional)? is that possible in R? (With a
>> "smoothing"
>> parameter of course).
>>
>> Best,
>> 
>> Corrado Topi
>>
>> Global Climate Change & Biodiversity Indicators
>> Area 18,Department of Biology
>> University of York, York, YO10 5YW, UK
>> Phone: + 44 (0) 1904 328645, Email: [hidden email]
>>
>> ______________________________________________
>> [hidden email] mailing list
>> https://stat.ethz.ch/mailman/listinfo/rhelp>> PLEASE do read the posting guide http://www.Rproject.org/postingguide.html>> and provide commented, minimal, selfcontained, reproducible code.
>
> David Winsemius, MD
> Heritage Laboratories
> West Hartford, CT
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/rhelp> PLEASE do read the posting guide http://www.Rproject.org/postingguide.html> and provide commented, minimal, selfcontained, reproducible code.
David Winsemius, MD
Heritage Laboratories
West Hartford, CT
______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/rhelpPLEASE do read the posting guide http://www.Rproject.org/postingguide.htmland provide commented, minimal, selfcontained, reproducible code.


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

David.
>
>
>
> On Nov 25, 2009, at 7:46 PM, David Winsemius wrote:
>
>> This is not a true convave hull, but a 2D density is something
>> similar and perhaps more "statistical":
>>
>> library(MASS)
>> xx < runif(100, 0, 1)
>> xx < runif(100, 1, 1)
>> yy < abs(xx)+rnorm(100,0,.2)
>> 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)
>>
>>
>> Happy Valentine's
>> 
>> David
>>
>> On Nov 25, 2009, at 11:37 AM, Corrado wrote:
>>
>>> Dear friends,
>>>
>>> Do you know how to calculate the CONCAVE hull of a set of points (2
>>> dimensional or ndimensional)? is that possible in R? (With a
>>> "smoothing"
>>> parameter of course).
>>>
>>> Best,
>>> 
>>> Corrado Topi
>>>
>>> Global Climate Change & Biodiversity Indicators
>>> Area 18,Department of Biology
>>> University of York, York, YO10 5YW, UK
>>> Phone: + 44 (0) 1904 328645, Email: [hidden email]
>>>
>>> ______________________________________________
>>> [hidden email] mailing list
>>> https://stat.ethz.ch/mailman/listinfo/rhelp>>> PLEASE do read the posting guide http://www.Rproject.org/postingguide.html>>> and provide commented, minimal, selfcontained, reproducible code.
>>
>> David Winsemius, MD
>> Heritage Laboratories
>> West Hartford, CT
>>
>> ______________________________________________
>> [hidden email] mailing list
>> https://stat.ethz.ch/mailman/listinfo/rhelp>> PLEASE do read the posting guide http://www.Rproject.org/postingguide.html>> and provide commented, minimal, selfcontained, reproducible code.
>
> David Winsemius, MD
> Heritage Laboratories
> West Hartford, CT
>
David Winsemius, MD
Heritage Laboratories
West Hartford, CT
______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/rhelpPLEASE do read the posting guide http://www.Rproject.org/postingguide.htmland provide commented, minimal, selfcontained, reproducible code.


Dear David and other concavehullists,
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 ndimensional 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 batlike.)
>
>

Corrado Topi
Global Climate Change & Biodiversity Indicators
Area 18,Department of Biology
University of York, York, YO10 5YW, UK
Phone: + 44 (0) 1904 328645, Email: [hidden email]
______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/rhelpPLEASE do read the posting guide http://www.Rproject.org/postingguide.htmland provide commented, minimal, selfcontained, reproducible code.


On 26/11/2009 4:02 AM, Corrado Topi wrote:
> Dear David and other concavehullists,
>
> 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 ndimensional 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 batlike.)
>>
>>
>
______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/rhelpPLEASE do read the posting guide http://www.Rproject.org/postingguide.htmland provide commented, minimal, selfcontained, reproducible code.


Raising a rather general question here.
This is a tantalising discussion, but the notion of "concave hull"
strikes me as extremely illdefined!
I'd like to see statement of what it is (generically) supposed to be.
The examples discussed so far seem to rely on a person's inner
feelings of what it is supposed to be.
Consider the following simple example (where I have drawn a "concave
hull" by hand, using sentimental criteria).
set.seed(54321)
X < c(1+rnorm(10),1+rnorm(10))
Y < rnorm(20)
plot(X,Y,pch="+",col="blue",xlim=c(4,4),ylim=c(3,3))
for(i in (1:20)) text(X[i]+0.150,Y[i],i,cex=0.25)
## Find their convex hull:
ix0 < chull(X,Y) ; n < length(CH.ix0)
ix1 < c(ix0,ix0[1]) # close it
lines(X[ix1],Y[ix1],col="green")
## Draw a "concave hull":
concix < c(19,18,8,16,11,1,3,2,4,7,15,5,10,9,14,13,20,12,17,19)
lines(X[concix],Y[concix],col="red")
I have deliberately left the single point 6 "dangling", since
I am agonising over the choice between:
[A] Leaving it as it is, as in interior point, on the grounds
that the resulting "concave hull" boundary is fairly smooth;
[B] Inserting it between c( ... ,2,4,7,6,15, ... ), which is
the "least uncomfortable" of the two obvious possibilities;
[C] Inserting it between c( ... ,2,4,6,7,15, ... ), which is
the "more uncomfortsable" of the two onvious possibilities.
Can someone provide counselling for me? I am hearing too many
voices about this!
Should I have tried to be less inclusive?
Ted.

EMail: (Ted Harding) < [hidden email]>
Faxtoemail: +44 (0)870 094 0861
Date: 26Nov09 Time: 20:52:03
 XFMail 
______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/rhelpPLEASE do read the posting guide http://www.Rproject.org/postingguide.htmland provide commented, minimal, selfcontained, reproducible code.


2009/11/26 Ted Harding < [hidden email]>:
> Raising a rather general question here.
>
> This is a tantalising discussion, but the notion of "concave hull"
> strikes me as extremely illdefined!
>
> I'd like to see statement of what it is (generically) supposed to be.
I'm curious too, but I can imagine the following definition,
Consider a sphere (ndimensional maybe) that we let come in contact
with the scatter of points from outside. The set of points that the
sphere can attain may define unambiguously (I think) a concave hull,
for a specified sphere radius. The convex hull is obtained in the
limit of infinite radius (plane).
It's probably not exactly this, but I guess that's the rough idea.
Just a thought,
baptiste
______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/rhelpPLEASE do read the posting guide http://www.Rproject.org/postingguide.htmland provide commented, minimal, selfcontained, reproducible code.


On 26Nov09 21:11:02, baptiste auguie wrote:
> 2009/11/26 Ted Harding < [hidden email]>:
>> Raising a rather general question here.
>>
>> This is a tantalising discussion, but the notion of "concave hull"
>> strikes me as extremely illdefined!
>>
>> I'd like to see statement of what it is (generically) supposed to be.
>
> I'm curious too, but I can imagine the following definition,
>
> Consider a sphere (ndimensional maybe) that we let come in contact
> with the scatter of points from outside. The set of points that the
> sphere can attain may define unambiguously (I think) a concave hull,
> for a specified sphere radius. The convex hull is obtained in the
> limit of infinite radius (plane).
>
> It's probably not exactly this, but I guess that's the rough idea.
>
> Just a thought,
> baptiste
Yes, it's the sort of idea I have had too! I imagined the true convex
hull as made of a stretchable material (like a soap bubble). With that
in place, now gently raise the air pressure outside the bubble. This
pushes the envelope inwards.
When the envelope, moving inwards, meets a point, it sticks to it and
does not move further at that point.
The parameter under your control is the pressure. You can stop when
you feel like it.
Once you have stopped, the set of points in contact with the envelope
can then be joined by lines (or, in higher dimensions, faces/simplexes).
This even has the merit that the surface has a definite equation
(with boundary conditions), so could be programmed!
However, the main thing left hanging in the air by this idea is that
you may want to arrange things so that the envelope gets pushed further
in from some directions than from others  i.e. on the soapbubble
analogy, you want to apply different levels of extra pressure to
different parts of the envelope.
For instance, in the example I included in my previous post, you might
want the envelope between points 19 & 3 to be under greater pressure
than the envelope between points 13 & 17.
So it is still an undefined solution. As is yours  since you might
want to use different radii of spheres from different directions.
Ted.

EMail: (Ted Harding) < [hidden email]>
Faxtoemail: +44 (0)870 094 0861
Date: 26Nov09 Time: 21:45:47
 XFMail 
______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/rhelpPLEASE do read the posting guide http://www.Rproject.org/postingguide.htmland provide commented, minimal, selfcontained, reproducible code.


There is a package on CRAN implementing such an idea:
alphahull, phull is other package,
kjetil
On Thu, Nov 26, 2009 at 6:11 PM, baptiste auguie
< [hidden email]> wrote:
> 2009/11/26 Ted Harding < [hidden email]>:
>> Raising a rather general question here.
>>
>> This is a tantalising discussion, but the notion of "concave hull"
>> strikes me as extremely illdefined!
>>
>> I'd like to see statement of what it is (generically) supposed to be.
>
> I'm curious too, but I can imagine the following definition,
>
> Consider a sphere (ndimensional maybe) that we let come in contact
> with the scatter of points from outside. The set of points that the
> sphere can attain may define unambiguously (I think) a concave hull,
> for a specified sphere radius. The convex hull is obtained in the
> limit of infinite radius (plane).
>
> It's probably not exactly this, but I guess that's the rough idea.
>
> Just a thought,
>
> baptiste
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/rhelp> PLEASE do read the posting guide http://www.Rproject.org/postingguide.html> and provide commented, minimal, selfcontained, reproducible code.
>
______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/rhelpPLEASE do read the posting guide http://www.Rproject.org/postingguide.htmland provide commented, minimal, selfcontained, reproducible code.


Thanks for the interesting reference to alphahull. It might be a good
starting point for placing e.g. a legend in a plot (I think the usual
techniques for this (gregmisc?) are a bit more bruteforce.)
baptiste
2009/11/27 Kjetil Halvorsen < [hidden email]>:
> There is a package on CRAN implementing such an idea:
> alphahull, phull is other package,
>
> kjetil
>
> On Thu, Nov 26, 2009 at 6:11 PM, baptiste auguie
> < [hidden email]> wrote:
>> 2009/11/26 Ted Harding < [hidden email]>:
>>> Raising a rather general question here.
>>>
>>> This is a tantalising discussion, but the notion of "concave hull"
>>> strikes me as extremely illdefined!
>>>
>>> I'd like to see statement of what it is (generically) supposed to be.
>>
>> I'm curious too, but I can imagine the following definition,
>>
>> Consider a sphere (ndimensional maybe) that we let come in contact
>> with the scatter of points from outside. The set of points that the
>> sphere can attain may define unambiguously (I think) a concave hull,
>> for a specified sphere radius. The convex hull is obtained in the
>> limit of infinite radius (plane).
>>
>> It's probably not exactly this, but I guess that's the rough idea.
>>
>> Just a thought,
>>
>> baptiste
>>
>> ______________________________________________
>> [hidden email] mailing list
>> https://stat.ethz.ch/mailman/listinfo/rhelp>> PLEASE do read the posting guide http://www.Rproject.org/postingguide.html>> and provide commented, minimal, selfcontained, reproducible code.
>>
>
______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/rhelpPLEASE do read the posting guide http://www.Rproject.org/postingguide.htmland provide commented, minimal, selfcontained, reproducible code.


Hi, I just want to add a possible solution to the problem in the special case all the points must stay on the edge of the outline. THis is sometimes the case when doing image analysis and you want to order the points along a closed path.
In this specific case, you can use some algorithm like the traveling salesman problem, which would give you the shortest path along all your points.
In this scenario, if your points are xy, you may use the following:
library(TSP)
tsp < TSP(dist(xy))
tour < solve_TSP(tsp,method='farthest')
xy < xy[tour,]
THis may not be the most economical solution (and you might also want contrains such as never to intersect the path) and is not valid if your boundary is not supposed to pass through all points.

