0
# RBush
1

2
RBush is a high-performance JavaScript library for 2D spatial indexing of points and rectangles. It's based on an optimized R-tree data structure with bulk insertion support, enabling efficient spatial queries like "all items within this bounding box" that can be hundreds of times faster than traditional iteration approaches.
3

4
## Package Information
5

6
- **Package Name**: rbush
7
- **Package Type**: npm
8
- **Language**: JavaScript
9
- **Installation**: `npm install rbush`
10

11
## Core Imports
12

13
ESM (ES Module):
14

15
```javascript
16
import RBush from 'rbush';
17
```
18

19
CommonJS:
20

21
```javascript
22
const RBush = require('rbush');
23
```
24

25
Browser (via CDN):
26

27
```html
28
<script type="module">
29
    import RBush from 'https://cdn.jsdelivr.net/npm/rbush/+esm';
30
</script>
31
```
32

33
Browser (global variable):
34

35
```html
36
<script src="https://cdn.jsdelivr.net/npm/rbush"></script>
37
<!-- RBush is available as global variable -->
38
```
39

40
## Basic Usage
41

42
```javascript
43
import RBush from 'rbush';
44

45
// Create a new spatial index (default maxEntries: 9)
46
const tree = new RBush();
47

48
// Define spatial items with minX, minY, maxX, maxY properties
49
const rect1 = {
50
  minX: 20, minY: 40, maxX: 30, maxY: 50,
51
  id: 'rectangle-1' // additional properties are preserved
52
};
53

54
const rect2 = {
55
  minX: 0, minY: 0, maxX: 10, maxY: 10,
56
  id: 'rectangle-2'
57
};
58

59
// Insert single items
60
tree.insert(rect1);
61

62
// Bulk load multiple items (2-3x faster than individual inserts)
63
const moreRects = [
64
  { minX: 15, minY: 15, maxX: 25, maxY: 25, id: 'rectangle-3' },
65
  { minX: 35, minY: 35, maxX: 45, maxY: 45, id: 'rectangle-4' }
66
];
67
tree.load(moreRects);
68

69
// Search for all items intersecting a bounding box
70
const searchArea = { minX: 10, minY: 10, maxX: 50, maxY: 50 };
71
const intersectingItems = tree.search(searchArea);
72
console.log(`Found ${intersectingItems.length} intersecting items`);
73

74
// Quick collision detection (faster than search when you only need true/false)
75
const hasCollisions = tree.collides(searchArea);
76
console.log(`Collisions detected: ${hasCollisions}`);
77

78
// Get all items in the index
79
const allItems = tree.all();
80
console.log(`Total items in tree: ${allItems.length}`);
81
```
82

83
## Architecture
84

85
RBush implements an optimized R-tree data structure with the following key components:
86

87
- **R-tree Structure**: Hierarchical bounding boxes for efficient spatial queries
88
- **Bulk Loading**: OMT (Overlap Minimizing Top-down) algorithm for initial data loading
89
- **Bulk Insertion**: STLT (Small-Tree-Large-Tree) algorithm for efficient batch insertions
90
- **Customizable Data Format**: Override methods to work with custom data structures
91
- **Serialization Support**: Export/import tree data as JSON for client-server workflows
92

93
## Capabilities
94

95
### Tree Creation and Configuration
96

97
Create a new RBush instance with optional node size configuration.
98

99
```javascript
100
import RBush from 'rbush';
101
```
102

103
```javascript { .api }
104
/**
105
 * Creates a new RBush spatial index
106
 * @param maxEntries - Maximum entries in a tree node (default: 9, range: 4-∞)
107
 * Higher values mean faster insertion but slower search, and vice versa
108
 */
109
constructor(maxEntries?: number): RBush;
110
```
111

112
### Spatial Search Operations
113

114
Core search functionality for finding items within spatial bounds.
115

116
```javascript
117
import RBush from 'rbush';
118
const tree = new RBush();
119
```
120

