α-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

Pingback: Convex Hull, one algorithm implementation | Castells