### Points and volumes in space

If I have N points in 3D space these will form some sort of a volume,

assuming that they are not all on the same plane or line. Some points

might be inside the volume while others will be defining the various

edges of the volume.

My question is, do anyone know of any general and efficient algorithm

for determining if another point is inside or outside of this volume,

and if it is positioned outside the volume how to determine the shortest

distance from the point onto the surface of the volume, and the position

of the projection of the point onto the surface?

Thanks,

Trond

Are you looking for a programming algorithm (if…then, etc., not too tough), or a mathematical one (calculus! augh! It’s been a while…)?

Mike

Both, please. In the end I’m looking for an algorithm that can be

prototyped in Max and eventually hard-coded for speed, but to get there

I also want to now if there are any clever shortcuts that can be done to

optimize the process.

I know how to project a point onto a line and how to project a point

onto a plane. This would serve the particular cases of only two or three

points defining the shape that the extra point is to to be projected

onto, but I’m less sure about how to expand this beyond three points

without having to project onto each of the planes constructed by any

combination of three points (the number of such processes required would

be !(n-2) for n points) and thus increase very fast as the number of

points increase.

I imagine that it should be possible to find a sort of method of least

squares approach, but I’m not sure about exactly how.

Best,

Trond

Mike Sayre wrote:

> Are you looking for a programming algorithm (if…then, etc., not too tough), or a mathematical one (calculus! augh! It’s been a while…)?

>

> Mike

>

The name of the volume you’re talking about is the "convex hull."

Now you can look up a bunch of algorithms. I think there are

relatively simple algorithms that run in O(n log n) time. The best

algorithms for this and your points/faces projection will depend on

whether your points are mainly static or dynamic.

-Randy

On Aug 5, 2006, at 6:28 AM, Trond Lossius wrote:

> If I have N points in 3D space these will form some sort of a

> volume, assuming that they are not all on the same plane or line.

> Some points might be inside the volume while others will be

> defining the various edges of the volume.

>

> My question is, do anyone know of any general and efficient

> algorithm for determining if another point is inside or outside of

> this volume, and if it is positioned outside the volume how to

> determine the shortest distance from the point onto the surface of

> the volume, and the position of the projection of the point onto

> the surface?

>

> Thanks,

> Trond

>