alpha shape function

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

alpha shape function

Pedroso MOACIR
Hi all,

I want to approximate te shape of an area defined by a set of points.
The convex hull is not good enough, but I think that an alpha shape
would be fine. I did an RSiteSearch(),  google search, RSeek.org search,
looked at the CRAN Views, but was unable do find a function in R that
computes the alpha shape.  Does anyone know if there is such a function
in R?

Theank you very much.

Moacir Pedroso
Embrapa - Brazil

______________________________________________
[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: alpha shape function

RKoenker
As it happens, I have also been looking into this.  I began by  
considering
Ken Clarkson's hull:  http://www.netlib.org/voronoi/hull.html  but  
eventually
discovered that its alpha shapes don't seem to treat holes in regions,  
only
simply connected regions.  (I would be happy to hear to the contrary, if
someone has other experience.)  There is a nice matlab implementation
http://www.mathworks.com/matlabcentral/fileexchange/6760 which I've
also experimented with using R.matlab, but  this is still very early  
days.
The matlab version is only 2d, whereas Clarkson does "moderate d"    
which
extends at least to 3d.
Given tripack, it seems like alpha-shapes shouldn't be such a big  
enterprise, and
might  make a nice project for someone with an interest in computational
geometry.   Hint, hint.  Nudge, Nudge.

url:    www.econ.uiuc.edu/~roger            Roger Koenker
email    [hidden email]            Department of Economics
vox:     217-333-4558                University of Illinois
fax:       217-244-6678                Champaign, IL 61820



On Feb 18, 2009, at 7:20 AM, Pedroso MOACIR wrote:

> Hi all,
>
> I want to approximate te shape of an area defined by a set of points.
> The convex hull is not good enough, but I think that an alpha shape
> would be fine. I did an RSiteSearch(),  google search, RSeek.org  
> search,
> looked at the CRAN Views, but was unable do find a function in R that
> computes the alpha shape.  Does anyone know if there is such a  
> function
> in R?
>
> Theank you very much.
>
> Moacir Pedroso
> Embrapa - Brazil
>
> ______________________________________________
> [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: alpha shape function

Yihui Xie
Hi,

If the convex hull for *all* the data points is not ideal enough, is
it feasible to break the data into small subsets using clustering
methods such as kmeans() and compute the convex hull for each cluster?
Finally we are able to know the "borders" of all clusters using
chull(); I don't know how difficult it will be to find an exact
solution to your problem in the future computation, but I think there
can be good enough approximations.

For example, you may choose a proper 'k' for the k-means clustering:

##
set.seed(1234)
devAskNewPage(ask = TRUE)
par(pch = 20)
dat = iris[, 1:2]
n = nrow(dat)
for (k in 2:30) {
    ch = integer()
    cl = kmeans(dat, k, 50)$cluster
    plot(dat, main = paste("k =", k))
    for (i in unique(cl)) {
        idx = chull(tmp <- dat[cl == i, ])
        ch = c(ch, as.integer(rownames(tmp[idx, ])))
        polygon(tmp[idx, ], border = NA, col = rgb(0, 0, 0, 0.2))
    }
    plot(dat, main = paste("Polygon shape when k =", k))
    polygon(dat[ch, ], col = rgb(0, 0, 0, 0.2))  # need to be ordered
}
##

One critical problem I have not solved in the above code, I think, is
the ordering of all the border points, so the last whole polygon looks
weird...

Regards,
Yihui
--
Yihui Xie <[hidden email]>
Phone: +86-(0)10-82509086 Fax: +86-(0)10-82509086
Mobile: +86-15810805877
Homepage: http://www.yihui.name
School of Statistics, Room 1037, Mingde Main Building,
Renmin University of China, Beijing, 100872, China



On Wed, Feb 18, 2009 at 9:46 PM, roger koenker <[hidden email]> wrote:

> As it happens, I have also been looking into this.  I began by considering
> Ken Clarkson's hull:  http://www.netlib.org/voronoi/hull.html  but
> eventually
> discovered that its alpha shapes don't seem to treat holes in regions, only
> simply connected regions.  (I would be happy to hear to the contrary, if
> someone has other experience.)  There is a nice matlab implementation
> http://www.mathworks.com/matlabcentral/fileexchange/6760 which I've
> also experimented with using R.matlab, but  this is still very early days.
> The matlab version is only 2d, whereas Clarkson does "moderate d"   which
> extends at least to 3d.
> Given tripack, it seems like alpha-shapes shouldn't be such a big
> enterprise, and
> might  make a nice project for someone with an interest in computational
> geometry.   Hint, hint.  Nudge, Nudge.
>
> url:    www.econ.uiuc.edu/~roger            Roger Koenker
> email    [hidden email]            Department of Economics
> vox:     217-333-4558                University of Illinois
> fax:       217-244-6678                Champaign, IL 61820
>
>
>
> On Feb 18, 2009, at 7:20 AM, Pedroso MOACIR wrote:
>
>> Hi all,
>>
>> I want to approximate te shape of an area defined by a set of points.
>> The convex hull is not good enough, but I think that an alpha shape
>> would be fine. I did an RSiteSearch(),  google search, RSeek.org search,
>> looked at the CRAN Views, but was unable do find a function in R that
>> computes the alpha shape.  Does anyone know if there is such a function
>> in R?
>>
>> Theank you very much.
>>
>> Moacir Pedroso
>> Embrapa - Brazil
>>

______________________________________________
[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.