Evenly spaced points in oddly shaped volume?

[blrnd]

This might be more of an algorithm question than a math question: how do I go about distributing n points as evenly as possible in a 3D volume of non-basic shape? Think human organs or the like. A related question is how do you know when you're inside a 3D volume versus outside it?

Thanks!

 

[Number Nine]

The easiest way, I think, would be to generate evenly distributed points in a cube around the object of interest, and then delete all of the points that fall outside of the shape. Of course, this requires that you have a mathematical description of the shape of interest, so that you can find the "outside".

May I ask what this is for? If you're trying to calculate its volume (an application where techniques like these come up), then uniformly distributed points are usually not the best way to go.

 

[chiro]

Hey blrnd and welcome to the forums.

Building on Number Nine's advice, I suggest you find a transformation that takes the cube to your desired object and then map the generated points in the cube to that object.

If you want more information look into tensor theory and deformation theory in continuum mechanics. By translating the cube to the object, you simulate the random uniform distribution in the cube and then just transform it.

You could possibly even find a transformation that allows you to get an actual 3D PDF for the object itself but this is going to be a lot harder and is not necessary for simulation.

 

[oli4]

Hi blrnd,
I remember having done exactly this a long time ago, the technique I found was to spread 'charged particles' randomly and simulate them repealing each other until the average distance would stay stable.
Cheers...

 

[phyzguy]

Another way that works in a volume of arbitrary dimensions is as follows:

(1) Randomly generate many more points in the volume than you need, say 100n points.
(2) Step through the points and find the point whose distance to any other point is the smallest. Delete this point.
(3) Repeat step 2 until you are down to the n points that you want.

This algorithm is simple to code, and generates points that are more or less uniformly distributed through the volume.

To determine whether a point is inside or outside of the volume, you need to have some mathematical description of the volume. Often this is done by having a set of bounding planes. The orientation of the planes is then defined so that one side of the plane points 'inward', and and one side points 'outward'. A point is inside of the volume if it is on the inward side of all planes, and it is outside if it is on the outward side of any plane.