Implementing polygon containment checks in C++

In geospatial edge computing, determining whether a streaming coordinate falls within a predefined geofence is a foundational operation. For IoT gateways processing telemetry at the network edge, this predicate must execute deterministically within strict memory and CPU budgets, eliminating cloud round-trip latency and bandwidth overhead. This implementation operates within the broader framework of Local Spatial Processing Patterns, where computational overhead is minimized by pushing spatial logic directly onto constrained hardware. The specific technique detailed here falls under On-Device Geometry Filtering, targeting field-deployed devices that cannot afford dynamic allocation or unpredictable garbage collection pauses. When deploying across heterogeneous edge fleets—from ARM Cortex-M7 microcontrollers to x86_64 industrial gateways—the containment check must be allocation-free, branch-predictable, and tolerant of raw GPS drift.

Algorithm Selection & Constraint Mapping

The ray-casting algorithm (even-odd rule) remains the industry standard for on-device polygon containment due to its O(n) complexity, minimal state requirements, and predictable memory access patterns. Unlike winding-number approaches, which require tracking directional crossings and handling complex topological rules, ray-casting only requires counting edge intersections along a horizontal projection. On embedded Linux or bare-metal RTOS environments, this translates to deterministic cache behavior and zero heap fragmentation.

Ray-casting containment with an AABB early-exit and vertex tolerance.

flowchart TD
    S[Point + polygon + AABB] --> A{Inside AABB + epsilon?}
    A -->|no| F[Return false]
    A -->|yes| L[Loop edges j..i]
    L --> V{On a vertex?}
    V -->|yes| T[Return true]
    V -->|no| X{Crossing test true?}
    X -->|yes| TOG[Toggle inside flag]
    X -->|no| NX[Next edge]
    TOG --> NX
    NX --> D{More edges?}
    D -->|yes| L
    D -->|no| RET[Return inside flag]

The implementation enforces three deployment constraints critical to field reliability:

Zero dynamic allocation: All vertex data is passed via raw pointers or fixed-size arrays. No STL containers, no heap allocation, no exceptions.
Early-exit bounding box: A cheap AABB (axis-aligned bounding box) check filters ~70% of false positives before entering the intersection loop, preserving CPU cycles for high-frequency telemetry ingestion.
Boundary tolerance: GPS jitter rarely lands exactly on a vertex or edge. A configurable epsilon threshold prevents false negatives caused by coordinate quantization and atmospheric multipath errors.

Note on coordinate systems: Ray-casting assumes a planar Cartesian space. For geofences under ~5km radius, treating WGS84 lat/lon as planar coordinates introduces negligible error (<0.1m). Larger deployments require pre-projection to a local UTM zone or EPSG:3857 before ingestion.

Constraint-Tested C++ Implementation

The following header-only implementation is designed for direct inclusion in IoT gateway firmware. Compile with -O2 -fno-exceptions -fno-rtti -ffast-math for deterministic latency on constrained targets.

// geofence_containment.hpp
#pragma once
#include <cmath>
#include <cstddef>

struct Point2D {
    double lat;
    double lon;
};

struct Polygon {
    const Point2D* vertices;
    std::size_t count;
};

struct AABB {
    double min_lat, max_lat;
    double min_lon, max_lon;
};

// Precompute AABB for early-exit filtering. 
// Call once during geofence provisioning, not per-telemetry packet.
inline AABB compute_aabb(const Polygon& poly) {
    AABB box{poly.vertices[0].lat, poly.vertices[0].lat,
             poly.vertices[0].lon, poly.vertices[0].lon};
    for (std::size_t i = 1; i < poly.count; ++i) {
        if (poly.vertices[i].lat < box.min_lat) box.min_lat = poly.vertices[i].lat;
        if (poly.vertices[i].lat > box.max_lat) box.max_lat = poly.vertices[i].lat;
        if (poly.vertices[i].lon < box.min_lon) box.min_lon = poly.vertices[i].lon;
        if (poly.vertices[i].lon > box.max_lon) box.max_lon = poly.vertices[i].lon;
    }
    return box;
}

