Key Takeaways
- A low-altitude airspace platform handling 5,000 MQTT messages per second needed 10,000 point-in-polygon tests per second.
- Per-message cost was about 30 ms, of which roughly 25 ms was re-parsing 1,000 GeoJSON strings that never changed.
- Pre-parsing geometry once and indexing it with STRtree cut per-message cost to about 15 us, a 2000x reduction.
- CPU utilisation at 5,000 msg/s fell from 100 percent saturation to about 5 percent on the same eight cores.
STRtree spatial indexing is what turned a saturated low-altitude airspace monitoring platform into a service that idles at 5 percent CPU, and the fix was architectural rather than algorithmic. As of 2026 the system ingests 5,000 MQTT messages per second at peak, performs two spatial tests on each message, and answers each test in about 15 microseconds instead of 30 milliseconds. The lesson is that geometry is relatively stable while queries are high frequency, so parsing belongs before the query path, not inside it.
What the platform does
The system is a low-altitude airspace supervision platform: every networked drone reports its position over MQTT in real time, including latitude, longitude, altitude, speed and serial number, and the platform decides whether it has entered airspace it should not be in.
Prohibited areas fall into two classes:
- Airspace, based on geofences: airport clear zones, restricted flight corridors and altitude-capped protection areas. The rule is that a drone inside the polygon raises an alert, which may be a no-fly condition or a height limit.
- Controlled targets, based on sensitive points: government compounds, substations and correctional facilities. The rule is that no drone may enter a circle of a given radius around the point.
Every incoming position therefore has to be tested against these regions in real time, and a hit generates an alert for the duty operator.
The real traffic
- MQTT ingest: peaks at 5,000 msg/s during an event or a large security operation.
- Tests per message: two spatial decisions, one for airspace and one for controlled targets.
- Point-in-polygon rate: 10,000 per second.
- Data volume: more than 1,000 airspace polygons and more than 200 controlled targets.
What was wrong: architecture, not algorithm
CPU inspection showed one core pinned at 100 percent while the others idled. Reading the code showed that every message did three things:
per message:
1) parse 1,000 GeoJSON strings ~25 ms <- repeated, never reused
2) walk 1,000 polygons for MBR prefilter ~3 ms
3) point-in-polygon on tens of candidates ~2 ms
~30 ms per message
x 5,000 msg/s x 2 indexes = 100,000 ms of work per 1000 ms = 100 CPU coresThere were eight cores available.
The problem was not the algorithm but the architecture. The same airspace GeoJSON was parsed again by the next message one second later. The topological relationship of the geometry objects was recomputed on every query. And all 1,000 polygons had to be walked before it was known which ones could possibly hit.
The core contradiction in one sentence: geometry objects are relatively stable, because airspace does not change every second, but the decisions are high frequency, tens of thousands per second. Move parsing out of the decision path and do it once.
That is what STRtree provides.
The fix: STRtree coarse filter plus PreparedGeometry precise test
The design stacks two index layers:
+--------------------------------------------+
| AlarmSpatialIndex |
| |
| +------------+ +----------------------+|
| | STRtree | | IndexedAlarmItem ||
| | (MBR index)| -> | - Data ||
| | | | - Geometry (parsed) ||
| | coarse | | - PreparedGeometry ||
| | candidates | | - CityCode ||
| +------------+ +----------------------+|
| | | |
| | candidates k <= 5 | |
| +----------+------------+ |
| v |
| PreparedGeometry.Covers(point) |
| exact test (k is about 3) |
+--------------------------------------------+Why STRtree
STRtree is the general-purpose optimum within the R-tree family:
- It indexes by minimum bounding rectangle, giving O(log N + k) query cost.
- It handles irregular polygons well, which matters for airport clear zones and star-shaped protection areas.
- At N of 1,000 it is nowhere near the R-tree bottleneck region.
Why PreparedGeometry as well
STRtree only solves the coarse filter, and MBR intersection does not mean the point is inside the polygon.
After the coarse filter returns k candidates, each one still needs an exact point-in-polygon test. PreparedGeometry is a pre-warmed geometry object from NetTopologySuite: the polygon’s topology, its edge and face tables, is computed in advance and then looked up at query time, which is 2 to 5 times faster than calling Covers on a bare geometry.
| Metric | Value |
|---|---|
| Polygon count | 1,000 |
| Candidates after coarse filter | About 3 |
| Single query | 15 us |
The query path in code
// Service/AlarmService/AlarmSpatialIndex.cs QueryAsync · 88-128
public async Task<List<AlarmItem>> QueryAsync(MyGeoPoint point, int cityCode)
{
// 1. take the current snapshot (volatile read, cost is about zero)
var tree = _tree;
if (tree == null) tree = await EnsureReadyAsync();
else if (_dirty) _ = RebuildInBackgroundAsync();
// 2. zero-area envelope as a point query (standard STRtree usage)
var env = new Envelope(
point.Longitude, point.Longitude,
point.Latitude, point.Latitude);
var candidates = tree.Query(env); // <- O(log N + k)
if (candidates == null || candidates.Count == 0)
return new List<AlarmItem>();
// 3. exact point-in-polygon, candidates only
foreach (var item in candidates)
{
// city filter, avoids cross-city false alarms
if (cityCode > 0 && item.CityCode != cityCode) continue;
// exact test via PreparedGeometry, 2-5x faster
if (!item.Covers(point)) continue;
result.Add(item.Data);
}
return result;
}Three steps: take the snapshot, coarse-filter with a zero-area rectangle, then test the candidates exactly.
Concurrency: atomic snapshot, single writer, many readers
STRtree only supports concurrent reads when nothing is inserted after build. But airspace and controlled targets are added, removed and edited, so the index has to be rebuilt. The question is how to rebuild without blocking queries.
The answer is to swap the whole reference:
// AlarmSpatialIndex.cs field definitions
private volatile STRtree<IndexedAlarmItem>? _tree; // current snapshot
private volatile bool _dirty = true; // data changed flag
private readonly SemaphoreSlim _rebuildLock = new(1, 1); // rebuild mutex
// RebuildInBackgroundAsync · 181-218
private async Task RebuildInBackgroundAsync()
{
// failing to take the lock means a rebuild is already running, skip this round
if (!await _rebuildLock.WaitAsync(0)) return;
try
{
do
{
_dirty = false; // clear the flag FIRST, see below
var newTree = await RebuildAsync();
if (newTree != null) _tree = newTree; // whole-reference swap
else _dirty = true;
} while (_dirty);
}
finally { _rebuildLock.Release(); }
}Three details that matter:
- Swap the reference instead of mutating in place. Reader threads always see a complete, immutable tree. Assigning
_tree = newTreeis atomic, so a reader sees either the old tree or the new one, never a half-built one. - Clear
_dirtybefore building, not after. Otherwise a change that arrives during the build gets erased by this clear, and the data stays permanently out of sync. This is an easy trap to fall into. - Use
WaitAsync(0)for a non-blocking lock attempt. If the lock is taken, return immediately, so a burst of edits does not start a pile of duplicate rebuilds.
The read path is lock-free throughout. A reader during a rebuild sees the old snapshot, which is briefly stale and acceptable.
Warm-up at startup
Building the index takes about 100 ms, one full database read plus geometry parsing. Doing that synchronously on the query path would block the first batch of messages for 100 ms, and since MQTT delivers a batch every 100 ms with up to 500 messages each, subsequent requests would queue on the lock.
So the build moved to a startup warm-up:
// Service/AlarmService/AlarmIndexInitWorker.cs
public class AlarmIndexInitWorker : BackgroundService
{
private readonly IServiceScopeFactory _scopeFactory;
private readonly ILogger _logger;
protected override async Task ExecuteAsync(CancellationToken stoppingToken)
{
var sw = System.Diagnostics.Stopwatch.StartNew();
try
{
// must resolve through a scope: AlarmSpatialIndex is a Singleton,
// but LoadAllEnabledDataAsync uses the Scoped SqlSugarClient
using var scope = _scopeFactory.CreateScope();
var airspaceIndex = scope.ServiceProvider
.GetRequiredService<AlarmSpatialIndex>();
var targetIndex = scope.ServiceProvider
.GetRequiredService<AlarmSpatialIndex>();
// warm both indexes in parallel, halving the time
var targetWarmupTask = targetIndex.WarmupAsync();
var airspaceWarmupTask = airspaceIndex.WarmupAsync();
await Task.WhenAll(targetWarmupTask, airspaceWarmupTask);
_logger.LogInformation("Alarm spatial index warm-up done in {Elapsed}ms",
sw.ElapsedMilliseconds);
}
catch (Exception ex)
{
// do not rethrow: a failed warm-up degrades to rebuild-on-query
_logger.LogError(ex, "Alarm spatial index warm-up failed, will rebuild on first query");
}
}
}Three details again:
- Resolve services through
IServiceScopeFactory. The index is a Singleton, but loading data queries the database and the database client is Scoped. - Warm both indexes in parallel. Serially it takes 200 ms; in parallel, 100 ms.
- Do not throw on failure. A failed warm-up degrades to rebuild-on-query, and the service must never fail to start.
Registration order matters too. The worker must be registered before the MQTT service, because hosted services start in registration order, so the index is ready before message consumption begins.
The cost of this design is that for up to about 100 ms after a change the old index is still used. For drone alerts that is irrelevant, since a drone cannot cross into and out of an airspace in 100 ms.
Before and after
| Dimension | Before | After | Improvement |
|---|---|---|---|
| Per-message decision time | About 30 ms | About 15 us | 2000x |
| GeoJSON parsing | 1,000 per message | Once at startup | 5000x |
| CPU at 5,000 msg/s | 100 percent saturated | About 5 percent | 20x |
| Startup time | 0 | Plus 100 ms, once | Acceptable |
| Memory | Baseline | Plus 50 percent for parsed geometry | Traded for speed |
Building the index lazily on first query instead of warming up would mean 5,000 messages per second times 100 ms of blocking times 100 concurrent callers, which puts every subsequent request in a queue on the lock. Warming to zero blocking is the experience guarantee.
Choosing between STRtree, quadtree and H3
For point-in-polygon workloads there are four common options:
| Option | Time complexity | Measured at N=1000 | Best fit |
|---|---|---|---|
| STRtree (this project) | O(log N + k) | About 5 us | Irregular polygons, arbitrary distribution |
| Quadtree | O(sqrt N) | About 10 us | Point data, uniform distribution |
| H3 (Uber) | O(1) cell lookup | About 50 us | Large-scale aggregation, cross-city |
| Naive iteration | O(N) | About 3000 us | Only viable for tiny N |
STRtree won here for three reasons. The data are irregular polygons, including airport clear zones and star-shaped protection areas. At N of 1,000 the quadtree’s advantage region has not been reached. And point-in-polygon accuracy is sensitive, because a false alarm can turn into an enforcement dispute, which makes the cell approximation error of H3 unacceptable.
Test coverage
Thirty unit tests cover the critical paths in a separate xUnit project:
AlarmResponseTests.cs, 5 tests: multiple triggers on the response object.AlarmHitTests.cs, 4 tests: conversion from hit to target summary.ReceiveUdpDataAccessorTests.cs, 5 tests: has-alarm, primary alarm and alarm count.AlarmPriorityTests.cs, 9 tests: priority ordering.GetTargetIdScenariosTests.cs, 7 tests: six core scenarios plus parallelism.
All 30 pass in 21 ms with dotnet test. The six core scenarios are: single airspace hit, single controlled-target hit, simultaneous airspace and target hit, altitude-capped airspace hit, no hit, and parallel execution with priority ordering.
The most valuable test is scenario three, the simultaneous hit, because both alerts must reach the list and the ordering decides which one becomes the alert’s subject.
Six lessons
- Parse geometry once. Never construct geometry objects on the query path. Pay once, benefit forever.
- Rebuild by swapping the reference. Do not mutate in place, and the read path needs no lock.
- Clear the dirty flag before building. Otherwise a concurrent change is erased. It is counterintuitive and very easy to get wrong.
- Warm up into memory at startup. Avoid a cold-start block, and accept about 100 ms of staleness after changes, which is irrelevant for drone alerts.
- Pair PreparedGeometry with STRtree. That combination is the golden path for point-in-polygon in the NetTopologySuite ecosystem: coarse filter to single-digit candidates, then an exact test on each.
- Sort multiple alerts by business priority, not just by type. When airspace and controlled-target alerts fire together, the order decides the alert’s subject, and that matters to the operator.
Have questions about this article? Feel free to contact us at [email protected] — we’re happy to help!
Frequently Asked Questions
Why was the geofence check taking 30 ms per message?
Because every message re-parsed 1,000 GeoJSON strings at roughly 25 ms, then walked 1,000 polygons for an MBR prefilter at about 3 ms and ran exact tests on the candidates at about 2 ms. Almost all of the cost was repeated parsing.
How much faster is STRtree than naive iteration?
At N of 1,000, a single query takes about 5 us with STRtree against about 3000 us with naive iteration. Combined with pre-parsing, the whole per-message decision dropped from about 30 ms to about 15 us.
Why is PreparedGeometry needed if STRtree already indexes the polygons?
STRtree only returns candidates whose bounding rectangles intersect. A point can sit inside the rectangle but outside the actual polygon, so an exact point-in-polygon test is still required, and PreparedGeometry makes that test 2 to 5 times faster.
How does the index stay consistent while airspace data changes?
Rebuilds run in the background and swap the whole tree reference atomically, so readers always see a complete immutable snapshot. The dirty flag is cleared before building, and the lock is taken non-blocking to avoid duplicate rebuilds.
When should I use H3 instead of STRtree?
H3 suits large-scale aggregation and cross-city analytics where cell approximation is acceptable. For enforcement-grade geofencing, the approximation error can produce false alarms, so an exact polygon index is the safer choice.
About Aomway
Aomway is a radio-frequency engineering company that designs and manufactures long-range FPV video transmitters, antennas, goggles and UAV communication links, and it publishes technical notes on airspace systems, perception and embedded control. Its hardware is built for builders who need dependable links at range, and its documentation aims to explain the engineering behind each product.
