From craig \\at// occam.gh.wits.ac.za  Wed Apr 17 12:47:33 1996
Received: from occam.gh.wits.ac.za  for craig;at;occam.gh.wits.ac.za
	by www.ccl.net (8.7.1/950822.1) id MAA20437; Wed, 17 Apr 1996 12:01:00 -0400 (EDT)
Received: (from craig- at -localhost) by occam.gh.wits.ac.za (8.6.12/8.6.9) id RAA04099; Wed, 17 Apr 1996 17:59:24 +0200
Date: Wed, 17 Apr 1996 17:59:24 +0200 (GMT+0200)
From: Craig Taverner <craig %-% at %-% hobbes.gh.wits.ac.za>
X-Sender: craig _-at-_)occam.gh.wits.ac.za
To: Rui Luo <rui \\at// iris6.carb.nist.gov>
cc: Robert Fraczkiewicz <robert%!at!%tocsy.utmb.edu>, chemistry%!at!%www.ccl.net
Subject: Re: CCL:Inside or outside of a polyhedron
In-Reply-To: <Pine.SGI.3.90.960415175329.15956A-!at!-iris6.carb.nist.gov>
Message-ID: <Pine.LNX.3.91.960417174807.3900B.,at,.occam.gh.wits.ac.za>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII


> Just an idea. It's very efficient, but not sure it's right.

Sorry, but it won't work.

> First transform the current coordinate system to one with the given point 
> (x,y,z) as the origin. I.e. subtrate (xi,yi,zi), where i=1,...,N, by 
> (x,y,z). This can be done very fast.
> 
> Second look at the sign of the transformed coordinates of all vertices. 
> If all xi's, where i=1,...,N, have the same sign, the point is outside 
> of the polyhedron. The statement holds for all yi's or all zi's. So if any 
> one of the three conditions holds, the point will be outside. Otherwise if 
> none of the conditions hold, it's inside.

If any one of your test conditions is true (eg, all x positive or all x 
negative) then yes the point is outside the polyhedron, however, if any 
number of tests is false, the point can still be outside the polyhedron.  
The tests only work one way.

Just consider a square on a 2-d surface with all sides at 45 degrees to 
the axes.  Place the origin just outside one side, and notice that your 
have points with both positive and negative values for both x and y axes.

Cheers, Craig

"Imagine if every Thursday your shoes exploded if you tied them the
 usual way.  This happens to us all the time with computers, and nobody
 thinks of complaining."
                -- Jeff Raskin, interviewed in Doctor Dobb's Journal

Craig Taverner
Structural Chemistry, University of the Witwatersrand, South Africa
tel:   +27-11-716-2290                fax: +27-11-716-3826
email: craig -8 at 8- hobbes.gh.wits.ac.za
www:   http://www.gh.wits.ac.za/craig