RBush

import RBush from 'rbush';

const RBush = require('rbush');

<script type="module">
    import RBush from 'https://cdn.jsdelivr.net/npm/rbush/+esm';
</script>

<script src="https://cdn.jsdelivr.net/npm/rbush"></script>
<!-- RBush is available as global variable -->

import RBush from 'rbush';

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

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

const rect2 = {
  minX: 0, minY: 0, maxX: 10, maxY: 10,
  id: 'rectangle-2'
};

// Insert single items
tree.insert(rect1);

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

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

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

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

import RBush from 'rbush';

/**
 * Creates a new RBush spatial index
 * @param maxEntries - Maximum entries in a tree node (default: 9, range: 4-∞)
 * Higher values mean faster insertion but slower search, and vice versa
 */
constructor(maxEntries?: number): RBush;

import RBush from 'rbush';
const tree = new RBush();

/**
 * Search for all items intersecting the given bounding box
 * @param bbox - Bounding box with minX, minY, maxX, maxY properties (required)
 * @returns Array of data items that intersect the bounding box (empty array if none found)
 * @throws No exceptions - returns empty array for invalid bounding boxes
 */
search(bbox: BoundingBox): any[];

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

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

import RBush from 'rbush';
const tree = new RBush();

/**
 * Insert a single item into the spatial index
 * @param item - Data item with spatial bounds (minX, minY, maxX, maxY properties)
 *               Additional properties are preserved. Pass undefined/null to do nothing.
 * @returns this (for method chaining)
 * @throws No exceptions - silently ignores undefined/null items
 */
insert(item: any): RBush;

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

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

/**
 * Remove all items from the spatial index, resetting to empty state
 * @returns this (for method chaining)
 */
clear(): RBush;

import RBush from 'rbush';
const tree = new RBush();

/**
 * Export tree data as JSON object for serialization
 * Preserves complete tree structure including spatial bounds and user data
 * @returns Object representing the internal tree structure (can be stringified)
 */
toJSON(): object;

/**
 * Import previously exported tree data
 * Note: maxEntries parameter must match between export and import trees
 * @param data - Previously exported tree data from toJSON()
 * @returns this (for method chaining)
 * @throws No validation - assumes data is valid tree structure
 */
fromJSON(data: object): RBush;

import RBush from 'rbush';
// Extend RBush to customize data format
class MyRBush extends RBush {
  // Override methods as needed
}

/**
 * Convert data item to bounding box format (override for custom data structures)
 * Default implementation expects items to already have minX, minY, maxX, maxY
 * @param item - Data item in your custom format
 * @returns Bounding box with minX, minY, maxX, maxY properties (required)
 * @example
 * // For point data [x, y]
 * toBBox([x, y]) { return {minX: x, minY: y, maxX: x, maxY: y}; }
 */
toBBox(item: any): BoundingBox;

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

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

/**
 * Bounding box interface for spatial queries
 */
interface BoundingBox {
  minX: number;
  minY: number;
  maxX: number;
  maxY: number;
}

/**
 * Main RBush class for spatial indexing
 */
class RBush {
  constructor(maxEntries?: number);
  
  // Search methods
  search(bbox: BoundingBox): any[];
  all(): any[];
  collides(bbox: BoundingBox): boolean;
  
  // Modification methods
  insert(item: any): RBush;
  load(data: any[]): RBush;
  remove(item: any, equalsFn?: (a: any, b: any) => boolean): RBush;
  clear(): RBush;
  
  // Serialization methods
  toJSON(): object;
  fromJSON(data: object): RBush;
  
  // Customization methods (overrideable)
  toBBox(item: any): BoundingBox;
  compareMinX(a: any, b: any): number;
  compareMinY(a: any, b: any): number;
}

// Example 1: Point data as [x, y] arrays
class PointRBush extends RBush {
  toBBox([x, y]) { 
    return { minX: x, minY: y, maxX: x, maxY: y }; 
  }
  compareMinX(a, b) { 
    return a[0] - b[0]; 
  }
  compareMinY(a, b) { 
    return a[1] - b[1]; 
  }
}

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

// Example 2: Geographic coordinates with custom properties
class GeoRBush extends RBush {
  toBBox(item) {
    return {
      minX: item.lng,
      minY: item.lat, 
      maxX: item.lng,
      maxY: item.lat
    };
  }
  compareMinX(a, b) { return a.lng - b.lng; }
  compareMinY(a, b) { return a.lat - b.lat; }
}

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

// Remove item by ID instead of reference
const items = [
  { minX: 0, minY: 0, maxX: 10, maxY: 10, id: 'rect1' },
  { minX: 20, minY: 20, maxX: 30, maxY: 30, id: 'rect2' }
];

tree.load(items);

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

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

// Server side - build and export spatial index
import RBush from 'rbush';

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

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

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

// Client can still add local data
clientTree.insert(userAddedItem);

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

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

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

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

// Slower - need actual intersecting items
const intersecting = tree.search(queryBounds);
processIntersectingItems(intersecting);