# Re: CCL:Inside or outside of a polyhedron

*From*: Alexander Golbraikh <golb -AatT- osi.lanet.lv>
*Subject*: Re: CCL:Inside or outside of a polyhedron
*Date*: Tue, 16 Apr 1996 11:50:50 +0300 (DST)

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
------------------------------------------------------------------------