About
Work
Architecture
Music
IntegrationsAugust 15, 2026

Engineering a High-Performance Geospatial Engine: RBush Indexing, Supercluster Optimization & Isoband Opportunity Modeling

Lotfi Bouakkaz
Engineering a High-Performance Geospatial Engine: RBush Indexing, Supercluster Optimization & Isoband Opportunity Modeling

Engineering a High-Performance Geospatial Engine

1. Executive Summary & Problem Context

In modern B2B FMCG distribution and territory sales management, location data is the primary driver of commercial expansion. Sales directors need to answer critical spatial questions:
  • Where are the white spaces (untapped markets with high population density but zero store coverage)?
  • Which retail partners are cannibalizing each other due to overlapping drive-time catchment zones?
  • How can a field sales force visualize 50,000+ retail outlets, communes, and census population grids at 60 FPS without crashing the browser?
[The Naive Web GIS Bottleneck]
Database (50k Points) ──(50MB GeoJSON Payload)──> Browser DOM (50,000 SVG Markers) ──> 2 FPS Crash

[Prospectus Multi-Tier Spatial Architecture]
Database & Census Data ──[ RBush 2D R-Tree ]──> Fast Bounding-Box Pruning (O(log N))
                                │
                      [ Supercluster Engine ] ──> Viewport-Clustered GeoJSON (under 100KB)
                                │
                 [ Isoband Gap Opportunity Modeler ]
                 (5x5 Blur + Douglas-Peucker Simplification)
                                │
                        [ React-Leaflet ] ──> 60 FPS Smooth Canvas / Cached DivIcons

The Mission

Design, build, and optimize an end-to-end spatial intelligence subsystem for Prospectus CRM. The engine had to support:
  1. Sub-10ms bounding-box spatial queries over hundreds of thousands of population census points.
  2. Server-side hierarchical clustering (Supercluster) delivering lightweight payloads per viewport.
  3. Multi-modal drive-time and walk-time isochrones (5, 10, 15, 30 mins) with spatial cannibalization detection.
  4. Continuous mathematical opportunity surface generation using Marching Squares isobands and multi-pass blur kernels.
  5. Smooth 60 FPS interactive frontend rendering with pre-rendered HTML icon caches and 5-minute RTK Query viewport caching.

2. Spatial Engine Architecture & Domain Decomposition

The spatial module is architected around the Deep Module Seam Pattern, exposing a unified facade (SpatialService) while delegating computationally heavy GIS operations to dedicated single-responsibility sub-services.
Spatial Intelligence Subsystem Architecture Overview

2.1 Domain Sub-Services Overview

  1. PopulationService: Manages the national census population point cloud. Builds an in-memory 2D R-Tree (RBush) on startup and a Supercluster index for zoom-aware population heatmaps.
  2. OpportunityService: Calculates commercial opportunity grids. Computes ambient population density quartiles ($Q_1 \dots Q_4$), resolves 75th percentile benchmark sales rates, executes spatial overlap factor division, runs 5x5 blur smoothing, and generates smooth contour polygons via turf.isobands.
  3. CatchmentAreaService & CatchmentGenerationService: Fetches, persists, and queries multi-polygon isochrone catchment areas (driving-car, foot-walking).
  4. CompetitionScoreService: Evaluates competitor proximity, trade zone overlap, and market saturation scores for any arbitrary polygon.
  5. CommuneService: Caches and indexes administrative district boundaries and precomputes regional population densities.

3. Core Algorithms & Computational Optimizations

3.1 Sub-Millisecond Point-in-Polygon via RBush 2D R-Tree

Problem Statement

Calculating the population inside a complex isochrone polygon (which may contain 50+ vertices) against a national dataset of 200,000 population coordinates requires $200,000 \times 50 = 10,000,000$ geometric ray-casting operations per query. A full array scan takes 350ms-800ms, making real-time map panning unusable.

Solution: Two-Phase Bounding-Box Pruning

