Add SpatialIndexManager for R-tree spatial indexing by MitjaBezensek · Pull Request #7676 · tldraw/tldraw

MitjaBezensek · 2026-01-12T10:35:51Z

Adds SpatialIndexManager using an R-tree (RBush) for O(log n) spatial queries instead of O(n) iteration.

pr-7676-walkthrough.mp4

Changes

SpatialIndexManager - R-tree based spatial index
- Accessible via editor.spatialIndex
- Uses RBush library for efficient spatial queries
- Incremental updates using filterHistory pattern
- Per-page index (rebuilds on page change)
- Optimized for viewport culling and selection queries
Early return optimizations for tools
- Brushing, scribble brushing, and erasing skip expensive shape iteration when spatial index returns no candidates
- Significantly improves performance when selecting/erasing in empty areas
Upgraded RBush to v4.0.1
- ESM-only build (dropped CommonJS/IE11 support)

API changes

New exports from @tldraw/editor

SpatialIndexManager (class)

New editor property

editor.spatialIndex: SpatialIndexManager

Methods:

getShapeIdsInsideBounds(bounds: Box): Set<TLShapeId> — Returns shape IDs that intersect with the given rectangular area.
getShapeIdsAtPoint(point: {x, y}, margin?: number): Set<TLShapeId> — Returns shape IDs near a point within an optional margin.
dispose(): void — Cleans up the spatial index.

Change type

improvement

Test plan

Create many shapes on the canvas
Use brush selection, scribble selection, and eraser tools
Verify selection/erasing works correctly
Performance should be noticeably better with many shapes

Release notes

Adds SpatialIndexManager for efficient spatial queries using R-tree indexing
New editor.spatialIndex API with getShapeIdsInsideBounds() and getShapeIdsAtPoint() methods
Improves performance of selection and erasing operations, especially with many shapes

Note

Adds an R-tree–backed spatial index and integrates it across core editor paths for faster queries.

New SpatialIndexManager (exported) with editor.spatialIndex providing getShapeIdsInsideBounds and getShapeIdsAtPoint
Editor integrates spatial search in getShapesAtPoint and adds getShapeIdsInsideBounds(bounds); refines getShapeAtPoint candidate filtering and increases search margin; maintains per-page index with incremental updates
Reworks notVisibleShapes to use spatial index; adds cached equality in getCulledShapes for stable Set identity; minor canvas reflow optimization via reference check
Tools (Brushing, ScribbleBrushing, Erasing) use spatial candidates and early returns to avoid full-shape iteration
Dependencies: add rbush and @types/rbush; export in src/index.ts; add comprehensive tests for visibility/culling

^{Written by Cursor Bugbot for commit 7686e2f. This will update automatically on new commits. Configure here.}

vercel · 2026-01-12T10:35:52Z

The latest updates on your projects. Learn more about Vercel for GitHub.

Project	Deployment	Review	Updated (UTC)
examples	Ready	Preview	Jan 16, 2026 0:15am

5 Skipped Deployments

Project	Deployment	Review	Updated (UTC)
analytics	Ignored	Preview	Jan 16, 2026 0:15am
chat-template	Ignored	Preview	Jan 16, 2026 0:15am
tldraw-docs	Ignored	Preview	Jan 16, 2026 0:15am
tldraw-shader	Ignored	Preview	Jan 16, 2026 0:15am
workflow-template	Ignored	Preview	Jan 16, 2026 0:15am

huppy-bot · 2026-01-12T10:35:58Z

API Changes Check Passed

Great! The PR description now includes the required "### API changes" section. This helps reviewers and SDK users understand the impact of your changes.

MitjaBezensek · 2026-01-12T11:32:51Z

Some quick performance tests using the added logging. This is while having many shapes on the page. With a small number of shapes the performance is pretty close if not slightly worse.

Erasing

📊 [Perf Summary] erasing (old)
94 operations | avg: 1.84ms | min: 0.80ms | max: 8.10ms (checked 576/576 shapes)

