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