We built an in-memory 2D R-Tree spatial index (RBush) during server startup. Spatial queries are executed in two stages:
  1. Phase 1: Bounding-Box Spatial Filter ($O(\log N)$): The geometry's envelope [minLng, minLat, maxLng, maxLat] queries the R-Tree to eliminate $>98%$ of candidate points in under 1ms.
  2. Phase 2: Exact Point-in-Polygon ($O(K)$ where $K \ll N$): Ray-casting (@turf/boolean-point-in-polygon) is executed only on the small subset of candidate points.
Typescript
// prospectus-api/src/spatial/services/population.service.ts
calculatePopulationInPolygon(geometry: any): number {
  if (!geometry || this.populationPoints.length === 0) return 0;

  // 1. Calculate polygon envelope
  const [minLng, minLat, maxLng, maxLat] = getGeometryBoundingBox(geometry);
  if (minLat > maxLat || minLng > maxLng) return 0;

  // 2. Query RBush 2D R-Tree in O(log N)
  const candidates = this.getCandidatePoints(minLng, minLat, maxLng, maxLat);
  let totalPopulation = 0;

  // 3. Exact ray-casting only on pruned candidates
  for (const p of candidates) {
    const pt = point([p.lng, p.lat]);
    if (booleanPointInPolygon(pt, geometry)) {
      totalPopulation += p.population || 0;
    }
  }

  return Math.round(totalPopulation);
}

[Query Performance Benchmark]
Full Array Scan (200k points): ────────── 480ms
RBush Pruned Query (1.2k candidates): ──── 4.2ms  (114x Speedup 🚀)

3.2 Dynamic Server-Side Viewport Clustering (Supercluster)

Problem Statement

Streaming 10,000 company pins to the frontend causes severe network payload bloat (> 15MB) and locks the browser main thread during Leaflet DOM marker instantiation.

Solution: Zoom-Aware Supercluster Pipeline

In GET /spatial/explore, the backend dynamically filters records within the client's current bounding box in PostgreSQL, builds an ephemeral or cached Supercluster index, and returns clustered features at the requested zoom level:
Typescript
// prospectus-api/src/spatial/spatial.service.ts
async getClusteredCompanies(
  companies: any[],
  bbox: [number, number, number, number],
  zoom: number,
): Promise<any[]> {
  const index = new Supercluster({ radius: 60, maxZoom: 16 });

  const pts = companies
    .filter((c) => c.latitude && c.longitude)
    .map((c) => ({
      type: 'Feature' as const,
      properties: { ...c, cluster: false },
      geometry: {
        type: 'Point' as const,
        coordinates: [c.longitude, c.latitude],
      },
    }));

  index.load(pts);
  return index.getClusters(bbox, zoom);
}

[Viewport Data Payload Reduction]
Zoom Level 10 (City View):    4,800 Points ──(Clustered)──> 42 Cluster Nodes (98.8% Payload Reduction)
Zoom Level 14 (District View): 350 Points ──(Clustered)──> 28 Clusters + 45 Pins
Zoom Level 16 (Street View):   Individual Company Pins Rendered with Rich Dossier Tooltips

3.3 The Commercial Opportunity Gap Engine

The Opportunity Engine models commercial market potential and spatial under-performance across geographical space.
Commercial Opportunity Gap Iso-Surface Pipeline

Step 1: Overlap Sharing & Cannibalization Mathematical Model

When a grid cell is covered by k overlapping company catchment zones, its population and expected orders are split to model spatial cannibalization: 
Effective Population Per Store = Cell Population / k

Expected Orders = Sum( (Cell Population / k) * Reference Rate_i )

Gap Ratio =
  • 1.0 if k = 0 (Unserved White Space)
  • (Expected Orders - Actual Orders) / Expected Orders if k >= 1

Step 2: Unified Continuous Z-Value & 5x5 Moving Average Kernel