121
```javascript { .api }
122
/**
123
 * Search for all items intersecting the given bounding box
124
 * @param bbox - Bounding box with minX, minY, maxX, maxY properties (required)
125
 * @returns Array of data items that intersect the bounding box (empty array if none found)
126
 * @throws No exceptions - returns empty array for invalid bounding boxes
127
 */
128
search(bbox: BoundingBox): any[];
129

130
/**
131
 * Get all items stored in the spatial index
132
 * @returns Array of all items stored in the tree (empty array if tree is empty)
133
 */
134
all(): any[];
135

136
/**
137
 * Check if any items intersect the given bounding box without returning them
138
 * Performance: Faster than search() when you only need boolean result
139
 * @param bbox - Bounding box with minX, minY, maxX, maxY properties (required)
140
 * @returns True if any items intersect the bounding box, false otherwise
141
 * @throws No exceptions - returns false for invalid bounding boxes
142
 */
143
collides(bbox: BoundingBox): boolean;
144
```
145

146
### Data Insertion and Modification
147

148
Methods for adding, removing, and managing data in the spatial index.
149

150
```javascript
151
import RBush from 'rbush';
152
const tree = new RBush();
153
```
154

155
```javascript { .api }
156
/**
157
 * Insert a single item into the spatial index
158
 * @param item - Data item with spatial bounds (minX, minY, maxX, maxY properties)
159
 *               Additional properties are preserved. Pass undefined/null to do nothing.
160
 * @returns this (for method chaining)
161
 * @throws No exceptions - silently ignores undefined/null items
162
 */
163
insert(item: any): RBush;
164

165
/**
166
 * Bulk load an array of items (2-3x faster than individual inserts)
167
 * Optimal for initial loading or batch insertions into empty/sparse trees
168
 * @param data - Array of data items to insert (each with minX, minY, maxX, maxY)
169
 *               Empty arrays are handled gracefully (no-op)
170
 * @returns this (for method chaining)
171
 * @throws No exceptions - handles empty/invalid arrays gracefully
172
 */
173
load(data: any[]): RBush;
174

175
/**
176
 * Remove an item from the spatial index
177
 * Uses reference equality by default, custom equality function for value-based removal
178
 * @param item - Item to remove (must have spatial bounds for traversal)
179
 *               Pass undefined/null to do nothing.
180
 * @param equalsFn - Optional custom equality function (a, b) => boolean
181
 *                   Useful for removing by ID or other properties
182
 * @returns this (for method chaining)
183
 * @throws No exceptions - silently handles items not found
184
 */
185
remove(item: any, equalsFn?: (a: any, b: any) => boolean): RBush;
186

187
/**
188
 * Remove all items from the spatial index, resetting to empty state
189
 * @returns this (for method chaining)
190
 */
191
clear(): RBush;
192
```
193

194
### Serialization and Export
195

196
Methods for saving and restoring tree data for client-server workflows.
197

198
```javascript
199
import RBush from 'rbush';
200
const tree = new RBush();
201
```
202

203
```javascript { .api }
204
/**
205
 * Export tree data as JSON object for serialization
206
 * Preserves complete tree structure including spatial bounds and user data
207
 * @returns Object representing the internal tree structure (can be stringified)
208
 */
209
toJSON(): object;
210

211
/**
212
 * Import previously exported tree data
213
 * Note: maxEntries parameter must match between export and import trees
214
 * @param data - Previously exported tree data from toJSON()
215
 * @returns this (for method chaining)
216
 * @throws No validation - assumes data is valid tree structure
217
 */
218
fromJSON(data: object): RBush;
219
```
220

221
### Data Format Customization
222

223
Overrideable methods for working with custom data structures (e.g., points, custom geometries).
224

225
```javascript
226
import RBush from 'rbush';
227
// Extend RBush to customize data format
228
class MyRBush extends RBush {
229
  // Override methods as needed
230
}
231
```
232

