Trying to understand behavior of holes in alphaShapes.

I have created the attached alphaShape object, which contains a hole.

load alph_shape;

shp

shp = 
  alphaShape with properties:

             Points: [6546×2 double]
              Alpha: 10
      HoleThreshold: 0
    RegionThreshold: 0

plot(shp)

I am trying to understand why, when I drastically increase the alpha radius,

shp.Alpha=1e6;

edges are added that transect the hole. Clearly, the radius is much bigger than the dimensions of the hole, so how can the enlargement cause new edges to be added inside it?

plot(shp)

Answer 1

[Matt J]

I found the following in posted material for a course at Stanford. It's a pretty intuitive explanation of how alpha shapes work, and clears up my question, if it is accurate.

-------------------------

As mentioned in Edelsbrunner’s and M ̈ucke’s paper [3], one can intuitively think of an α-shape as the following. Imagine a huge mass of ice-cream making up the space Rd and containing the points S as “hard” chocolate pieces. Using one of these sphere-formed ice-cream spoons we carve out all parts of the ice-cream block we can reach without bumping into chocolate pieces, thereby even carving out holes in the inside ([Ed. the ice cream spoon is allowed to travel freely through space, even to within areas girded by the points S. However, it is allowed to draw a scoop if and only if the points in S can be excluded. ]).

We will eventually end up with a (not necessarily convex) object bounded by caps, arcs and points. If we now straighten all “round” faces to triangles and line segments, we have an intuitive description of what is called the α-shape of S...And what is α in the game? α is the radius of the carving spoon.

Answer 2

[Kumar Pallav]

Hi,

The default alpha radius is one which is the smallest alpha radius that produces an alpha shape that encloses all points.

From my understanding, as you increase the 'alpha' value, it no longer produces the tighest fitting alpha shape, and you can observe this with the holes getting filled by points connected within that radius.

For an extreme value of 'alpha'=inf, it basically produces a conves hull with all the points inside it.

Since, you have given a large value of alpha, it is basically producing a convex hull.

Refer this for more on alphaShape.

Hope this helps!

[Matt J]

@Kumar Pallav, Thanks, but I don't think that completely explains it, and your link to the alphashape doc page does not contain any information about the defining properties of an alphashape. Therefore, I looked to this wiki page, which says,

An edge of the alpha-shape is drawn between two members of the finite point set whenever there exists a generalized disk of radius 1/α containing none of the point set and which has the property that the two points lie on its boundary.

Now, if 2 points lie on opposite sides of a hole, it doesn't seem possible for a circle whose radius is larger than the hole to avoid containing other members of the point set. Therefore, it doesn't seem like an edge should ever be drawn between them.

[Matt J]

The source I found for my other answer makes me wonder if the wiki page had a typo and "none of the point set" should really have been "one of the point set".