📊 [Perf Summary] erasing (spatial)
103 operations | avg: 0.88ms | min: 0.20ms | max: 1.30ms (checked 0/576 shapes)

Panning (tests culling)

📊 [Perf Summary] notVisibleShapes (old)
218 operations | avg: 0.78ms | min: 0.30ms | max: 15.80ms (unchanged)

📊 [Perf Summary] notVisibleShapes (spatial)
314 operations | avg: 0.37ms | min: 0.10ms | max: 5.40ms (unchanged)

Zooming

📊 [Perf Summary] notVisibleShapes (old)
29 operations | avg: 0.59ms | min: 0.40ms | max: 0.80ms (589 non-visible)

📊 [Perf Summary] notVisibleShapes (spatial)
41 operations | avg: 0.42ms | min: 0.10ms | max: 0.80ms (618 non-visible)

Switching pages (has to build the index as it is per page)

[perf] setCurrentPage (old) (total with render+paint): 755.30ms

[perf] setCurrentPage (spatial) (total with render+paint): 786.00ms

Get shape at point

📊 [Perf Summary] getShapeAtPoint (old)
112 operations | avg: 2.35ms | min: 1.40ms | max: 3.10ms (checked 624 shapes → no hit)

📊 [Perf Summary] getShapeAtPoint (spatial)
207 operations | avg: 0.90ms | min: 0.20ms | max: 2.10ms (checked 0 shapes → no hit)

…ounds first before doing an early return. Optiize early return if no shapes have changed.

…moving shapes between pages.

bhaktatejas922 · 2026-01-15T19:22:05Z

(sorry about previous comments, rouge agent)

ds300

This looks excellent! The incremental derivation seems to be updated correctly and the perf gains are fantastic. Well done mitja!

cursor

Cursor Bugbot has reviewed your changes and found 2 potential issues.

^{Bugbot Autofix is OFF. To automatically fix reported issues with Cloud Agents, enable Autofix in the Cursor dashboard.}

cursor · 2026-01-16T12:21:22Z

packages/tldraw/src/lib/tools/EraserTool/childStates/Erasing.ts

+		}
+
+		const allShapes = editor.getCurrentPageRenderingShapesSorted()
+		const currentPageShapes = allShapes.filter((shape) => candidateIds.has(shape.id))


Frames not checked when spatial index returns no candidates

Medium Severity

Frame labels are positioned above frame shapes, outside their bounds. In Editor.ts, getShapeAtPoint and getShapesAtPoint handle this by always including frames regardless of spatial index results. However, the erasing, brushing, and scribble brushing tools filter shapes using only candidateIds.has(shape.id) without the frame exception. This causes frames to be missed when only their label intersects the erase/brush area but their body bounds don't.

Additional Locations (2)

packages/tldraw/src/lib/tools/SelectTool/childStates/Brushing.ts#L161-L179

packages/tldraw/src/lib/tools/SelectTool/childStates/ScribbleBrushing.ts#L102-L117

cursor · 2026-01-16T12:21:22Z

packages/editor/src/lib/editor/managers/SpatialIndexManager/SpatialIndexManager.ts

+				processedShapeIds.add(to.id)
+
+				const wasOnPage = this.editor.getAncestorPageId(from) === this.lastPageId
+				const isOnPage = this.editor.getAncestorPageId(to) === this.lastPageId


Page change detection uses current state, not historical state

Medium Severity

The getAncestorPageId method always fetches the current shape state via this.getShape(id), ignoring the passed shape object. When checking wasOnPage using from (the old state), it actually returns the current page, not the previous page. This causes shapes moved away from the current page to remain in the spatial index incorrectly, since both wasOnPage and isOnPage will return the same value (current state), and the removal branch is never taken.