233
```javascript { .api }
234
/**
235
 * Convert data item to bounding box format (override for custom data structures)
236
 * Default implementation expects items to already have minX, minY, maxX, maxY
237
 * @param item - Data item in your custom format
238
 * @returns Bounding box with minX, minY, maxX, maxY properties (required)
239
 * @example
240
 * // For point data [x, y]
241
 * toBBox([x, y]) { return {minX: x, minY: y, maxX: x, maxY: y}; }
242
 */
243
toBBox(item: any): BoundingBox;
244

245
/**
246
 * Compare function for X-axis sorting during tree construction (override for custom data)
247
 * Default implementation compares item.minX values
248
 * @param a - First item to compare
249
 * @param b - Second item to compare  
250
 * @returns Negative if a < b, zero if equal, positive if a > b
251
 */
252
compareMinX(a: any, b: any): number;
253

254
/**
255
 * Compare function for Y-axis sorting during tree construction (override for custom data)
256
 * Default implementation compares item.minY values
257
 * @param a - First item to compare
258
 * @param b - Second item to compare
259
 * @returns Negative if a < b, zero if equal, positive if a > b
260
 */
261
compareMinY(a: any, b: any): number;
262
```
263

264
## Types
265

266
```javascript { .api }
267
/**
268
 * Bounding box interface for spatial queries
269
 */
270
interface BoundingBox {
271
  minX: number;
272
  minY: number;
273
  maxX: number;
274
  maxY: number;
275
}
276

277
/**
278
 * Main RBush class for spatial indexing
279
 */
280
class RBush {
281
  constructor(maxEntries?: number);
282
  
283
  // Search methods
284
  search(bbox: BoundingBox): any[];
285
  all(): any[];
286
  collides(bbox: BoundingBox): boolean;
287
  
288
  // Modification methods
289
  insert(item: any): RBush;
290
  load(data: any[]): RBush;
291
  remove(item: any, equalsFn?: (a: any, b: any) => boolean): RBush;
292
  clear(): RBush;
293
  
294
  // Serialization methods
295
  toJSON(): object;
296
  fromJSON(data: object): RBush;
297
  
298
  // Customization methods (overrideable)
299
  toBBox(item: any): BoundingBox;
300
  compareMinX(a: any, b: any): number;
301
  compareMinY(a: any, b: any): number;
302
}
303
```
304

305
## Advanced Usage Examples
306

307
### Custom Data Formats
308

309
Override methods to work with custom data structures:
310

311
```javascript
312
// Example 1: Point data as [x, y] arrays
313
class PointRBush extends RBush {
314
  toBBox([x, y]) { 
315
    return { minX: x, minY: y, maxX: x, maxY: y }; 
316
  }
317
  compareMinX(a, b) { 
318
    return a[0] - b[0]; 
319
  }
320
  compareMinY(a, b) { 
321
    return a[1] - b[1]; 
322
  }
323
}
324

325
const pointTree = new PointRBush();
326
pointTree.load([[20, 50], [30, 60], [10, 25]]);
327
const nearbyPoints = pointTree.search({ minX: 15, minY: 45, maxX: 35, maxY: 65 });
328

329
// Example 2: Geographic coordinates with custom properties
330
class GeoRBush extends RBush {
331
  toBBox(item) {
332
    return {
333
      minX: item.lng,
334
      minY: item.lat, 
335
      maxX: item.lng,
336
      maxY: item.lat
337
    };
338
  }
339
  compareMinX(a, b) { return a.lng - b.lng; }
340
  compareMinY(a, b) { return a.lat - b.lat; }
341
}
342

343
const geoTree = new GeoRBush();
344
geoTree.insert({ lng: -122.4194, lat: 37.7749, name: 'San Francisco' });
345
```
346

347
### Custom Equality for Removal
348

349
Use custom equality function when removing items by value:
350

