Forums > MaxMSP

Points and volumes in space

August 5, 2006 | 1:28 pm

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


August 8, 2006 | 4:47 am

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


August 8, 2006 | 12:34 pm

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
>


August 8, 2006 | 9:58 pm

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
>


Viewing 4 posts - 1 through 4 (of 4 total)