Follow-up to #7676. I've reconsidered and made the spatial index private. This PR makes the SpatialIndexManager internal to the editor rather than part of the public API. The spatial index is an implementation detail used for efficient shape queries. Changes: - Mark `SpatialIndexManager` class as `@internal` - Remove `editor.spatialIndex` public property (now `private _spatialIndex`) - Mark `editor.getShapeIdsInsideBounds()` as `@internal` The public API for shape queries remains `editor.getShapeAtPoint()` and `editor.getShapesAtPoint()`, which handle edge cases like frame labels being outside their bounds. ### Change type - [x] `api` ### API changes - Removed `editor.spatialIndex` property from public API - Changed `editor.getShapeIdsInsideBounds()` from `@public` to `@internal` - Changed `SpatialIndexManager` class from `@public` to `@internal` ### Test plan 1. Existing tests pass 2. Internal usages in brushing/erasing tools still work ### Release notes - Remove `editor.spatialIndex` from public API  --- > [!NOTE] > Makes spatial indexing an internal implementation detail and removes it from the public API. > > - Mark `SpatialIndexManager` as `@internal`; update class docs accordingly > - Remove public `editor.spatialIndex`; introduce private `editor._spatialIndex` and update usages in hit-testing and bounds queries > - Mark `editor.getShapeIdsInsideBounds()` as `@internal` and clarify its bounds-only behavior > - Public querying remains via `editor.getShapeAtPoint()` / `editor.getShapesAtPoint()` > > <sup>Written by [Cursor Bugbot](https://cursor.com/dashboard?tab=bugbot) for commit f366bfb. This will update automatically on new commits. Configure [here](https://cursor.com/dashboard?tab=bugbot).</sup>

Spatial index again.

e0ac451

MitjaBezensek added 2 commits January 12, 2026 11:43

Remove tests, fix lint.

e23f22c

Consolidate flags.

3de0ed8

MitjaBezensek changed the title ~~Spatial index again.~~ Add granular perf logging for spatial index and refactor to manager pattern Jan 12, 2026

MitjaBezensek changed the title ~~Add granular perf logging for spatial index and refactor to manager pattern~~ Add SpatialIndexManager with granular perf logging Jan 12, 2026

MitjaBezensek temporarily deployed to e2e-dotcom January 12, 2026 11:12 — with GitHub Actions Inactive

MitjaBezensek temporarily deployed to bemo-canary January 12, 2026 11:12 — with GitHub Actions Inactive

github-actions bot deployed to bemo-preview January 12, 2026 11:14 View deployment

vercel bot deployed to Preview – examples January 12, 2026 11:14 View deployment

Log again.

10276a3

MitjaBezensek force-pushed the mitja/indexing-again branch from 092d552 to 10276a3 Compare January 12, 2026 11:21

MitjaBezensek added 2 commits January 12, 2026 13:10

Cache it?

11502d2

Add debug panel.

6f869a3

MitjaBezensek temporarily deployed to bemo-canary January 12, 2026 12:37 — with GitHub Actions Inactive

MitjaBezensek temporarily deployed to e2e-dotcom January 12, 2026 12:37 — with GitHub Actions Inactive

Improve.

00fd34d

MitjaBezensek force-pushed the mitja/indexing-again branch from 9bf9222 to 00fd34d Compare January 12, 2026 12:37

MitjaBezensek added 6 commits January 12, 2026 14:02

Split the implementations. for testing.

8b54ad5

Simplify log.

9e917e3

Add shape creation.

d50d642

Add tests.

6cac766

Dispose.

86510fc

Additional tests.

699ba09

MitjaBezensek requested a review from ds300 January 13, 2026 10:33

MitjaBezensek added 3 commits January 13, 2026 12:30

Improve the tool.

4dcd8ba

Improve.

a83c148

Early return if we are out of bounds.

37ecda8

MitjaBezensek force-pushed the mitja/indexing-again branch from 0a7e4c0 to 418e9e5 Compare January 13, 2026 12:25

MitjaBezensek added 6 commits January 13, 2026 13:50

Eaerly returns for other options as well.

8474989

Only calculate change for the current page. Make sure we update the b…

