Trond Lossius

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 

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?

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?

points-and-volumes-in-space

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

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 

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 

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.

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

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.

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.

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 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.

> 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
>


Points and volumes in space