Purpose: Perform a point-in-polygon spatial join — tag each point with the zone that contains it and roll the results up into per-zone counts (a choropleth).
Business problem: Spatial join is the workhorse of GIS analysis: which sales territory, census tract, flood zone, delivery region, or voting precinct does each record fall in?
Scope: Simple (non-self-intersecting) polygon rings tested with even-odd ray casting. Holes, multi-polygons, and bounding-box pre-filtering are future work.
Algorithm
Even-odd ray casting: A point is inside a ring when a ray cast from it crosses the ring's edges an odd number of times — the standard crossing-number test.
First-match assignment: Zones are tested in order and the first containing zone wins, giving deterministic behavior when zones overlap.
Flat ring layout: Across the ABI, all zone vertices are packed into one contiguous buffer with a per-zone ring-size array, avoiding per-polygon marshalling overhead.
Complexity: O(points × zone-vertices) in the brute-force MVP; a bounding-box or grid pre-filter would skip most edge tests for large layers.
API Layer
Controller:SpatialOverlayController is versioned at /api/v1/overlay and allows anonymous demo access.
Endpoint:POST /api/v1/overlay/spatial-join accepts SpatialJoinRequestDto (points and zone rings).
Response:SpatialJoinResultDto returns each point's zone index (-1 = outside all zones), per-zone summaries, and assigned/unassigned tallies.
Validation: The service enforces point and zone caps, a total-vertex cap, at least three vertices per ring, and finite coordinates.
Services and Native Boundary
Service:SpatialOverlayService validates input, dispatches to SpatialOverlayNativeBridge, and assembles per-zone rollups shared by both paths.
Native bridge:SpatialOverlayNativeBridge flattens zone rings into a single vertex buffer plus a ring-size array and reads back one zone index per point.
C++ library:native/spatial_overlay_kernel exposes Overlay_AssignPointsToZones, returning the number of assigned points.
Why C++ here: The crossing-number test is a branch-light arithmetic loop over contiguous vertex memory — a natural vectorization and cache-locality target at layer scale.
Managed fallback:SpatialOverlayService reproduces the identical even-odd test in C#, so the join is correct with no native library present.
Engineering Decisions and Tradeoffs
Even-odd over winding number: The crossing-number rule is simpler and sufficient for simple rings; winding-number handles self-intersections a demo layer will not contain.
First-match semantics: Deterministic and easy to explain; a production join might instead assign to all matching zones or the smallest-area zone.
Flat vertex ABI: One buffer + ring-size array keeps P/Invoke marshalling cheap and predictable versus arrays of jagged arrays.
Future improvements: Polygon holes and multi-polygons, R-tree/bounding-box pre-filtering, GeoJSON ingestion, and ArcGIS/Leaflet choropleth rendering over real administrative boundaries.
Interview Discussion Points
How does even-odd differ from the winding-number rule, and when does the difference matter?
What indexing structure would you add first to scale to millions of points?
How should the join behave when zones overlap or a point sits exactly on an edge?
Why is a flat vertex buffer a better ABI than passing jagged polygon arrays across P/Invoke?