From: adepaoli@plod.esrin.esa.it (Andy de Paoli)
Newsgroups: sci.math
Subject: Re: Point in space
Date: 10 Oct 1995 15:35:01 GMT

In article <4536bf$7em@netaxs.com>, tracor@netaxs.com says...
>Given- a grid X by Y
>     - an irregularly shaped polygon with N vertices (<20)
>       contained within the grid
>How do I determine if point(x,y) is within the polygon?

There are three possible algorithms:
the first is probably the most elegant, draw a ray from the point. 
If the number of sides it intersects is 0 mod 2 (i.e. even, 
including zero) then it is outside the polygon, if it is 1 mod 2 
then it is inside. The power of this algorithm is that your polygon 
may not even be simple (i.e. it may have "holes" in it) nor convex 
and it still works.

The second works only for convex polygons. Imagine each side to be a 
vector whose head is connected to the end of the following vector (a 
square would be four vectors sort of spin wheel fashion - sorry but 
I think an ASCII pic would be worse).
You then determine whether the point is to the same direction (i.e. 
to the left or to the right) of *all* the sides, if not it is 
outside, if yes then the orientation of the vectors tealls you that 
the point is inside (in the limit this is valid for closed curves).
(I have written up a short C code using this one.)

The third is to draw a vector from the point to each vertex 
sequentially. Then sum the angles so drawn (in the same order, 
including sum of last+first) if the point is inside then the sum 
will be 2*\pi (sign may be plus or minus) if it is outside then they 
will zero out. This algorithm has the disadvantage that the 
calculations of angles is given by the relations of the vectors and 
so may be slow in a real time situation.

You can get very good info regarding this in comp.graphics (I am not 
sure of the name) in the graphics FAQ, and excellent bibliography as 
well. In WWW search for the key words: point polygon inside, that 
should point you to it.

HTH,

cheers,

-- 
Andy de Paoli     e-mail: adepaoli@plod.esrin.esa.it
-----------------------------------------------------
If men with fleshy mortals must be fed ...
What else is this but to devour our guests...
Pythagoras  (6th cent. b.c.)

==============================================================================

Newsgroups: sci.math
From: jfran@world.std.com (Joseph A Francoeur)
Subject: Re: Algorithm for inside of polygon
Date: Wed, 3 Jan 1996 04:04:50 GMT

Have a look at the "Graphics Gems" series of books.  I think it's in 
Graphics Gems IV.  There's an interesting discussion of the point 
inclusion problem there.  I believe you can download source code written 
in C for the algorithms mentioned from ftp.princeton.edu.  If you just 
ftp to that site and hunt around, you may be able to come across the 
Graphics Gems directories.  Sorry for the fuzziness - I don't have exact 
references before me.

It appears that many people have worked on this problem, and there are a 
lot of considerations into making good fast algorithms.  I think there 
are faster algorithms available if you know you have a convex polygon.

I found the article in Graphics Gems very interesting - it takes you 
through the various trade-offs of the "usual" algorithms.

Joe