Subject: Re: CCL:Inside or outside of a polyhedron

From: Alexander Golbraikh <[email-masked]>
Date: Wed, 17 Apr 1996 11:03:29 +0300 (EET DST)

On Tue, 16 Apr 1996, Brian W. Beck wrote:

> Alexander Golbraikh wrote:
> :
> :
> :
> : Take any ray beginning at the given point. Count the number of
> : points of intersection of this ray with polyhedron surface. If it is
> : even, then the point is outside the polyhedron, if it is odd, then inside.
> : One precaution: the ray may slide on some edges of the polyhedron.
> :
> : Best regards,
> : Alexander Golbraikh
> :
> :
>        ^ /
>        |/
>        <     As you say, the ray may slide. The "o" point at the left is
>        |\    outside the "polyhedron" yet passes through the polyhedron
>        | \   surface only once if you send the ray only through the vertices
>        o  \  defined by... say the Calphas of a protein.
>
> 	-Brian
> --

Thank you for your remark. I mean the point must be taken into
account in case the ray crosses the surface of the polyhedron, i.e. when
any whatever small segment of the ray containing this point
contains also points both in the inside and in the outside of the
polyhedron. Both cases could be easily discriminated. You may also ask
what to do if the given point belongs to the polyhedron surface. In this
case all depends on which polyhedron we consider: the closed or the open
one. (If we consider that the border (the surface) of the polyhedron
belongs to the polyhedron, it is closed). If it is closed, the point
belongs to the polyhedron (but isn't its inner point), if it is open, the
point doesn't belong to the polyhedron.

Alexander

+----------------------------------------------------------------------+
+  Dr. Alexander Golbraikh                   Email: [email-masked]  +
+  Group of Molecular Biophysics                                       +
+  Latvian Institute of Organic Synthesis    FAX:   + (371) 7-821-038  +
+  21 Aizkraukles st.                                                  +
+  Riga LV-1006                              Phone: + (371) 7-552-354  +
+  LATVIA                                                              +
+----------------------------------------------------------------------+

---

From: Craig Taverner <[email-masked]>
Date: Wed, 17 Apr 1996 17:59:24 +0200 (GMT+0200)

> 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: [email-masked]
www:   http://www.gh.wits.ac.za/craig