[Update REQ 5265]: 3-D Geometry Stuff

["Nina Amenta" <nina>]

Hi,

This kind of algorithm has been implemented many times, but 
I don't know of any publicly available code, unfortunately.
If you find some, let us know! We're trying to collect pointers
to useful stuff on the net. 

First note that if your 3-D polyhderon (I assume that's what
you mean when you say a polygon in 3-D? If you really mean a 2-D 
polygon that just happens to be floating around in 3-D, see below) 
is convex and doesn't have too many sides, you can just check that 
the point is inside all the sides. 

One good discussion of the 2-D (non-convex) basics is in Joe
O'Rourke's book ``Computational Geometry in C'' - I would buy this
book if I were you! Cambridge University Press. The code for all the
algorithms in the book is available at:

grendel.csc.smith.edu
/local/ftp/pub/compgeom

For a non-convex 3-D polyhedron, you can also use the first 
method that he describes for 2-D - count how many times an
infinite ray through the point intersects the boundary of the
polyhedron. Testing whether the ray intersects a given face of
the polyhedron means testing whether the point of intersection 
of the ray with the plane containing the face lies in the face;
an example of the 2-D test!

Have fun - Nina