Re: CCL:Inside or outside of a polyhedron

[pueyo # - at - # pinon.ccu.uniovi.es (Lorenzo Pueyo)]

 Robert Fraczkiewicz <robert # - at - # tocsy.utmb.edu> wrote:
 >Dear Netters,
 >Suppose you have given N arbitrary points (in 3D space) that are vertices
 >of a polyhedron: (x1,y1,z1),.....,(xN,yN,zN). What is the fastest
 >algorithm for determining if a given point (x,y,z) is inside or outside of
 >this polyhedron? (Calculating distances to every vertex is not a good
 >idea). I will post summary to the net.
 You can find a long answer in the comp.graphics.algorithm FAQ archived at:
  http://www.cis.ohio-state.edu/hypertext/faq/usenet/graphics/algorithms-faq/faq.html
 In any case:
  1) If your polyhedron is convex, it is very efficient to have determined
     the Ax+By+Cz+D=0 plane equation for each face with the sign convention,
     for instance, that all points lying in the 'inside' hemi-space
     are positive (i.e. A x0 + B y0 + C z0 + D > 0). In that case, checking
     if a new point is inside or outside is just a question of substituting
     the cartesian coordinates of the point in the plane equations of
     every face and testing whether all signs are positive or there is
     one or more negative.
  2) No matter if your polyhedron is convex or not, an inside point is such that
     every ray that begins in the point will intersect the polyhedron faces
     an odd number of times. Given a new point, you can always decide
     an arbitrary direction and check for the intersections of the line
     with the polyhedron faces. If there is zero or an even number of
     intersections, your point is outside the polyhedron, otherwise it is
     inside.
 Hope this helps you.
     Sincerely,
           Victor Lua~na
 --
     HomePage   http://www.uniovi.es/~quimica.fisica/qcg/vlc/luana.html
 +--------------------------------------------+  +---^---/    /
 !               Victor Lua~na                !  |   ~       / Just in case
 ! Departamento de Quimica Fisica y Analitica !  |           | you don't
 ! Universidad de Oviedo, 33006-Oviedo, Spain ! <            / remember
 !  e-mail: victor # - at - # carbono.quimica.uniovi.es  !  |          /  where
 Oviedo
 !          phone: (34)-8-5103491             !  |____  ___/   is  ;-)
 !           fax: (34)-8-5103125              !       \/
 +--------------------------------------------+