Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!inria!geocub!pelegrin
From: pelegrin@geocub.greco-prog.fr
Newsgroups: comp.graphics
Subject: Re: Point in a polygon (3D case)
Message-ID: <1819@geocub.greco-prog.fr>
Date: 9 Apr 90 12:58:15 GMT
References: <5405@amelia.nas.nasa.gov> <2094@crash.cts.com>
Sender: news@geocub.greco-prog.fr
Reply-To: goofi!pelegrin@geocub.UUCP (Francois Pellegrini)
Organization: ENSERB University of Computer Science, Bordeaux, France
Lines: 45

In article <2094@crash.cts.com> jcs@crash.cts.com (John Schultz) writes:
>  Here's a similar problem I've been working on in 3-space- finding
>the intersection of a line with a polygon.  The solution I worked out
>involves computing the line/plane intersection point and then checking
>to see if the point is bounded by the polygon by rotating the polygon
>and point into a plane so that the point can be checked in 2-space, then
>check to see if the point is  bounded by the polygon by determining
>the orientation of the polygon (clockwise or counter) and computing
>cross-products with each line segment.  The sign can be checked to see
>which side the point lies on.
>  John

 I suggest some improvements :

  - Use dot products instead of cross products : for each segment [Ai;Ai+1],
    compute a vector Vi parallel to the plane, orthogonal to the given segment,
    and directed to the interior of the convex polygon.
    To check if a point is inside, perform for each segment the dot
    product : Vi . AiM
    If any of these is negative, the point is outside the polygon.
    (precompute the Vi and store them with the polygon data).

                  M
                _+ 
           /  _/                    \Polygon
          / _/         /|\Vi         \
         /_/            |             \
        //              |              \
       -----------------+----------------
      Ai                                    Ai+1

  - You may use first the intersection with a sphere to check if your
    plane/line intersection point will not be in an infinite distance.


			f.p.

-------------------------------------------------------------------------------
|   Zeu<FP> : The craziest programmer in France  |         _________          |
|------------------------------------------------|     /   |        \   \     |
| Francois Pellegrini is :                       |    /    |__   ___/    \    |
|      goofi!pelegrin@geocub.greco-prog.fr       |    \    |     |       /    |
| mcsun!inria!geocub!goofi!pelegrin@uunet.uu.net |     \   |     |      /     |
|         goofi!pelegrin@geocub.UUCP             |                            |
-------------------------------------------------------------------------------