Subject: Re: CCL:Inside or outside of a polyhedron

From: [email-masked] (Lorenzo Pueyo)
Date: Tue, 16 Apr 1996 12:13:02 +0200

Robert Fraczkiewicz <[email-masked]> 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: [email-masked]  !  |          /  where Oviedo
!          phone: (34)-8-5103491             !  |____  ___/   is  ;-)
!           fax: (34)-8-5103125              !       \/
+--------------------------------------------+