351
```javascript
352
// Remove item by ID instead of reference
353
const items = [
354
  { minX: 0, minY: 0, maxX: 10, maxY: 10, id: 'rect1' },
355
  { minX: 20, minY: 20, maxX: 30, maxY: 30, id: 'rect2' }
356
];
357

358
tree.load(items);
359

360
// Remove by ID even if you only have a copy of the object
361
const itemCopy = { minX: 20, minY: 20, maxX: 30, maxY: 30, id: 'rect2' };
362
tree.remove(itemCopy, (a, b) => a.id === b.id);
363

364
// Remove by custom property
365
tree.remove({ category: 'temporary' }, (a, b) => a.category === b.category);
366
```
367

368
### Client-Server Workflow
369

370
Export tree data on server and import on client:
371

372
```javascript
373
// Server side - build and export spatial index
374
import RBush from 'rbush';
375

376
const serverTree = new RBush(16); // Use same maxEntries on both sides
377
serverTree.load(largeDataset);
378
const treeData = serverTree.toJSON();
379

380
// Send treeData to client (via API, WebSocket, etc.)
381
response.json({ spatialIndex: treeData });
382

383
// Client side - import and use pre-built index
384
const clientTree = new RBush(16).fromJSON(treeData);
385
const results = clientTree.search(userQueryBounds);
386

387
// Client can still add local data
388
clientTree.insert(userAddedItem);
389
```
390

391
### Performance Optimization Examples
392

393
```javascript
394
// Scenario 1: Initial data loading - use bulk load
395
const tree = new RBush();
396
tree.load(initialDataset); // 2-3x faster than individual inserts
397

398
// Scenario 2: Mixed operations - separate bulk and individual operations  
399
const updates = [...]; // New items to add
400
if (updates.length > 10) {
401
  // Bulk load for large batches
402
  tree.load(updates);
403
} else {
404
  // Individual inserts for small batches
405
  updates.forEach(item => tree.insert(item));
406
}
407

408
// Scenario 3: Collision detection vs. full search
409
const queryBounds = { minX: 100, minY: 100, maxX: 200, maxY: 200 };
410

411
// Fast - only need to know if anything intersects
412
if (tree.collides(queryBounds)) {
413
  handleCollision();
414
}
415

416
// Slower - need actual intersecting items
417
const intersecting = tree.search(queryBounds);
418
processIntersectingItems(intersecting);
419
```
420

421
## Performance Characteristics
422

423
- **Insertion**: Single items use non-recursive R-tree insertion with R*-tree split routine
424
- **Bulk Loading**: OMT algorithm combined with Floyd-Rivest selection (2-3x faster than individual inserts)
425
- **Bulk Insertion**: STLT algorithm for inserting into existing trees
426
- **Search**: Standard non-recursive R-tree search
427
- **Deletion**: Non-recursive depth-first traversal with free-at-empty strategy
428

429
Optimal `maxEntries` value is typically 9 (default) for most applications. Higher values mean faster insertion but slower search, and vice versa.
430

431
## Error Handling
432

433
RBush is designed to be robust and handle edge cases gracefully:
434

435
**Method Return Patterns:**
436
- Modification methods return `this` for chaining: `insert`, `load`, `remove`, `clear`, `fromJSON`
437
- Query methods return data: `search` (array), `all` (array), `collides` (boolean), `toJSON` (object)
438

439
**Graceful Error Handling:**
440
- `insert(undefined)` or `insert(null)` - silently ignored, no error thrown
441
- `load([])` - empty arrays handled as no-op
442
- `remove(nonExistentItem)` - silently ignored if item not found
443
- `search(invalidBBox)` - returns empty array for malformed bounding boxes
444
- `collides(invalidBBox)` - returns false for malformed bounding boxes
445

446
**Data Validation:**
447
- Items must have valid numeric `minX`, `minY`, `maxX`, `maxY` properties for correct operation
448
- Bounding boxes should satisfy: `minX <= maxX` and `minY <= maxY`
449
- Invalid spatial data may cause unexpected results but won't crash the library
450

451
**Memory Considerations:**
452
- Large datasets benefit from bulk loading with `load()` rather than individual `insert()` calls
453
- Tree height grows logarithmically - extremely large datasets remain performant