Path: utzoo!attcan!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!helios!gordon
From: gordon@cs.tamu.edu (Dan Gordon)
Newsgroups: comp.graphics
Subject: Re: Algorithm needed to determine if a point is inside a polygon
Keywords: polygon
Message-ID: <6951@helios.TAMU.EDU>
Date: 29 Jul 90 20:02:52 GMT
References: <1990Jul27.201939.17816@cbnewsh.att.com] <46093@brunix.UUCP>
Sender: usenet@helios.TAMU.EDU
Distribution: na
Organization: Computer Science Department, Texas A&M University
Lines: 25

In article <46093@brunix.UUCP] dga@cs.brown.edu (Daniel Gerardo Aliaga) writes:
]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.
]>
]>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. 

In 2-D, this algorithm takes time O(N), where N is the no. of points.
If you assume that the coordinates of the polygon are in arrays, then
there is a method of doing it in O(logN) time. It is only advantageous 
if your polygons have "lots" of vertices, where "lots" depends on your
computing environment and on how often you need to solve this problem.