Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!wuarchive!cs.utexas.edu!uunet!brunix!dga
From: dga@cs.brown.edu (Daniel Gerardo Aliaga)
Newsgroups: comp.graphics
Subject: Re: Algorithm needed to determine if a point is inside a polygon
Keywords: polygon
Message-ID: <46093@brunix.UUCP>
Date: 28 Jul 90 06:51:22 GMT
References: <1990Jul27.201939.17816@cbnewsh.att.com>
Sender: news@brunix.UUCP
Reply-To: dga@cs.brown.edu (Daniel Gerardo Aliaga)
Distribution: na
Organization: Brown University Department of Computer Science
Lines: 66

In article <1990Jul27.201939.17816@cbnewsh.att.com> jmn@cbnewsh.att.com (john.b.medamana) writes:
>I am posting this article for a friend who works in the field of
>Urban Planning. 
>
>I am looking for software which determines whether an arbitrary
>point lies within or outside a polygon.  Please e-mail or post
>replys.
>
>Thanks in advance.
>
>John Medamana
>AT&T
>email:  att!arch3!johnm



One very simple algorithm (from some paper in SigGraph '89 I believe) is
take the dot product of the normal of each side of the polygon and the
vector formed by the point in question and a vertex of the current side. 
If all of these dot products are negative, the point is inside the object.
This of course can be generalized to the 3-D case. The disadvantage is that
this only works for convex polygons. 

graphically:


     |
 n   |
 <---|  /p
     | /
     |/v

If all the dot products <n,(p-v)> < 0, then p is inside convex polygon.



Alternatively, you could use an even odd rule if you have non convex polygons.
Imagine the 2-D case, take a polygon and draw a line through the point. If
that line intersects an even number of sides, it is inside else outside. This
may produce some hairy cases when the point is right on a side, or when the 
line you draw coincides exactly with one of the sides. You will have to
check for these cases.

graphically:
                _____
	       /     \
            ---       \_____
           |                \
           |         ---     |
      xxxxxxxxx p xxxxxxxxxxxxxxxxx
           \_______/     \___|

Notice that the line crosses the sides. It also coincides with a side.


These should work, good luck !


P.S. I have software for the first method, though it uses a in house 
polyhedra representation package, I could give you a copy ...


 XXXXXXXXXXXXXXX       XXXXXXXXXXXXXXXXXX      Daniel G. Aliaga '91
          XXX         XXX     XXXXX            Brown University
        XXXXXXXXXXXXXXXXXX 
         XXXXXXXXXXXXXXXXX		 "Real men write self modifying code"