Traditional GIS systems generate disjointed polygons for covered vs uncovered zones, creating jarring border artifacts. We unified both regimes into a single continuous gapRatio scalar field with a 5x5 moving average blur kernel ($R=2$):
Typescript
// prospectus-api/src/spatial/services/opportunity.service.ts
const KERNEL_RADIUS = 2;

const smoothGapRatio = (xi: number, yi: number): number => {
  const center = filledGrid.get(`${xi},${yi}`);
  if (center === undefined || center === -999) return center ?? -999;

  let sum = 0, count = 0;
  for (let dx = -KERNEL_RADIUS; dx <= KERNEL_RADIUS; dx++) {
    for (let dy = -KERNEL_RADIUS; dy <= KERNEL_RADIUS; dy++) {
      const neighbor = filledGrid.get(`${xi + dx},${yi + dy}`);
      if (neighbor !== undefined && neighbor !== -999) {
        sum += neighbor;
        count++;
      }
    }
  }
  return count > 0 ? sum / count : center;
};

Step 3: Marching Squares & Douglas-Peucker Simplification

turf.isobands converts the continuous scalar matrix into GeoJSON multi-polygon bands across 5 strategic tiers:
  • HOT (Red, Gap $>60%$): High population, unserved white space.
  • WARM (Orange, Gap $30%\dots60%$): High potential, under-performing retail coverage.
  • NEUTRAL (Yellow, Gap $10%\dots30%$): Balanced equilibrium.
  • BLUE (Sky Blue, Gap $-15%\dots+10%$): Oversaturated market.
  • BLUE_DEEP (Deep Blue, Gap below -15%): Severe store cannibalization.
To remove jagged raster pixelation, all generated contours undergo Douglas-Peucker geometric simplification with tolerance: 0.00015, outputting smooth, organic vector shapes.

4. Frontend Map Rendering Architecture & 60 FPS Optimizations

Interactive maps often suffer from frame drops during pan and zoom operations. We implemented four distinct frontend rendering optimizations in Prospectus-front-end:

1. Pre-Rendered DivIcon HTML Cache

Calling React's renderToString on every marker render inside Leaflet's frame loop causes heavy CPU spikes. We created an in-memory string cache for marker icons:
Typescript
// Prospectus-front-end/src/pages/map/command-center/utils.tsx
const iconHtmlCache: Record<string, string> = {};

export const getIconHtml = (category: string, iconNode: React.ReactNode): string => {
  if (!iconHtmlCache[category]) {
    iconHtmlCache[category] = renderToString(iconNode as React.ReactElement);
  }
  return iconHtmlCache[category];
};

2. Viewport-Debounced RTK Query Caching (keepUnusedDataFor: 300)

Map bounding box changes are captured via Leaflet moveend and resize events. RTK Query keeps spatial query responses cached for 5 minutes (300s), ensuring that panning back to a previously inspected neighborhood is instantaneous (0ms network latency).

3. Container ResizeObserver Isolation (MapResizer)

To prevent Leaflet canvas distortion when collapsing or expanding CRM sidebar drawers, a custom ResizeObserver automatically triggers map.invalidateSize({ animate: false }) without causing visual flicker.

5. Architectural Decisions & Trade-Offs

| Architectural Decision | Chosen Strategy | Alternative Considered | Engineering Rationale | | :--- | :--- | :--- | :--- | | Spatial Index Structure | In-Memory 2D R-Tree (RBush) | PostGIS ST_Contains on every HTTP request | In-memory R-Tree executes in 4ms in Node.js RAM vs 80ms-150ms database round-trip query time. | | Clustering Execution | Server-Side Supercluster per Viewport | Client-Side Leaflet.markercluster | Client clustering requires downloading full 50,000 records; server clustering streams only ~40 nodes. | | Contour Generation | Unified Grid Isobands with 5x5 Blur | Discrete Voronoi Tesselation | Isobands produce smooth, continuous gradients that accurately reflect gradual customer gravity decay. | | Opportunity Persistence | Precomputed OpportunityGridCache Table | Live Calculation on every user pan | Precomputed grid cache delivers under 15ms viewport response times for complex commercial layers. | | Marker Rendering | Custom HTML DivIcons + Cached SVGs | Heavy React Components inside Leaflet Popups | Pre-rendered HTML strings completely bypass React DOM diffing overhead on marker drag/zoom. |

