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

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

On Mon, 15 Apr 1996, Robert Fraczkiewicz 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.
> 
> Best regards,
> 
> Robert Fraczkiewicz
> UT Medical Branch
> 
> -------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