0724fe8

…ounds first before doing an early return. Optiize early return if no shapes have changed.

Return sets. Use the unordered variant for generating the index. Fix …

9be209b

…moving shapes between pages.

Avoid duplicates.

b9df492

Upsert.

a80ba05

Improve.

81a07e7

tldraw deleted a comment from bhaktatejas922 Jan 15, 2026

ds300 approved these changes Jan 16, 2026

View reviewed changes

MitjaBezensek added 3 commits January 16, 2026 12:15

Remove logs.

7610322

Simplify.

600e523

Rbush already handles this.

c7daa84

MitjaBezensek force-pushed the mitja/indexing-again branch from 2b977ea to c7daa84 Compare January 16, 2026 11:34

Use version 4.

e6afdac

MitjaBezensek changed the title ~~Add SpatialIndexManager with granular perf logging~~ Add SpatialIndexManager for R-tree spatial indexing Jan 16, 2026

MitjaBezensek added 2 commits January 16, 2026 13:06

Fix frame hit testing.

4cf012d

Already a set.

5edddee

MitjaBezensek marked this pull request as ready for review January 16, 2026 12:09

huppy-bot bot added the improvement Product improvement label Jan 16, 2026

Fix.

7686e2f

MitjaBezensek enabled auto-merge January 16, 2026 12:12

MitjaBezensek added this pull request to the merge queue Jan 16, 2026

cursor bot reviewed Jan 16, 2026

View reviewed changes

Merged via the queue into main with commit 2643056 Jan 16, 2026
19 checks passed

MitjaBezensek deleted the mitja/indexing-again branch January 16, 2026 12:27

MitjaBezensek mentioned this pull request Jan 16, 2026

refactor(editor): make SpatialIndexManager internal #7699

Merged

1 task

mimecuvalo mentioned this pull request Jan 29, 2026

Explore spatial index-based culling strategy #7435

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add SpatialIndexManager for R-tree spatial indexing#7676

Add SpatialIndexManager for R-tree spatial indexing#7676
MitjaBezensek merged 31 commits intomainfrom
mitja/indexing-again

MitjaBezensek commented Jan 12, 2026 •

edited by steveruizok

Loading

Uh oh!

vercel bot commented Jan 12, 2026 •

edited

Loading

Uh oh!

huppy-bot bot commented Jan 12, 2026 •

edited

Loading

Uh oh!

MitjaBezensek commented Jan 12, 2026 •

edited

Loading

Uh oh!

bhaktatejas922 commented Jan 15, 2026

Uh oh!

ds300 left a comment

Uh oh!

cursor bot left a comment

Uh oh!

cursor bot Jan 16, 2026

Uh oh!

cursor bot Jan 16, 2026

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Conversation

MitjaBezensek commented Jan 12, 2026 • edited by steveruizok Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Changes

API changes

New exports from @tldraw/editor

New editor property

Change type

Test plan

Release notes

Uh oh!

vercel bot commented Jan 12, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

huppy-bot bot commented Jan 12, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

MitjaBezensek commented Jan 12, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Erasing

Panning (tests culling)

Zooming

Switching pages (has to build the index as it is per page)

Get shape at point

Uh oh!

bhaktatejas922 commented Jan 15, 2026

Uh oh!

ds300 left a comment

Choose a reason for hiding this comment

Uh oh!

cursor bot left a comment

Choose a reason for hiding this comment

Uh oh!

cursor bot Jan 16, 2026

Choose a reason for hiding this comment

Frames not checked when spatial index returns no candidates

Uh oh!

cursor bot Jan 16, 2026

Choose a reason for hiding this comment

Page change detection uses current state, not historical state

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

MitjaBezensek commented Jan 12, 2026 •

edited by steveruizok

Loading

vercel bot commented Jan 12, 2026 •

edited

Loading

huppy-bot bot commented Jan 12, 2026 •

edited

Loading

MitjaBezensek commented Jan 12, 2026 •

edited

Loading