The eleventh Geometry entry, and the first built to be self-intersecting on purpose. Point in Polygon's ray-casting test answers "is this point inside?" by counting how many times a ray from the point crosses the boundary — odd means inside, even means outside. That page's own Pitfalls section verified a concave notch against an independent oracle: a from-scratch implementation of this algorithm, which tracks not just how many times the boundary crosses the ray but which direction it was heading each time, summing +1 for an upward crossing and −1 for a downward one instead of just flipping a boolean. On every polygon whose boundary never crosses itself, the two methods always agree — proven there, never contradicted. The question this page actually answers is what happens once that assumption breaks: build a boundary that genuinely winds around a region twice, and ray casting's odd-or-even parity check and this algorithm's signed running total stop being two ways of asking the same question.
A square with a second, smaller square nested inside it, both traced in the same
rotational direction and stitched into one continuous boundary by a zero-width slit on the top edge
— not two separate shapes, one single self-intersecting polygon. A point in the ring between the
two squares has the boundary wound around it once, same as any ordinary polygon. A point inside the
inner square has the boundary wound around it twice. Both panels below draw the
exact same boundary from the exact same vertex list — the only difference is the fill rule the
browser's own SVG renderer is told to use, evenodd on the left and nonzero
on the right, which is precisely the distinction this algorithm exists to make.
Both fill rules start from the identical per-edge test point-in-polygon.html uses: does this
edge's y-span straddle the query point's height, and does it cross to the right of the
point rather than the left? That test, run over every edge, produces the exact same set of
"crossings" no matter which rule reads the result afterward — the two algorithms are not two
different scans of the boundary, they're one scan totaled two different ways. The even-odd rule
throws away which direction each crossing was heading and just flips a boolean, so two crossings in
a row look identical to zero. The winding number keeps the direction: +1 for a crossing where the
edge was heading downward-to-upward through the query's height, −1 for upward-to-downward. Summed
over the whole boundary, that signed total is exactly the number of times the boundary loops around
the query point, net — a real topological quantity, not a parity trick. For a simple polygon (no
self-crossings), that quantity can only ever be −1, 0, or 1: the boundary either separates the plane
into one inside and one outside, or the point isn't enclosed at all, so "nonzero" and "odd" describe
the identical set of points. A self-intersecting boundary can wind around a point 2, −2, or any other
integer number of times, and that's precisely where "nonzero" and "odd" stop being the same
question — 2 is nonzero (winding rule: inside) but even (even-odd rule: outside).
The seam connecting the two squares is deliberately zero-width: enter the inner loop at one
vertex and leave from that same vertex, so the "in" and "out" edges of the slit are the identical
segment traversed forward and then immediately back. Whatever a query point's ray does to that
segment on the way in, it undoes on the way out — the near the seam preset
((279, 52)) confirms this directly, landing on exactly the same verdict as any other
ring point despite sitting right next to the stitch. The slit is bookkeeping to make one connected
vertex list out of two loops, not a real fifth edge with an opinion of its own.
function isLeft(a, b, pt) {
// > 0 if pt is left of the directed line a→b, < 0 if right, 0 if exactly on it
return (b.x - a.x) * (pt.y - a.y) - (pt.x - a.x) * (b.y - a.y);
}
function windingNumber(pt, poly) {
let wn = 0;
for (let i = 0, n = poly.length; i < n; i++) {
const a = poly[i], b = poly[(i + 1) % n];
if (a.y <= pt.y) {
if (b.y > pt.y && isLeft(a, b, pt) > 0) wn++; // upward crossing, to the right of pt
} else {
if (b.y <= pt.y && isLeft(a, b, pt) < 0) wn--; // downward crossing, to the right of pt
}
}
return wn; // nonzero means inside, regardless of how large the number gets
}Ray casting's even-odd rule doesn't fail rarely on this shape — it fails on exactly the
inner square, the whole thing, every time. At the doubly-wound center
preset (280, 180), the rightward ray crosses the boundary twice — once entering the
outer square's top edge, once entering the inner square's top edge — an even count, so ray casting
reports outside. The winding number sums those same two crossings as +1 and +1
(both edges head downward-to-upward through that height on the way the boundary was drawn),
totaling 2 — nonzero, so it reports inside, correctly: the
boundary really does enclose that point twice. This isn't a one-point coincidence: sweeping a grid
of 53,671 points (every 2 pixels across the full 560×380 canvas) found the two rules disagree on
exactly 3,600 of them — which is exactly the inner square's own 120×120 area
divided by the 2×2 sampling cell, not an approximate match — and agree that the point is inside on
another 13,300, exactly the ring's area (260×260 minus 120×120) divided the same way. The
disagreement isn't scattered noise near an edge case; it's confined to precisely, exhaustively, the
one region that's genuinely wound twice.
Dropping the isLeft "which side" check and just tallying every
height-crossing edge by direction throws away the algorithm's only dependence on the query point's
x-coordinate. That check is what limits the tally to crossings happening
specifically to the right of the point, the same role point-in-polygon.html's
pt.x < ix comparison plays; remove it and every edge whose endpoints straddle the
query's height contributes regardless of where the point sits sideways. Concretely, at height
y=80 the real winding number is 1 at x=280 (inside the
ring) and 0 at x=1000 (empty space, nowhere near either square) —
genuinely different answers for genuinely different points — but the broken version returns
0 for both, because it never once looks at x. Sweeping a grid wider
than the shape itself (roughly double the canvas in each direction) confirms it's not a lucky
near-miss: 4,225 of 22,538 sampled points, 18.7%, come out wrong.
Time: O(n) per query, identical to
Point in Polygon — one constant-time test per edge,
no early exit. Space: O(1) beyond the polygon itself. The per-edge
work costs one extra multiplication and comparison over plain ray casting (the isLeft
product, instead of just the crossing test), for a result that's a superset of what ray casting
reports: on any simple polygon the two never disagree, so reach for the simpler even-odd boolean
there and save the extra arithmetic; reach for this instead the moment the polygon might be
self-intersecting, or the caller cares about how many times a region is enclosed rather
than just whether it is.
This site's guide, Choosing a Geometry
Algorithm, places this entry alongside Point in
Polygon as the two answers to the same one-off containment question, at the same
O(n)/O(1) cost — reach for this one only once the polygon might not be
simple.