Point in Polygon: Ray Casting vs Winding Number

The idea: count the walls you cross

You stand at a point Q and want to know if you are inside a room. Walk in a straight line until you are far away, and count the walls you pass through. Each wall flips you between inside and outside, and far away you are outside. So an odd number of walls means you started inside, and an even number means outside.

This is the most common question asked of a polygon. A map asks which country or delivery zone a GPS point is in, a game asks if a unit is in a region, and a drawing app asks which shape the mouse is over (hit testing). The page shows the two standard answers, ray casting and the winding number, on a polygon with whole-number corners so every number can be checked by hand.

Ray casting (the even-odd rule)

Shoot a ray from Q to the right, along the line y = Q.y. For each edge a→b:

1. If both ends are above the line, or both are below it, the edge cannot meet the ray. Skip it.
2. Otherwise find where the edge meets the line: x = a.x + (Q.y − a.y)·(b.x − a.x) / (b.y − a.y).
3. If that x is right of Q, the ray crosses the edge: count it.

An odd count means inside. W. R. Franklin's well-known PNPOLY code is just this loop:

inside = false
for each edge (a, b):
    if (a.y > q.y) != (b.y > q.y):
        x = a.x + (q.y - a.y) * (b.x - a.x) / (b.y - a.y)
        if q.x < x: inside = not inside

In the room shape, Q at (4, 10) sees 4 edges straddle its line. K→A meets it at x = 2, left of Q, so it does not count. I→J (x = 6), G→H (x = 14) and E→F (x = 18) do: 3 crossings, inside (Demo: ray casting, Q in the left arm). From the gap at (10, 10), only G→H and E→F are to the right: 2 crossings, outside (Demo: ray casting, Q in the gap).

When the ray hits a corner

A ray can pass exactly through a corner. Counting both edges that meet there gives 2, counting none gives 0, and only one of those can be right. The test (a.y > q.y) != (b.y > q.y) settles it without a special case: a corner on the line counts as just above it (a half-open rule).

• If the corner is a tip and both of its edges go down from it, neither edge straddles the line: 0 crossings. The ray only touched the tip, so 0 is right.
• If one edge goes up from the corner and the other goes down, exactly one of them straddles: 1 crossing, as for a plain edge.

Q at (4, 4) has its ray pass through corner C (10, 4), the tip of a notch in the floor. B→C and C→D both have C on the line and their other end below, so neither counts; only E→F does: 1 crossing, inside (Demo: the ray passes through a corner). A horizontal edge lying on the line has both ends "above", so it is skipped too.

The winding number (the nonzero rule)

Walk once around the polygon and watch Q. The winding number is how many times the boundary goes around Q counter-clockwise. It is 0 for a point outside and ±1 for a point inside a simple polygon. It can be counted on the same ray, with a sign per crossing:

• an edge that goes up past the line (a.y ≤ Q.y < b.y) with Q on its left adds +1;
• an edge that goes down past the line (b.y ≤ Q.y < a.y) with Q on its right adds −1.

Left or right is the sign of the cross product cross(a, b, Q) = (b.x − a.x)·(Q.y − a.y) − (b.y − a.y)·(Q.x − a.x), the same orientation test as in Convex Hull: Graham Scan vs Gift Wrapping. With whole numbers it is exact, and there is no division. This version is due to Dan Sunday. In the room, from (4, 10): I→J +1, G→H −1, E→F +1, total 1, inside (Demo: winding number on the same Q). The room is drawn counter-clockwise, so inside points get +1; a clockwise copy would give −1.

When the two rules disagree

For a simple polygon (no edge crosses another) both rules give the same answer. A polygon that crosses itself is different. In a five-pointed star drawn in one stroke, the boundary goes around the centre twice. From the centre (10, 7) the ray crosses B→C and E→A: 2 crossings, so even-odd says outside, but both edges go up with Q on their left, so the winding number is 2 and nonzero says inside (Demo: star, even-odd says out, winding says in).

These are the two fill-rule values of SVG and the HTML canvas, evenodd and nonzero (the default). A font or icon designer uses nonzero to fill overlapping strokes, and even-odd or an opposite-direction inner path to cut holes. On the page the orange area shows the points where the rules disagree.

Case	Crossings	Even-odd	Winding number	Nonzero
Room, Q in the left arm (4, 10)	3	inside	1	inside
Room, Q in the gap (10, 10)	2	outside	0	outside
Room, ray through corner C (4, 4)	1	inside	1	inside
Room, Q left of the shape (1, 8)	4	outside	0	outside
Star, Q in the centre (10, 7)	2	outside	2	inside
Star, Q in the top tip (10, 12)	1	inside	1	inside

Cost and where it is used

Both methods look at every edge once: O(n) per point for a polygon with n edges, with no memory beyond a counter. That is fine for one query. When millions of points must be tested against thousands of polygons, systems first throw away most polygons with a cheap bounding-box test or a spatial index, and only run the edge loop on the few left; see quadtrees and geohashes. PostGIS's ST_Contains and GEOS work this way. A convex polygon can be tested in O(log n) by binary search on the corners around a fixed one.

A GPU fills a triangle with the same kind of left-or-right edge test, run for every pixel; see Rasterization: Edge Functions and the Z-Buffer. The cross product itself is explained in vectors, the dot product and the cross product.

Both rules rest on the same orientation test used to find crossing segments: see Segment Intersection.

What the page leaves out

The page skips points that lie exactly on an edge (ray casting puts them on one side or the other by the half-open rule; GIS libraries report "on the boundary" separately), floating-point coordinates, where a cross product near 0 can get the wrong sign, polygons with holes (a list of rings, inner rings drawn the other way), points on a sphere (latitude and longitude, where edges are great-circle arcs), and the faster pre-processed methods: slab decomposition, trapezoidal maps and grids of cells.

References

W. Randolph Franklin, PNPOLY: point inclusion in polygon test

Point in polygon (Wikipedia)

K. Hormann and A. Agathos, "The point in polygon problem for arbitrary polygons", Computational Geometry, 2001

SVG 2: the fill-rule property (nonzero, evenodd)