From owner-chemistry:~at~:ccl.net  Tue Apr 16 13:47:01 1996
Received: from bedrock.ccl.net  for owner-chemistry {*at*} ccl.net
	by www.ccl.net (8.7.1/950822.1) id NAA04301; Tue, 16 Apr 1996 13:26:42 -0400 (EDT)
Received: from MOLENG.UCSC.EDU  for wipke "-at-" SECS.UCSC.EDU
	by bedrock.ccl.net (8.7.1/950822.1) id NAA01109; Tue, 16 Apr 1996 13:26:36 -0400 (EDT)
Received: by SECS.UCSC.EDU (MX V3.1C) id 11292; Tue, 16 Apr 1996 10:24:42 PDT
Date: Tue, 16 Apr 1996 10:24:37 PDT
From: "W. Todd Wipke" <wipke -8 at 8- SECS.UCSC.EDU>
To: chemistry*- at -*ccl.net
Message-ID: <009A0F07.60966DE0.11292 /at\SECS.UCSC.EDU>
Subject: CCL:Inside or outside of a polyhedron                           


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
 wipke {*at*} chemistry.ucsc.edu