@jim/spandex

Fast 2D spatial indexing with last-writer-wins semantics. Insert overlapping rectangles, library decomposes into disjoint fragments (≤4 per overlap).

Installation

Deno:

deno add jsr:@jim/spandex

import createMortonLinearScanIndex from '@jim/spandex/index/mortonlinearscan';

Node.js:

npx jsr add @jim/spandex

import createMortonLinearScanIndex from '@jim/spandex/index/mortonlinearscan';

Quick Start

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

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

// Insert regions using A1 notation (spreadsheet style)
adapter.insert('A1:C3', 'red');
adapter.insert('B2:D4', 'blue'); // Overlaps! LWW: blue wins in overlap

// Query returns non-overlapping fragments (as rectangles)
for (const [bounds, value] of adapter.query()) {
	console.log(bounds, value);
}
// Output:
// [0, 0, 2, 0] 'red'   (top row of red region)
// [0, 1, 0, 2] 'red'   (left column of red region)
// [1, 1, 3, 3] 'blue'  (blue covers entire overlap)

Algorithm Selection

import createMortonLinearScanIndex from '@jim/spandex/index/mortonlinearscan';
import createRStarTreeIndex from '@jim/spandex/index/rstartree';
import createLazyPartitionedIndex from '@jim/spandex/index/lazypartitionedindex';

// Sparse data (< 100 rectangles)
const sparse = createMortonLinearScanIndex<'red' | 'blue' | 'green'>();

// Large datasets (≥ 100 rectangles)
const large = createRStarTreeIndex<'header' | 'data' | 'footer'>();

// Partitioned by attribute
const partitioned = createLazyPartitionedIndex<{ color?: 'red' | 'blue'; bold?: boolean }>(
	createMortonLinearScanIndex,
);

Core Interface

interface SpatialIndex<T> {
	insert(bounds: Rectangle, value: T): void;
	query(bounds?: Rectangle): IterableIterator<[Rectangle, T]>;
	extent(): ExtentResult;
}

type Rectangle = readonly [xmin, ymin, xmax, ymax];

Coordinate Semantics

Closed intervals: All endpoints inclusive. [0, 0, 4, 4] = {(x,y) | 0 ≤ x ≤ 4, 0 ≤ y ≤ 4}.

Infinite bounds: Use ±Infinity for unbounded edges.

index.insert([-Infinity, 0, Infinity, 0], 'horizontal'); // Infinite left/right
index.insert([5, -Infinity, 5, Infinity], 'vertical'); // Infinite up/down

Adapters

// Google Sheets GridRange (half-open → closed)
import { createGridRangeAdapter } from '@jim/spandex/adapter/gridrange';
createGridRangeAdapter(index).insert({ startRowIndex: 0, endRowIndex: 5, ... }, value);

// A1 notation ("A1:C3", "B:B", "5:10", "D4")
import { createA1Adapter } from '@jim/spandex/adapter/a1';
createA1Adapter(index).insert('A1:C3', value);

Visualization

// ASCII (terminal)
import { createRenderer } from '@jim/spandex-ascii';
console.log(createRenderer().render(index, { legend }));

// HTML (browser)
import { createRenderer } from '@jim/spandex-html';
const html = createRenderer().render(index, { legend, showCoordinates: true });

Use Cases

Performance

Crossover n≈100. See BENCHMARKS.md for current measurements.

Implementation-Specific Methods

Diagnostic methods available on concrete types (not on SpatialIndex<T> interface):

import createMortonLinearScanIndex, { type MortonLinearScanIndex } from '@jim/spandex/index/mortonlinearscan';
import createRStarTreeIndex, { type RStarTreeIndex } from '@jim/spandex/index/rstartree';
import createLazyPartitionedIndex, { type LazyPartitionedIndex } from '@jim/spandex/index/lazypartitionedindex';

const morton = createMortonLinearScanIndex<'red' | 'blue'>();
morton.size(); // Count of stored rectangles (O(1))

const rtree = createRStarTreeIndex<'header' | 'data'>();
rtree.size(); // Count of stored rectangles (O(1))
rtree.getTreeQualityMetrics(); // { depth, overlapArea, deadSpace, nodeCount }

const partitioned = createLazyPartitionedIndex<{ color?: 'red' | 'blue' }>(createMortonLinearScanIndex);
partitioned.keys(); // Iterator of partition keys
partitioned.sizeOf('color'); // Count for specific partition
partitioned.isEmpty; // True if no partitions (getter)
partitioned.clear(); // Remove all partitions

Common Patterns

"Deleting": Use Last-Writer-Wins with null
Resetting: Create new instance

For detailed patterns (switching implementations, diagnostics), see PRODUCTION-GUIDE.md.

Documentation

New to spandex? Start with Getting Started for a comprehensive tutorial.

Need help? Check Troubleshooting for common issues.

More resources:

• Production Guide - Algorithm selection guide
• Benchmarks - Performance data
• Research Docs - Full documentation

Compatibility

Pure JavaScript (ES2020+) - works in any modern JavaScript runtime:

• Browsers, Node.js, Deno 2+, Bun
• Constrained environments: Google Apps Script, V8 isolates
• No WASM, SharedArrayBuffer, or native dependencies required

Works anywhere JavaScript runs.

Related Packages

• @jim/spandex-ascii - ASCII visualization for terminal/logs
• @jim/spandex-html - HTML visualization for browser debugging

Repository

GitHub Repository - Source code, issues, discussions

License

MIT