// Deterministic point-in-polygon check with epsilon tolerance and AABB early-exit.
// Division by zero is mathematically impossible due to the strict inequality guard.
[[nodiscard]] inline bool point_in_polygon(const Point2D& pt, 
                                           const Polygon& poly, 
                                           const AABB& box, 
                                           double epsilon = 1e-9) {
    // Early-exit AABB check (expanded by epsilon for boundary tolerance)
    if (pt.lat < box.min_lat - epsilon || pt.lat > box.max_lat + epsilon ||
        pt.lon < box.min_lon - epsilon || pt.lon > box.max_lon + epsilon) {
        return false;
    }

    bool inside = false;
    for (std::size_t i = 0, j = poly.count - 1; i < poly.count; j = i++) {
        double yi = poly.vertices[i].lat, xi = poly.vertices[i].lon;
        double yj = poly.vertices[j].lat, xj = poly.vertices[j].lon;

        // Vertex proximity check (handles GPS quantization on corners)
        if (std::abs(pt.lat - yi) < epsilon && std::abs(pt.lon - xi) < epsilon) {
            return true;
        }

        // Ray-casting intersection logic
        // (yi > pt.lat) != (yj > pt.lat) ensures yi != yj, preventing division by zero
        if (((yi > pt.lat) != (yj > pt.lat)) &&
            (pt.lon < (xj - xi) * (pt.lat - yi) / (yj - yi) + xi)) {
            inside = !inside;
        }
    }
    return inside;
}

Integration & Validation

Embedding this predicate into a telemetry processing loop requires strict adherence to memory layout and polling cadence. The AABB must be computed once during geofence provisioning and cached in read-only memory. Telemetry parsers should feed raw NMEA or binary payloads directly into Point2D structs without intermediate string parsing overhead.

// Example: High-frequency telemetry loop integration
void process_geofence_stream(const Point2D* telemetry_buffer, 
                             std::size_t buffer_len,
                             const Polygon& geofence,
                             const AABB& geofence_aabb) {
    for (std::size_t i = 0; i < buffer_len; ++i) {
        if (point_in_polygon(telemetry_buffer[i], geofence, geofence_aabb, 1.5e-5)) {
            // ~1.5e-5 epsilon ≈ 1.5 meters at equator
            trigger_edge_alert(telemetry_buffer[i]);
        }
    }
}

Validation against field-deployed hardware requires synthetic drift injection. Feed the function with coordinates oscillating ±2 meters around polygon edges to verify epsilon behavior. Cross-reference results against OGC Simple Features Specification compliance test suites to ensure topological consistency when migrating to multi-polygon or hole-containing geometries.

Edge Deployment & Performance Tuning

On memory-constrained RTOS targets, align vertex arrays to cache-line boundaries (typically 32 or 64 bytes) to prevent false sharing and reduce pipeline stalls. Use __attribute__((aligned(64))) for GCC/Clang or alignas(64) for C++17+ targets. When targeting ARM Cortex-M series, consult the ARM Cortex-M Optimization Guide to verify floating-point unit (FPU) utilization and ensure -mfpu=fpv4-sp-d16 or equivalent is enabled for hardware-accelerated double operations.

For Python developers interfacing with edge gateways, avoid serializing coordinates as JSON. Instead, pack lat/lon pairs into fixed-width binary frames (e.g., struct.pack('<dd', lat, lon)) and parse directly into Point2D via ctypes or memory views. This eliminates heap allocation in the gateway’s ingress buffer and maintains sub-millisecond predicate latency even at 10Hz+ ingestion rates.

When scaling to fleet-wide deployments, monitor branch misprediction rates using hardware performance counters. If inside = !inside toggles frequently due to highly concave geofences, consider pre-flattening complex boundaries into convex hulls or triangulated meshes during the provisioning phase. The ray-casting loop remains allocation-free, but reducing vertex count directly lowers instruction cache pressure and improves deterministic execution windows.

Implementing polygon containment checks in C++

Algorithm Selection & Constraint Mapping #

Constraint-Tested C++ Implementation #

Integration & Validation #

Edge Deployment & Performance Tuning #

Algorithm Selection & Constraint Mapping

Constraint-Tested C++ Implementation

Integration & Validation

Edge Deployment & Performance Tuning