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
      >