Spandex

Fast 2D spatial indexing with last-writer-wins semantics for JavaScript/TypeScript

Insert overlapping rectangles, get back non-overlapping fragments. O(n) for <100 ranges, O(log n) for ≥100.

Use cases: Spreadsheet formatting, GIS overlays, game collision, spatial databases.

Why Spandex?

You need to track which 2D regions have which properties, and regions can overlap:

Example: Spreadsheet cells with formatting (some cells red, some bold, ranges overlap)

The challenge: When range B2:D4 overwrites A1:C3, you need:

1. Old region split into non-overlapping pieces
2. New region preserved intact
3. Efficient queries ("what formatting applies to C2?")

Without spandex: Manual rectangle splitting (tricky, error-prone, easy to get wrong)

With spandex: index.insert() handles decomposition automatically with mathematical correctness guarantees

Real-world applications: Spreadsheets (cell properties), GIS (land parcels), Games (area-of-effect), Databases (2D spatial queries)

Quick Start

deno add jsr:@jim/spandex      # Deno
npx jsr add @jim/spandex       # Node.js

import createMortonLinearScanIndex from '@jim/spandex/index/mortonlinearscan';
import { createA1Adapter } from '@jim/spandex/adapter/a1';
import { createRenderer } from '@jim/spandex-ascii';

const index = createMortonLinearScanIndex<'red' | 'blue'>();
const adapter = createA1Adapter(index);

// Insert first region (A1:C3 in spreadsheet notation)
adapter.insert('A1:C3', 'red');

// Insert overlapping region (B2:D4 - last-writer-wins)
adapter.insert('B2:D4', 'blue');

// Visualize the decomposition
const { render } = createRenderer();
console.log(render(adapter, { legend: { R: 'red', B: 'blue' } }));
// Output:
//     A   B   C   D
//   ┏━━━┳━━━┳━━━┓   ·
// 1 ┃ R ┃ R ┃ R ┃
//   ┣━━━╋━━━╋━━━╋━━━┓
// 2 ┃ R ┃ B ┃ B ┃ B ┃
//   ┣━━━╋━━━╋━━━╋━━━┫
// 3 ┃ R ┃ B ┃ B ┃ B ┃
//   ┗━━━╋━━━╋━━━╋━━━┫
// 4     ┃ B ┃ B ┃ B ┃
//   ·   ┗━━━┻━━━┻━━━┛
//
// B = "blue"
// R = "red"

// Query returns 3 non-overlapping fragments
for (const [rect, value] of adapter.query()) {
	console.log(rect, value);
}
// [0,0,2,0] 'red'
// [0,1,0,2] 'red'
// [1,1,3,3] 'blue'

Red region split into 2 fragments, blue wins the overlap (3 total fragments).

Where to Go Next

New to spandex? → Getting Started Guide - 10-minute tutorial with examples

Choosing an algorithm? → Production Guide - Decision tree and performance data

Hit an error? → Troubleshooting - Common issues and solutions

Want the details? → Research Summary - Why these design choices? (5 min)

Contributing? → Contributing Guide - Development workflow

Published Packages

Compatibility: Pure JavaScript (ES2020+) - works in browsers, Node.js, Deno 2+, Bun, and constrained environments like Google Apps Script. No WASM or SharedArrayBuffer required.

Algorithm Selection

See PRODUCTION-GUIDE.md for decision tree and BENCHMARKS.md for measurements.

Documentation

Using: Getting Started • Production Guide • Troubleshooting • API Reference • Benchmarks • Statistics

Research: Summary (5 min overview) • All Docs • Theory

Contributing: Implementation Lifecycle • Benchmark Framework • Testing