Path: utzoo!utgpu!news-server.csri.toronto.edu!clyde.concordia.ca!uunet!samsung!usc!ucsd!ucbvax!hplabs!hpcc01!hpsmdca!phil
From: phil@hpsmdca.HP.COM (Philip Walden)
Newsgroups: comp.graphics
Subject: Re: Point in Polygon Problem
Message-ID: <60110003@hpsmdca.HP.COM>
Date: 8 Aug 90 15:17:29 GMT
References: <5990@milton.u.washington.edu>
Organization: HP Product Generation Processes
Lines: 43

I use a simple routine that computes the sum of arc angles between the
test point and each vertex on the polygon. If the sum == 0, its outside
If the summ == 2pi its inside.

I have attached a brief explanation in pseudo-fortran. 
In the actual algorithm I use, the polygon can actually be a set
of polygons (members) such that "holes" can be created. The key to it all
is the fortran intrinsic ATAN2(rise,run) which returns the 4 quandrant
angle (-pi to pi) of the specified vector. Don't use ATAN(rise/run) as
it returns only 2 quadrant angles (-pi/2 to pi/2).

Yes it works for anything.

Brief explanation:
*************************
Is a point inside a polygon?

Use sum of arc angles:

Given a point (x,y) and a polygon SUM(i=1,n) (xi,yi), total arc angle is


sum = 0
for i = 1,n			! assumes (x1,y1) = (xn,yn)
do
        dx1 = (x - xi)
        dy1 = (y - yi)
        dx2 = (xi+1 - x)
        dy2 = (yi+1 - y)
        ds1 = SQRT(dx1**2 + dy1**2)
        ds2 = SQRT(dx2**2 + dy2**2)

        sini = (dx1*dy2 - dx2*dy1)/ds1*ds2 !from cross product
        cosi = (dx1*dx2 + dy1*dy2)/ds1*ds2 !from dot product
        sum = sum + atan2(sini,cosi)
end do

If |sum| > 0, point is inside


Note: you can skip the computation of ds1, ds2 and the divisions by ds1*ds2,
      as they cancel out in the atan2 function. I just put them in to
      clarify the algorithm.