volume of set of points in 3-d space

Hi, I have large set of points in 3-d space, i want to calculate volume enclosed by that cluster of points. what is efficient way to approach this problem other than convex hull method which doesn't give accurate prediction for kind of shapes?

[Antti]

So each point is a corner point?

In convex hull there can be, at maximum, (n_points - 4) points inside the object?

Interesting question...

[Antti]

Could you please give an example in order to describe how a (small) set of points in 3-d space create volume?

In my mind, same set of points can create different kinds of volumes(?).

If you have a corner points of a dice and you add to this set one extra corner point, you'll have several opportunities to draw the object of these 7 corner points.

[sam]

thanks antti,

so large set of points is present, but i am concerned about volume only enclosed by outer points (extreme points) of data set.

Answer 1

[Walter Roberson]

"volume enclosed by a cluster of points" is not well defined. You can make arbitrary cuts into the cloud, connecting the points with vertices in many different ways, resulting in a very large number of different possible "volumes".

The "volume" cannot be meaningfully measured unless you can place strict rules about what is connected to what -- rules strict enough that there is no choice in the placement (unless it could be proven that the choice did not affect the calculation.)

"convex hull" is a sufficiently strict set of rules as to eliminate choices that would affect the calculation, but if you require that your hull be non-convex then you will likely find it difficult to define the volume uniquely.

Answer 2

[sam]

thanks walter, so large set of points is present, but i am concerned about volume only enclosed by outer points (extreme points) of data set. if one join all outer points (not by convex hull), we'll get a surface then volume enclosed by surface obtained is what i m interested in.

[Walter Roberson]

A convex hull *is* what you get if you join the outer points. Unless you have a different definition of "outer points", or you have a special way of joining them??

[Sean de Wolski]

What you're describing Sam sounds like the definition of a convex hull to me.

[sam]

i think convex hull will not consider all outer points, it will do something like shown in picture in this page

http://www.mathworks.com/help/techdoc/ref/convhull.html

it will take only convex shape, which is not exact shape of data set outer boundary.

[Walter Roberson]

If you are thinking that in that example that the shape you want would follow the curve of the "heart", in and back out again, then my previous answer applies: the answer is not well-defined unless you can create strict rules about what is "inside".

[sam]

yes, thatswhat i mean, curve should go in 'heart' shape But in 3-d space. anyway how can i draw/get that curve/surface exactly like in pic but going in heart shape.

[Sean de Wolski]

Define constraints. Otherwise the heart is just what the human eye sees because we know what a heart looks like. Computers don't have souls or hearts and thus they don't know what they are.

There is a huge number of possible pemutations (well above n!) to connect those points

Answer 3

[Sean de Wolski]

Please see Steven Lord's wonderful reply here:

• Old:Newsreader:Thread On concave hull