Subject: CCL:Inside or outside of a polyhedron

From: "W. Todd Wipke" <[email-masked]>
Date: Tue, 16 Apr 1996 10:24:37 PDT

There are a few quick checks:

If the x coords of all vertices are all less than or all greater than the
x coord of the pt, then the point must be outside.  Similarly for y and z.

Find the center of an enclosing sphere for the polyhedron.  If the point
is outside the enclosing sphere, then it is outside the polyhedron.

Find the center of a maximal enclosed sphere for the polyhedron.  If the
point is inside the enclosed sphere, then it must be inside the polyhedron.

There is also the scheme of shooting out a ray from the point.  If it
crosses the polyhedron surface an odd number of times, then it is inside,
if an even number of times, then it is outside.
-Todd Wipke
 Molecular Engineering Laboratory
 University of California
 Santa Cruz, CA
 [email-masked]

---

From: Michael Kotelyanskii <[email-masked]>
Date: Tue, 16 Apr 1996 16:19:44 +22305133 (EDT)

OK, here is another one:

1) Make a Delone tesselation for the polyhedron vortices.

If it is convex, all Delone simplexes (tetrahedra) are inside
the polyhedron.
In this case if your point is inside of any of the simplexes (simplex is
a tetrahedron - so check is simple (center of tetrahedron is always
inside, connect center with your point and see wether the border is crossed)
it is inside polyhedron.

If polyhedron is not convex, there will be Delone simplexes connecting
vortices which are entirely outside the polyhedron, and they can be excluded

I believe it should work
Mike

Michael Kotelyanskii PhD
Department of Chemical Engineering
University of Delaware                          [email-masked]
Newark DE 19716