Point in polygon
From Wikipedia, the free encyclopedia
In computational geometry, the point-in-polygon (PIP) problem asks whether a given point in the plane lies inside, outside, or on the boundary of a polygon. It finds applications in areas that deal with processing geometrical data, such as computer graphics, geographical information systems (GIS), motion planning, and CAD.
[edit] Ray casting algorithm
One simple way of finding whether the point is inside or outside a simple polygon is to test how many times a ray starting from the point intersects the edges of the polygon. If it is an even number of times, the point is outside, if odd, inside.
This algorithm does not always produce the correct answer if P lies directly on the polygon's boundary; if implemented on a computer with floating point arithmetic, the results may also be wrong if the point lies very close to that boundary, because of rounding errors. This is not normally a concern, as speed is much more important than complete accuracy in computer graphics. However, for a formally correct computer program, one would have to introduce a numerical tolerance ε and test in line (*) whether P lies within ε of L, in which case the algorithm should stop and report "P lies very close to the boundary."
