How to use the point in polygon tester
- Enter the corners of the polygon in order, one "x, y" pair per line, going around the shape in either direction.
- Enter the points to test, one "x, y" pair per line, up to 1,000.
- Read the counts of points inside, on the edge and outside, then the table with both methods for each point.
- Check whether the polygon crosses itself, because only then can the two methods disagree.
Formula
Ray casting: count edges crossed by a ray from the point toward +x. Odd means inside.
Winding number: +1 for an edge crossing upward with the point on its left, -1 for downward; non-zero means inside.
On the edge: cross product of the edge and the point is 0 and the point lies within the segment.
Area (shoelace) = half the sum of (x_i y_(i+1) - x_(i+1) y_i)
The edge test allows a tolerance of one part in a billion of the polygon size, to absorb rounding in decimal coordinates.
A five-sided shape
The polygon has corners (0, 0), (6, 0), (6, 4), (3, 6) and (0, 4), an area of 30, and its corners run counterclockwise. Of the points (3, 3), (0, 0), (6, 2), (7, 3) and (3, 6.1), one is inside, two are on the edge and two are outside.
The point (3, 3) is inside. The corner (0, 0) and the point (6, 2) on the right edge are on the boundary. The points (7, 3) and (3, 6.1) are outside. The results agree with an independent geometry library on these points and on a concave arrow shape.
Two ways to decide
The crossing-number method draws a ray from the point and counts how many times it crosses the outline. An odd number means the point is inside. The winding-number method counts how many times the outline winds around the point, and a non-zero count means inside. For a polygon that does not cross itself both always agree, which is a useful check on the answer.
When the outline crosses itself, such as a bow tie or a five-pointed star drawn in one stroke, the methods can differ for points in the middle region. Ray casting treats the star center as outside, while the winding number counts it as inside because the outline circles it twice.
Practical uses and limits
Common uses include checking which points fall in a property outline, a service area or a game region. The page treats coordinates as flat. For latitude and longitude over small areas this works well, but over large distances the straight edges are not great-circle paths; see the great circle distance calculator for geography.
To get the area of the same outline use the polygon area from coordinates calculator, and for the smallest outline around a set of points see the convex hull calculator.
Assumptions and limits
- Coordinates are flat x and y values in one unit, and the polygon has 3 to 500 corners.
- The first corner is not repeated at the end of the list; the last corner connects back to the first.
- Points on the boundary are reported separately, using a tolerance of one part in a billion of the polygon size.
- Holes and multiple polygons are not supported; enter one outline at a time.
Frequently asked questions
Does the order of corners matter?
The corners must follow the outline in order, either clockwise or counterclockwise. A scrambled order draws a different shape, possibly one that crosses itself. The page reports the direction and whether edges cross.
What happens for a point exactly on a corner or an edge?
It is reported as on the edge, not inside or outside. Many simple programs give arbitrary answers for boundary points, so the page checks them first.
Why might the two methods disagree?
Only when the outline crosses itself. Even-odd ray casting and non-zero winding treat overlapping regions differently. For a simple polygon they cannot disagree, so any difference signals a self-crossing outline.
Can I test a point against several polygons?
Run the polygons one at a time. Each run accepts up to 1,000 points, so a long list of points can be sorted into one region per run.