α – Shape generation with R

α-shape, is a family of piecewise linear simple curves in the Euclidean plane associated with the shape of a finite set of points.
— Wikipedia

Boum!. Let’s make it simpler. α-shape is a generalization of the convex hull concept. And the convex hull of a set of points is the minimal convex set containing all the points. Is typical to depict as some pins covered by a rubber band.

The concept of the α-shape involves trying to approach the “boundary” points more precisely and even create holes inside. I personally like the extravagant definition given by Kaspar Fischer on Introduction to Alpha Shapes.

Summarized: the universe of the definition is a big mass of ice cream with chocolate topping. With a spoon we start to carve out all the possible ice cream without touching any of the chocolate sprinkles. This results in a mass of rounded ice cream. If we now transform all the round faces to straight lines we obtain a “polygon”, an intuitive description of what is an α-shape. (As I told, a rocambolesque definition, I like it :-)).

The next image shows the idea in a 2D space (Imagine ice cream mass from a top view). The circles represent the spoon carvings.

In all this ice cream history, α is the radius of the spoon.
If α → 0, we can “theoretically” remove all the ice cream, leaving only the chocolate sprinkles.
If α → ∞ the spoon is too big, then we obtain the convex hull.
The game is between those extreme values.

Some α-shapes

For this example I use the R statistical package. It is nice to use this because is really simple to try some things without a lot of fuss. The example here is the same packed with alphahull.

First things first, install the package alphahull. From the R environment:

install.packages("alphahull")

Now we can start with the example. Create the “chocolate toppings”, a point cloud from which the α-shape has to be generated.

# Uniform sample of size n=300 in the annulus B(c, 0.5)\B(c, 0.25) 
# with c=(0.5, 0.5). 
n <- 300
theta<-runif(n,0,2*pi)
r<-sqrt(runif(n,0.25^2,0.5^2))
x<-cbind(0.5+r*cos(theta),0.5+r*sin(theta))

plot(x)

From this dataset, with R and alphahull is really easy to generate the α-shape, and it can be plotted with the delaunay triangulation and the Vornoi diagram (wlines=”del”, “vor” or both). The full help can be accessed with help(plot.ashape)

# alpha-shape 
ashape.obj <- ashape(x, alpha = 0.1)

#Plotting the alpha
plot(ashape.obj, wlines= "del", col = c(4, 1, 2, 3), lwd = c(1,3))
plot(ashape.obj, wlines= "vor", col = c(4, 1, 2, 3), lwd = c(1,3))

And the basic example is here :-).
A nice animation on the α value sensitiviy can be checked at Yihui Xie blog.

---

References

Edelsbrunner, Herbert; Kirkpatrick, David G.; Seidel, Raimund (1983), “On the shape of a set of points in the plane” ⇒ GO

Kaspar Fischer, Introduction to Alpha Shapes ⇒ GO

Beatriz Pateiro-López;Alberto Rodríguez-Casal, (2010): Generalizing the Convex Hull of a Sample: The R Package alphahull ⇒ GO

alphahull package at CRAN ⇒ GO

CGAL manual on α shapes⇒ GO

BioGeometry project explanation on α shapes ⇒ GO