Subject: Inside or outside of a polyhedron

From: Robert Fraczkiewicz <[email-masked]>
Date: Mon, 15 Apr 1996 09:17:05 +0059 (CDT)

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.

Best regards,

Robert Fraczkiewicz
UT Medical Branch

---

From: Rui Luo <[email-masked]>
Date: Mon, 15 Apr 1996 18:11:38 +30000

On Mon, 15 Apr 1996, Robert Fraczkiewicz wrote:

> -------This is added Automatically by the Software--------
> -- Original Sender Envelope Address: [email-masked]
> -- Original Sender From: Address: [email-masked]
> [email-masked]: Everybody | [email-masked]: Coordinator
> [email-masked]: HELP CHEMISTRY or HELP SEARCH | Gopher: www.ccl.net 73
> Anon. ftp: www.ccl.net   | [email-masked] -- archive search
>              Web: http://www.ccl.net/chemistry.html 
> 

Just an idea. It's very efficient, but not sure it's right.

First transform the current coordinate system to one with the given point 
(x,y,z) as the origin. I.e. subtrate (xi,yi,zi), where i=1,...,N, by 
(x,y,z). This can be done very fast.

Second look at the sign of the transformed coordinates of all vertices. 
If all xi's, where i=1,...,N, have the same sign, the point is outside 
of the polyhedron. The statement holds for all yi's or all zi's. So if any 
one of the three conditions holds, the point will be outside. Otherwise if 
none of the conditions hold, it's inside.

Good Luck!

Rui Luo
CARB, UMBI
04/15

---

From: Harry Johnson <[email-masked]>
Date: Mon, 15 Apr 1996 20:02:42 -0400 (EDT)

>>>>> "Rui" == Rui Luo <[email-masked]> writes:

    Rui> Second look at the sign of the transformed coordinates of all
    Rui> vertices.  If all xi's, where i=1,...,N, have the same sign,
    Rui> the point is outside of the polyhedron. The statement holds
    Rui> for all yi's or all zi's. So if any one of the three
    Rui> conditions holds, the point will be outside. Otherwise if
    Rui> none of the conditions hold, it's inside.

Your last statement is incorrect.  Consider the 2D case:

    ----
   /   /
 +/   /
 /   /
/   /
---

If the point '+' is the origin, then all of the Xi's do not have the
same sign, nor do all of the Yi's, so none of the above conditions
hold, yet the point is still outside the polygon.  Your method is
another implementation of a bounding box.  Usually, however, it is
done by simply finding the maximum and minimum value of each
coordinate, x, y, and z, and checking to see whether the point's
coordinates lie within the extrema of the polyhedrons coordinates.  If
most of the points of interest likely lie outside the polyhedron this
is a quick initial screening method.

-Harry
______________________________________________________________________
Avant!			 Harry C. Johnson IV      [email-masked]
1101 Slater Rd		  Software Engineer       Phone: (919)941-6726
RTP, NC 27703		                            FAX: (919)941-6700
______________________________________________________________________

---

From: [email-masked]
Date: Mon, 15 Apr 1996 21:08:36 -0400 (EDT)

> > of a polyhedron: (x1,y1,z1),.....,(xN,yN,zN). What is the fastest 
snip...
> none of the conditions hold, it's inside.
It seems to me that this test will be reliable if the polyhedron is known 
to be convex, but other wise might be easily fooled:

       ___
       \  \
        \  \
         \  \
        *|  |
         /  /
        /  /
       /  /
      ----

Steve Williams
Chemistry, ASU
Boone, NC USA

snip