Re: CCL:Inside or outside of a polyhedron

[Rui Luo <rui $#at#$ iris6.carb.nist.gov>]

 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: robert $#at#$ tocsy.utmb.edu
 > -- Original Sender From: Address: robert $#at#$ tocsy.utmb.edu
 > CHEMISTRY $#at#$ www.ccl.net: Everybody | CHEMISTRY-REQUEST $#at#$
 www.ccl.net: Coordinator
 > MAILSERV $#at#$ www.ccl.net: HELP CHEMISTRY or HELP SEARCH | Gopher:
 www.ccl.net 73
 > Anon. ftp: www.ccl.net   | CHEMISTRY-SEARCH $#at#$ www.ccl.net -- 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