Point in polygon
|
|
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 simple polygon. It finds applications in areas that deal with processing geometrical data, such as computer graphics, geographical information systems (GIS), motion planning, and CAD.
Ray casting algorithms
One simple way of finding whether the point is inside or outside 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.
Below is another variant of this approach.
Let P = (x0,y0) be the point to be tested against a polygon specified by the ordered list of its vertices (and hence, edges).
- Set l := 0 and r := 0
- for each line segment L of the polygon do the following:
- if the y-coordinate of one endpoint of L is less than y0 and the other is greater than or equal to y0, then:
- if P lies in the half plane to the left of L, then set l := l + 1, else set r := r + 1 (*)
- if the y-coordinate of one endpoint of L is less than y0 and the other is greater than or equal to y0, then:
- if both l and r are odd, then P lies inside the polygon; if both l and r are even, then P lies outside the polygon; if one is even and the other is odd, then some error has occurred, e.g. a rounding error or the line segments do not form a closed path.
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."
External link
- C code to determine if a point is in a polygon (http://www.ecse.rpi.edu/Homepages/wrf/research/geom/pnpoly.html)