Re: CCL:Inside or outside of a polyhedron

[Alexander Golbraikh <golb -AatT- osi.lanet.lv>]

 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
 >
 >
 Take any ray beginning at the given point. Count the number of
 points of intersection of this ray with polyhedron surface. If it is
 even, then the point is outside the polyhedron, if it is odd, then inside.
 One precaution: the ray may slide on some edges of the polyhedron.
 Best regards,
 Alexander Golbraikh
 ------------------------------------------------------------------------
 Dr. Alexander Golbraikh                 e-mail: golb -AatT- osi.lanet.lv
 Latvian Institute of Organic Synthesis
 Aizkraukles st. 21                      Phone:  +(371)-7-552-354
 Riga, LV-1006                           FAX:    +(371)-7-821-038
 LATVIA
 ------------------------------------------------------------------------