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

From: Alexander Golbraikh <[email-masked]>
Date: Tue, 16 Apr 1996 11:50:50 +0300 (DST)

On Mon, 15 Apr 1996, Robert Fraczkiewicz wrote:

>
> Dear Netters,
>
> Suppose you have given N arbitrary points (in 3D space) that are vertices
> of a polyhedron: (x1,y1,z1),.....,(xN,yN,zN). What is the fastest
> algorithm for determining if a given point (x,y,z) is inside or outside of
> this polyhedron? (Calculating distances to every vertex is not a good
> idea). I will post summary to the net.
>
> Best regards,
>
> Robert Fraczkiewicz
> UT Medical Branch
>
>

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

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

---

From: [email-masked] (Brian W. Beck)
Date: Tue, 16 Apr 1996 08:35:45 -0700 (PDT)

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
-- 
=============================================================================
|   .---------.| Brian W. Beck      |    E-mail Addresses:                  |
|/\ |         || Biochem/Biophysics |        [email-masked]        |
|| \\     WSU || Washington St. Univ|   [email-masked]                  |
|\  -        *|| 206 Fulmer         |  URL  http://elmo.chem.wsu.edu/~brian |
| |           || Pullman, WA, USA   |    VOICE    (509) 335-4083            |
| \___________||       99164-4660   |      FAX    (509) 335-9688            |
=============================================================================