Concave hull

classic Classic list List threaded Threaded
16 messages Options
Reply | Threaded
Open this post in threaded view
|

Concave hull

Corrado Topi
Dear friends,

Do you know how to calculate the CONCAVE hull of a set of points (2-
dimensional or n-dimensional)? 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, E-mail: [hidden email]

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: Concave hull

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



remko

-------------------------------------------------
Remko Duursma
Post-Doctoral 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 n-dimensional)? 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, E-mail: [hidden email]
>
> ______________________________________________
> [hidden email] 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.
>

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: Concave hull

barry rowlingson
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/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: Concave hull

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

r

-------------------------------------------------
Remko Duursma
Post-Doctoral 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/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: Concave hull

David Winsemius
In reply to this post by Corrado Topi
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 n-dimensional)? 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, E-mail: [hidden email]
>
> ______________________________________________
> [hidden email] 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.

David Winsemius, MD
Heritage Laboratories
West Hartford, CT

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: Concave hull

David Winsemius
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 n-dimensional)? 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, E-mail: [hidden email]
>>
>> ______________________________________________
>> [hidden email] 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.
>
> David Winsemius, MD
> Heritage Laboratories
> West Hartford, CT
>
> ______________________________________________
> [hidden email] 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.

David Winsemius, MD
Heritage Laboratories
West Hartford, CT

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: Concave hull

David Winsemius

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

--
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 n-dimensional)? 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, E-mail: [hidden email]
>>>
>>> ______________________________________________
>>> [hidden email] 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.
>>
>> David Winsemius, MD
>> Heritage Laboratories
>> West Hartford, CT
>>
>> ______________________________________________
>> [hidden email] 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.
>
> 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/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: 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: [hidden email]

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

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

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: Concave hull

Ted.Harding-2
Raising a rather general question here.

This is a tantalising discussion, but the notion of "concave hull"
strikes me as extremely ill-defined!

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.

--------------------------------------------------------------------
E-Mail: (Ted Harding) <[hidden email]>
Fax-to-email: +44 (0)870 094 0861
Date: 26-Nov-09                                       Time: 20:52:03
------------------------------ XFMail ------------------------------

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: Concave hull

baptiste auguie-5
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 ill-defined!
>
> 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 (n-dimensional 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/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: Concave hull

Ted.Harding-2
On 26-Nov-09 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 ill-defined!
>>
>> 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 (n-dimensional 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 soap-bubble
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.

--------------------------------------------------------------------
E-Mail: (Ted Harding) <[hidden email]>
Fax-to-email: +44 (0)870 094 0861
Date: 26-Nov-09                                       Time: 21:45:47
------------------------------ XFMail ------------------------------

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: Concave hull

barry rowlingson
On Thu, Nov 26, 2009 at 9:45 PM, Ted Harding
<[hidden email]> wrote:

> So it is still an undefined solution. As is yours -- since you might
> want to use different radii of spheres from different directions.

 I think the formal and rigorous definition is "a nice polygon that goes round
my points".

Barry

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: Concave hull

Kjetil Halvorsen
In reply to this post by baptiste auguie-5
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 ill-defined!
>>
>> 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 (n-dimensional 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/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
>

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: Concave hull

baptiste auguie-5
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 brute-force.)


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 ill-defined!
>>>
>>> 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 (n-dimensional 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/r-help
>> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
>> and provide commented, minimal, self-contained, reproducible code.
>>
>

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: Concave hull

davide.viggiano
In reply to this post by Corrado Topi
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.