Edge Geospatial IoT Gateway Processing

Winding number vs ray casting for concave zones

Ray casting is the containment test everyone writes first, and for a simple polygon it is correct, fast and adequate. For the shapes a real operational zone set contains — self-touching boundaries, holes, a zone digitised twice with reversed winding, two administrative areas sharing an edge — it starts producing answers that depend on details nobody intended to specify. The winding number gives a different answer in exactly those cases, and knowing which one you want is the decision this page is about. It belongs to on-device geometry filtering inside Local Spatial Processing Patterns.

The two rules

Ray casting counts how many times a ray from the query point crosses the boundary. Odd means inside. This is the even-odd rule, and it treats a region enclosed twice — a polygon that loops back over itself — as outside, because the ray crosses it twice.

Winding number sums the signed turns the boundary makes around the query point. Non-zero means inside. A region enclosed twice in the same direction has a winding number of two and counts as inside; one enclosed clockwise and again anticlockwise has a winding number of zero and counts as outside.

For a simple, non-self-intersecting ring the two agree everywhere. The disagreement appears exactly where the geometry is not simple, which on a zone set imported from several sources is more often than anyone expects.

Where the two rules disagree Three shapes. A simple ring: both rules call the interior inside and agree everywhere. A self-overlapping shape where the boundary loops twice around a central region: ray casting calls that region outside because a ray crosses four times, while the winding number is two and calls it inside. A ring with an inner hole digitised in the same direction as the outer ring: ray casting correctly calls the hole outside, while the winding number is two and wrongly calls it inside — the hole must be wound in the opposite direction for the winding rule to work. Same query point, three geometries, two rules simple ring — both say inside self-overlap — ray says out, winding says in hole, same winding — ray right, winding wrong
Neither rule is correct in general. Each is correct for a data convention, and the convention is what the zone import has to enforce.

Both, in the same pass

The two rules share almost all of their work: both walk the edges, both test whether the edge straddles the query’s horizontal line, both compute the same side-of-line determinant. Computing them together costs one extra accumulator, which makes disagreement detectable rather than invisible.

/* contain.c — even-odd and winding-number containment in one pass.
 * Build: cc -O2 -fno-exceptions -c contain.c
 * Integer coordinates (projected centimetres) so the side test is exact:
 * a floating-point cross product near zero is the source of most
 * boundary-case disagreements between two implementations. */
#include <stdint.h>

typedef struct { int32_t x, y; } pt_t;

typedef struct {
    int inside_evenodd;      /* ray-casting verdict */
    int winding;             /* signed winding number */
    int on_boundary;         /* the query lies exactly on an edge */
} contain_t;

/* Sign of the cross product (b-a) x (p-a): >0 left, <0 right, 0 collinear. */
static int side_of(pt_t a, pt_t b, pt_t p)
{
    int64_t cross = (int64_t)(b.x - a.x) * (p.y - a.y)
                  - (int64_t)(b.y - a.y) * (p.x - a.x);
    return (cross > 0) - (cross < 0);
}

contain_t contain_point(const pt_t *ring, uint16_t n, pt_t p)
{
    contain_t out = {0, 0, 0};
    for (uint16_t i = 0, j = (uint16_t)(n - 1); i < n; j = i++) {
        pt_t a = ring[j], b = ring[i];

        /* Half-open crossing rule: count an edge only when one endpoint is
         * strictly above the ray and the other is not. This settles the
         * vertex-on-ray and horizontal-edge cases without a special case. */
        int a_above = a.y > p.y;
        int b_above = b.y > p.y;

        if (a_above != b_above) {
            int s = side_of(a, b, p);
            if (s == 0) { out.on_boundary = 1; }     /* exactly on this edge */
            /* Even-odd: crossing to the right of p flips the parity. */
            if ((b_above && s > 0) || (!b_above && s < 0)) {
                out.inside_evenodd ^= 1;
                /* Winding: upward crossing to the left adds, downward
                 * crossing to the right subtracts. */
                out.winding += b_above ? 1 : -1;
            }
        }
    }
    return out;
}

/* The caller decides which rule applies, and is told when they disagree. */
int contains(const pt_t *ring, uint16_t n, pt_t p, int use_winding,
             uint32_t *disagreements)
{
    contain_t c = contain_point(ring, n, p);
    int by_wind = c.winding != 0;
    if (by_wind != c.inside_evenodd) {
        (*disagreements)++;
    }
    return use_winding ? by_wind : c.inside_evenodd;
}

The disagreements counter is the reason to compute both. Exported as a metric, it says how often the zone set contains geometry where the rule choice matters — and on a well-formed layer it should be exactly zero forever. The first time it is not, a zone was imported with a winding or a self-intersection nobody checked, and it is far better to learn that from a counter than from a report of a missed crossing.

Cost of each rule at three polygon sizes Three polygon sizes measured on a Cortex-A53. At 40 vertices ray casting takes 1.9 microseconds, winding 2.1, and both computed together 2.2. At 400 vertices the figures are 17, 19 and 20 microseconds. At 4 000 vertices they are 168, 184 and 191. Computing both together costs between 12 and 15 percent over ray casting alone, which is the price of detecting a disagreement rather than silently picking one answer. Computing both costs 12–15% over computing one ray castingwindingboth, one pass 40 vertices 1.9 µs2.1 µs2.2 µs 400 vertices 17 µs19 µs20 µs 4 000 vertices 168 µs184 µs191 µs All three are linear in vertex count, which is why the prefilter in the parent guide matters far more than this choice does.
The performance difference is not the reason to choose between them. The data convention is.

