Etiquetas

, , ,

What are the alpha shapes?:

“The concept of alpha shapes formalizes the intuitive notion of “shape” for spatial point set data, which occurs frequently in the computational sciences. An alpha shape is a concrete geometric object that is uniquely defined for a particular point set.[...] Alpha shapes are generalizations of the convex hull.

Given a finite point set S, and a real parameter alpha, the alpha shape of S is a polytope which is neither necessarily convex nor necessarily connected, and can be derived from the (weighted) Delaunay triangulation of the point set.

The set of all real numbers alpha leads to a family of shapes capturing the intuitive notion of “crude” versus “fine” shape of a point set. For sufficiently large alpha, the alpha shape is identical to the convex hull of S. As alpha decreases, the shape shrinks and gradually develops cavities. These cavities may join to form tunnels and voids. For sufficiently small alpha, the alpha shape is empty.”

This text is extracted from the Biogeometry software project webpage, where you could find more information.

A package called alphahull includes functions for computing alpha shapes and hulls in R. Details about it are reported in this paper. This package defines a method for plot in order to visualize the shapes. However, I want to display the results with lattice. Here is my solution for the ashape objects:


panel.ashape <- function(x, y, alpha=0.05, lty=1, lwd=1, col='black'){
 as <- ashape(x, y, alpha=alpha)
 lin <- as$edges
 lin <- data.frame(t(lin))
 lapply(lin, function(x)panel.segments(x[3], x[4], x[5], x[6], lty=lty, lwd=lwd, col=col))
}

and for ahull objects:


panel.ahull <- function(x, y, alpha=0.05, lty=1, lwd=1, col='black'){
 calcArc <- function (c, r, v, theta) ##adapted from alphahull::arc
 {
 angles <- anglesArc(v, theta)
 seqang <- seq(angles[1], angles[2], length = 100)
 x <- c[1] + r * cos(seqang)
 y <- c[2] + r * sin(seqang)
 res=cbind(x, y)
 }
 ah <- ahull(x, y, alpha=alpha)
 arcos <- subset(ah$arcs, ah$arcs[, 3] > 0)
 arcos <- data.frame(t(arcos))
 lapply(arcos, function(x)llines(calcArc(x[1:2], x[3], x[4:5], x[6]), lty=lty, lwd=lwd, col=col))
}

Now let’s try them with an example (adapted from help(ahull)). First I generate random points from a uniform distribution on a Koch snowflake:


library(lattice)

library(latticeExtra)
library(alphahull)

points <- as.data.frame(rkoch(2000, side = 1, niter = 3))
names(points) <- c('x', 'y')
points=rbind(points, points+1, points-1)
points$ID <- rep(c('A', 'B', 'C'), each=2000)

[/lang]

I plot them with xyplot and superpose a <a title="layer" href="http://search.r-project.org/library/latticeExtra/html/layer.html" target="_blank">layer</a> with the result of ahull:

1

p <- xyplot(y~x, data=points, cex=0.5, alpha=0.3, groups=ID)##Here alpha is the transparency parameter
p+layer(panel.ahull(x, y, lwd=4, alpha=.08, col='black'))##Here alpha is used by ahull

and with the result of ashape:


p <- xyplot(y~x, data=points, cex=0.5, alpha=0.3, groups=ID)##Here alpha is the transparency parameter
 p+layer(panel.ashape(x, y, lwd=4, alpha=.08, col='black'))##Here alpha is used by ashape


Moreover, with glayer we can use the fact that the points are grouped to get different colors of the shapes:


p+glayer(panel.ahull(x, y, lwd=4, alpha=.08, col=col.line))

p+glayer(panel.ashape(x, y, lwd=4, alpha=.08, col=col.line))

There are more examples of the use of alphahull here and here.

About these ads