alpha shape vs convex hull volume value

Calculating the volume value with alpha shape yields a value of 1.6448e+09.

Calculating the volume value with convex hull yields a value of 1.8100e+10

I have calculated the same ply file, but why is it so different?

Calculated as an alpha shape is very different from the actual volume value.

I would like to get the calculated value of the convex hull as the volume value in concave hull form.

Do I have to do it the other way than the Alpha Shape?

[John D'Errico]

Without seeing the data, it is impossible to tell you. But it is easy enough to create some data that has a 10-1 volume differential between a convex hull and an alpha shape. So if you want help, you need to actually provide some information that would help the person who might answer you. Post the data that created these results.

[woongkuk ryu]

ply file attached.

I know the difference between convex and concave, but I do not understand why the result is so different.

Answer 1

[John D'Errico]

A problem with your data is it has holes in it. The inside looks to be empty. But worse, it has a void on one corner, where the alpha ball can penetrate.

S0 = alphaShape(data(:,1:3))
S0 = 
  alphaShape with properties:

             Points: [76370×3 double]
              Alpha: 246.2
      HoleThreshold: 0
    RegionThreshold: 0
    
volume(S0)
ans =
   1.5087e+09

A volume of 1.5e9. But look at the alpha radius choen by alphaShape: 246.2. When I looked at the plot, the hole was roughly 5 times as large. Let me plot the result, and rotate it to show the interior:

plot(S0)
view(-2.5,11.5)

Do you see the hole? The result is completely HOLLOW.

Instead, if I use a larger value for alpha, I get a larger volume, closer to that of the convex hull.

S = alphaShape(data(:,1:3),1500);
volume(S)
ans =
   1.7524e+10

Admittedly, it does not resolve the details of that shape as well. But if you don't want the holes to allow the alpha ball to erode the entire interior of the volume, then you cannot have large holes in your data!!!

Perhaps you don't understand the idea of an alpha shape. You essentially start with the convex hull, as a delaunay triangulation. Then you roll a ball (of radius alpha) around the surface of the shape. Allow the ball to penetrate any facet of the surface, but do NOT allow it to pass through a node. So each simplex in the triangulation has 4 vertices, three of which can comprise an exterior facet. If the alpha ball can touch the 4TH vertex of a simplex on the surface, thus penetrating that simplex, then you delete the indicated simplex, removing it from the tessellation.

The idea is to remove large surface simplexes that form when we have a concave domain, because a basic delaunay triangulation ALWAYS describes a convex region.

Essentially, we allow the alpha ball to erode the tessellation. But what happens when you have a large hole in the cloud? A BAD IDEA. You will not be able to use an alpha shape with a small value of alpha, because you will see exactly what happens here.

xy = rand(1000,2);
k = sqrt(sum((xy - [1, .5]).^2,2)) < 0.4;
xy(k,:) = [];
plot(xy(:,1),xy(:,2),'.')

So a roughly square region, not too finely sampled. So there are some problems areound the edges, but mainly a hole of radius 0.4 intruding into one side. First, the delaunay triangulation will be equivalent to an alpha shape with an infinite radius alpha ball.

S0 = alphaShape(xy,inf)
area(S0)
ans =
       0.9783
       
plot(S0)

So a roughly square region. But we expect to have a region with area a little less than:

1 - pi*0.4^2/2
ans =
      0.74867

First, let alphaShape decide the radius itself.

S = alphaShape(xy)
S = 
  alphaShape with properties:

             Points: [733×2 double]
              Alpha: 0.035248
      HoleThreshold: 0
    RegionThreshold: 0
>> area(S)
ans =
      0.50374

It went too far. Note that there are subtly different ways to perform an alpha shape. My algorithm did not allow the ball to delete internal holes, alhthough I recall I offered that as an option.) The algorithm in alphaShape does allow that to happen. But I could have changed that behavior by setting the HoleThreshold.

Regardless, you can see the result used too small a value for alpha. Try it using a more reasonable alpha radius.

S = alphaShape(xy,.4)

area(S)
ans =
      0.75336

plot(S)

Here, you can see that I probably should have gone just a bit smaller for alpha, perhaps 0.3. Or, I could have used the HoleThreshold.

S = alphaShape(xy,0.1,'HoleThreshold',1)
S = 
  alphaShape with properties:

             Points: [733×2 double]
              Alpha: 0.1
      HoleThreshold: 1
    RegionThreshold: 0
    
plot(S)

To get a better approximation to the true area expected, I needed to use a reasonable alpha, but more importantly, I needed to more carefully sample the boundaries of the region.

So finally, let me do a good job of this.

xy = rand(100000,2);
k = sqrt(sum((xy - [1, .5]).^2,2)) < 0.4;
xy(k,:) = [];

S = alphaShape(xy,0.3,'HoleThreshold',1);

area(S)
ans =
      0.74726
      
plot(S)

As you can see, it quite reasonably approximates the area, which was analytically computed as 0.74867...

Answer 2

[Steven Lord]

Place your hand, palm down and fingers spread, on a piece of paper. Trace around it until you reach your wrist (where you would wear a watch) and connect across where your wrist would be with a straight line. The figure you've just drawn is an alpha shape for your hand.

Now place your hand, palm down and fingers spread, on another piece of paper. Trace from your wrist up along the outside of your pinky finger and your thumb, then connect the dots from fingertip to fingertip, pinky to ring to middle to index finger to thumb. Connect where your wrist would be with a straight line. That's a convex hull for your hand. [Technically it's probably not, if you spread your pinky finger and thumb out past forming a straight line with the side of your hand. But it's close enough for this demonstration.]

The area of the convex hull of your hand encompasses the space between your fingers while the area of the alpha shape of your hand doesn't. Same hand, different area.

Answer 3

[Matt J]

Because the convex hull and an alpha shape are not necessarily the same shape. The alpha shape, in particular, depends on the alpha radius parameter you have chosen. If you make the alpha radius larger and larger, then the alpha shape (and likewise the calculated volume) should become closer and closer to the convex hull of your points.