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 algorithms

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.

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 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."

[edit] External links

• Point in polygon strategies
• C code to determine if a point is in a polygon
• C code for an algorithm using integers and no divides
• C code for determining if a point is inside a polygon that includes spline curves