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