Talk:Point in polygon

From Wikipedia, the free encyclopedia

The algorithm given in this page is not correct.
For example, consider the unit square polygon and a test point (0.5,0.5). The algorithm will terminate with either L=0,R=2 or L=2,R=0 (depending on which way you order the vertices). So the algorithm will report that the point is not within the polygon. Clearly, this is wrong.

Not clearly -- if you take 'left' to mean that the x of the point is less than the x of the segment at the level of y. -- It will always be to the right of the left hand segment, and to the left of the right hand segment, so L=1 and R=1. Drf5n 22:09, 10 August 2006 (UTC)

I would suggest this algorithm be removed, and this article only give short list of different strategies for solving this problem. Say, a summary of the article "Point in Polygon Strategies" by Eric Haines : http://www.acm.org/pubs/tog/editors/erich/ptinpoly/

It looks poorly transcribed from http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html Drf5n 21:47, 18 July 2006 (UTC)

I concur that the algorithm is not correct, but the above counterexample actually works. It's possible the algorithm was revised since the counterexample was written. Today, the algorithm gives the wrong answer if the point is inside a triangle with points (0,0), (10,0), and (10,10). For example, the point might be (9, 1). This terminates with l=0, r=1 which is an error condition, yet the polygon is closed and there were no rounding issues. I will be changing the main page to warn the unwary. Marc W. Abel 15:24, 4 August 2006 (UTC)

Are you sure it doesn't terminate properly with l=1 and r=1? The point (9,1) is to the left of the (10,0)-(10,10) segment, and to the right of the (0,0)-(10,10) segment. I don't think the test condition is clear. It might be best to think of this algorithm as drawing a line from (-infinity,y0) to (x0,y0) to (+infinity,y0) and counting the segments that cross the left hand ray (r) or the right hand ray (l). If you expect it to be a closed polygon, then whether or not either l or r is is odd or not tells you if it is in or out. The test requiring l and r to both be either even or both be odd is a weak sort of a test for the set of segments making up the polygon to be closed or not-- it tries two rays. But this algorithm doesn't test closedness well at all -- it completely ignores all the segments that don't intersect the horizontal line through x0. This algorithm is optimized for computational speed, rather than clarity. Drf5n 22:09, 10 August 2006 (UTC)