Which rule for which data

Three data conventions cover most zone sets, and each implies a rule.

Simple rings, no holes — a fenced yard, a delivery zone, a site boundary. Both rules agree; use ray casting, and keep the disagreement counter as an import-validity check.

Rings with holes, wound oppositely — the GeoJSON and Shapefile convention, where an outer ring is anticlockwise and its holes are clockwise. Winding number is correct and even-odd also works, because opposite winding produces an even crossing count inside a hole. Either rule is safe provided the winding convention was honoured on import, which is the part that fails.

Rings with holes, all wound the same — common in data exported by tools that discard winding. Even-odd is correct here and winding is wrong: it reports the hole as inside. If the layer cannot be re-wound, use ray casting and record why.

The general rule: use even-odd unless the data has a winding convention you control and verify. Winding number’s extra expressiveness is only an advantage if the winding actually carries information, and in imported operational data it frequently does not.

Constraint validation

Constraint Expected impact Mitigation built into the code
CPU Both rules are linear in vertex count One pass computes both; the prefilter upstream is what bounds how often this runs
RAM No allocation is acceptable in the hot path Stack-only, integer arithmetic, no dynamic structures
Determinism Two devices must agree exactly Integer coordinates and an exact cross product; no floating-point comparison near zero
Correctness Boundary points are a contract decision on_boundary is returned rather than folded into the verdict
Observability A rule disagreement is invisible by default Disagreement counter exported as a metric

Gotchas and edge cases

  • The boundary is a third state, and the caller must define it. A point exactly on an edge is neither in nor out until someone decides. Define it once — “on the boundary counts as inside” is the usual choice — and apply it identically everywhere, including in the reconciliation running upstream.
  • Integer coordinates are what make this reproducible. In floating point, side_of near zero depends on rounding, so a point on an edge can be inside on one device and outside on another. The quantisation described in integer microdegree quantization is what makes the comparison exact.
  • Multi-part zones need the rule applied across all parts. A zone that is two disjoint areas is one logical zone; run the accumulation over every ring before deciding, rather than testing each ring independently and OR-ing the results, which gives the wrong answer for a hole in the second part.
  • The half-open crossing rule is not optional. Counting an edge when both endpoints are on the ray, or when one is exactly on it, double-counts and flips the parity. The a_above != b_above test with a strict comparison is what handles vertices and horizontal edges without special cases.
  • Validate winding at import, not at query time. Computing ring orientation is one pass over the vertices and it belongs in the layer import, where the answer can be recorded. Doing it per query is a linear cost paid over and over for an answer that never changes.
Import-time checks that make the query-time rule safe Four checks applied when a zone layer is imported. Ring closure confirms the first and last vertex coincide. Self-intersection detection flags rings whose edges cross, which is where the two rules diverge. Orientation records whether each ring is clockwise or anticlockwise, so hole convention can be verified. Duplicate-vertex removal drops repeated points that create zero-length edges. All four run once per import on the build host, and their results are recorded in the layer metadata rather than recomputed on the device. Four checks at import make the query-time choice a formality ring closure first vertex == last vertex an unclosed ring makes both rules meaningless self-intersection any pair of non-adjacent edges crossing the only place the two rules disagree orientation signed area per ring, recorded lets the hole convention be verified, not assumed duplicate vertices removed; zero-length edges dropped they contribute nothing and break side tests
Every one of these runs on the build host, once per layer. None of them belongs on the device, and all of them prevent a class of field bug.

Integration

Call the combined function from behind the envelope prefilter described in the parent guide, so it only ever runs on candidates. Pass use_winding from the layer metadata rather than hard-coding it — a fleet operating over several imported layers may legitimately need different rules for different ones, and the metadata is where that decision was already recorded.

Export the disagreement counter alongside the containment latency histogram. Together they say something no single metric does: how expensive the exact stage is, and whether the data it is running on is the shape everyone assumed.

Reconciling with the upstream engine

The device is rarely the only thing evaluating containment. A platform-side reconciler, a reporting query and an analyst’s desktop GIS all run their own tests, and they do not all use the same rule. PostGIS and most desktop tools apply the even-odd rule with an explicit handling of ring orientation; some rendering pipelines apply non-zero winding by default; and a hand-written service may do either.

The consequence is a class of dispute that is very hard to diagnose: the device says a vehicle was inside, the platform says it was not, both are running correct code, and the polygon has a self-intersection nobody has looked at since it was digitised in 2019.

Two habits prevent it. Record the rule with the verdict — one field, three possible values — so a disagreement is immediately attributable rather than mysterious. And run the reconciler’s rule against the device’s zone layer at import time, comparing verdicts over a grid of sample points across each zone’s envelope. Any point where the two disagree identifies a polygon that needs repairing, and finding those on a build host is a morning’s work against a lifetime of intermittent disputes.

Related in On-Device Geometry Filtering