Sources
Help build the largest human-edited directory on the web.
Submit a site - Become an editor
Wikipedia. Licensed under the GNU Free Documentation License.
Are you an expert in this subject? Join the discussion and share your knowledge at Wikipedia.org.
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.
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."