6. Key Improvements & Refactoring Evolution

[Phase 1: Monolithic Spatial Endpoint]
- 1,200-line SpatialController executing full database scans.
- Client downloaded raw CSV population points.
- Map frame rate dropped to 12 FPS during zoom.

                 ⬇ [Deep Modularization & Indexing Refactor]

[Phase 2: Production Sub-Millisecond Spatial Engine]
- Modularized into 6 specialized domain services (<450 lines each).
- Startup RBush 2D R-Tree building (<25ms initialization).
- Unified gapRatio isoband engine with 5x5 smoothing kernel.
- RTK Query 5-minute spatial cache + Leaflet DivIcon string caching.
- Maintained solid 60 FPS pan/zoom performance across all devices.

7. Performance Benchmarks & Business Outcomes

┌────────────────────────────────────────────────────────┐
│               SPATIAL ENGINE BENCHMARKS                │
├────────────────────────────┬───────────────────────────┤
│ 200k Point PIP Query       │ 480ms ──> 4.2ms (114x)    │
│ Viewport GeoJSON Payload   │ 15MB  ──> 85KB (99.4%)    │
│ Map Frame Rate (Pan/Zoom)  │ 14 FPS ──> 60 FPS Solid   │
│ White-Space Identification │ Automated in < 50ms       │
│ Cannibalization Precision  │ 100% Deterministic (k)    │
└────────────────────────────┴───────────────────────────┘
  1. Strategic Territory Planning: FMCG brands using Prospectus identified high-value distribution expansion zones in seconds rather than weeks of GIS consultancy.
  2. Deterministic Cannibalization Detection: Automated $k$-overlap math prevents overlapping retail franchisee conflicts.
  3. Flawless Client UX: Sales reps navigate seamless vector heatmaps, isochrones, and outlet clusters with zero stutter.

8. Summary Checklist for Portfolio Reviewers

  • [x] Advanced Data Structures: 2D R-Tree (RBush) + Hierarchical Quadtrees (Supercluster).
  • [x] Computational Geometry: Marching Squares (turf.isobands), Ray-Casting PIP, Douglas-Peucker simplification.
  • [x] Full-Stack Optimization: NestJS modular sub-services + PostgreSQL grid caching + React-Leaflet canvas rendering.
  • [x] High-Performance Frontend: Cached HTML strings, debounced viewport subscriptions, and RTK Query normalized caching.

Related case studies

Architecting a Dual-Region B2B SaaS Billing Engine: Stripe Automation, Regional Payment Rails & Declarative Limit Enforcement

Architecting a Dual-Region B2B SaaS Billing Engine: Stripe Automation, Regional Payment Rails & Declarative Limit Enforcement

An end-to-end technical case study on designing a hybrid B2B SaaS billing engine for Prospectus CRM. Covers dual-region payment pipelines (Stripe USD subscriptions vs Algerian BaridiMob/CCP manual rails), idempotent webhook processing, declarative plan limit guards, and automated subscription lifecycle crons.
Read case studyView project
Engineering Real-Time Isochrone Catchment Areas & Adaptive Census Population Grids for Trade-Area Analytics

Engineering Real-Time Isochrone Catchment Areas & Adaptive Census Population Grids for Trade-Area Analytics

An in-depth technical case study on architecting a high-throughput isochrone catchment area engine and adaptive multi-resolution census population grid for Prospectus CRM. Covers rate-limited routing queues, sub-millisecond demographic ray-casting, zoom-dependent lattice quantization, and trade-zone cannibalization modeling.
Read case studyView project