Points and volumes in space


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

    • Aug 08 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
    • Aug 08 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 >
    • Aug 08 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 >