Point Inclusion in Polyhedron Testing

Here is one way to test whether a 3D point in inside a polyhedron.
  1. Run a semi-infinite ray up from the point, P, and
  2. Count how many faces it crosses.
The ray crosses face F iff
  1. P lies below the plane of F, and
  2. when P is projected (in the direction of the ray) onto the plane of F, then it is inside F. This is a 2D point-containment problem.
If the ray intersects a vertex or an edge, then you're in trouble. Consider perturbing P slightly. Simulation of Simplicity provides a better, more complicated, solution.

Wm. Randolph Franklin, Associate Professor
Email: wrfATecse.rpi.edu
http://wrfranklin.org/
☎ +1 (518) 276-6077; Fax: -6261
ECSE Dept., 6026 JEC, Rensselaer Polytechnic Inst, Troy NY, 12180 USA
(GPG and PGP keys available)