Point in polygon

The point in polygon (PIP) problem and algorithms (also spelt point-in-polygon) are a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographical information systems (GIS), motion planning, CAD. The problem is to determine whether a given point in the plane lies inside, outside, or on the boundary of a polygon.

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 = (x₀,y₀) 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 y₀ and the other is greater than or equal to y₀, then:
    • if P lies in the half plane to the left of L, then set l := l + 1, else set r := r + 1 (*)
• 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 program, one would have to introduce a numerical tolerance eps and test in line (*) whether P lies within eps of L, in which case the algorithm should stop and report "P lies very close to the boundary."