Geometry And Spatial Indexing For Canvas Objects

What's being tested

This topic tests whether you can turn geometric queries over millions of canvas objects into predictable-latency operations using the right spatial index, bounding representation, and update strategy. You should be able to distinguish broad-phase candidate filtering from exact geometric hit testing, reason about transformed and rotated objects, and explain complexity under realistic workloads. Figma cares because selection, hover, marquee operations, viewport rendering, snapping, and interaction latency all depend on finding the relevant objects without scanning the entire document.

Core knowledge

• Axis-aligned bounding boxes (AABBs) represent an object as $(x_{\min}, y_{\min}, x_{\max}, y_{\max})$. Intersection requires $a_{\min} \le b_{\max}$ on both axes; they are cheap but over-approximate rotated or irregular geometry.

• A two-phase query first performs broad-phase filtering against bounding boxes, then narrow-phase testing against the actual shape, path, stroke, or transformed geometry. This avoids expensive polygon or curve calculations for obviously irrelevant objects.

• An R-tree indexes rectangles hierarchically, typically providing expected $O(\log N + K)$ query behavior for $N$ objects and $K$ candidates. It handles nonuniform object distributions better than a fixed grid, but overlapping nodes can degrade selectivity.

• A quadtree recursively partitions 2D space into four regions. It works well for relatively uniform point or object distributions, but large objects crossing many cells, highly skewed layouts, and frequent movement can cause duplication or expensive reinsertion.

• A uniform spatial hash/grid maps an AABB to every overlapped cell, producing near-constant-time lookup when object density and cell size are reasonable. Choose cell size near the common interaction or viewport scale; too small causes duplication, too large returns excessive candidates.

• BVH (bounding-volume hierarchy) structures objects in a tree of enclosing bounds and is often effective for static or mostly-static scene geometry. Rebuilding or refitting the hierarchy is a tradeoff: refitting is cheaper after movement, while rebuilding restores query quality.

• For a transformed object, transform its local-space corners by the full world transform and compute the enclosing world-space AABB. Testing only the untransformed local rectangle creates false negatives; testing only a center point misses large or rotated objects.

• Coordinate-space discipline matters: convert pointer or viewport rectangles into document coordinates before querying. With zoom $z$ and viewport origin $(o_x,o_y)$, a screen point $(s_x,s_y)$ commonly maps to $((s_x-o_x)/z,(s_y-o_y)/z)$.

• For marquee selection, query the selection rectangle against object bounds, then apply the declared semantic: “touching” uses AABB intersection, while “fully contained” requires $x_{\min}^{obj}\ge x_{\min}^{sel}$ and analogous inequalities on all sides.

• Dynamic canvases need an update protocol: remove or mark stale entries, mutate the object, recompute bounds, and reinsert or update the index. Version numbers or generation IDs prevent a delayed query from returning geometry from an older object state.

• Rendering and hit testing usually need z-order resolution after spatial filtering. The index should return candidates, not decide visual precedence; sort candidates by stacking context or traverse the scene graph in reverse paint order.

• Measure more than average latency: track p50, p95, and p99 query time, candidate counts, index update cost, memory overhead, and false-positive rate. A design that is $O(\log N)$ but returns 100,000 candidates is not interactive.

Worked example

No concrete interview title was supplied, so use this representative prompt: “Design hit testing for objects on an infinite canvas.” In the first 30 seconds, clarify whether objects can rotate, whether strokes and transparent regions count as hits, the expected object count, mutation rate, and latency target for pointer movement. State the assumptions that the canvas may contain millions of objects, queries arrive at interactive frequency, and exact geometry checks are more expensive than bounding-box checks. Organize the answer around coordinate conversion, a broad-phase spatial index, narrow-phase geometry testing, and z-order resolution. Explain that each object maintains a world-space AABB, while the index stores an object ID plus a version or reference to detect stale bounds. A pointer query converts screen coordinates into document coordinates, retrieves nearby candidates, performs exact local-space hit testing, and chooses the topmost visible match. Explicitly flag the tradeoff between an R-tree, which handles uneven layouts well, and a grid, which can provide simpler and faster updates under stable density. Close by saying that with more time you would benchmark adversarial layouts, add caching for repeated pointer queries, and test behavior during concurrent document updates.

A second angle

The same design applies to a marquee-selection query, but the result is a set rather than one topmost object. The key semantic choice is whether an object counts when its AABB touches the rectangle or only when its actual geometry is fully contained. Large rotated objects make AABB-only containment overly permissive, so broad-phase candidates should be followed by exact polygon, path, or transformed-boundary checks. You would also consider returning results incrementally so a large selection does not block the interaction thread.

Common pitfalls

Pitfall: Treating an AABB hit as an exact hit. This produces surprising selections around rotated rectangles, transparent interiors, and thin paths; present AABBs as a broad-phase approximation and define the narrow-phase test.

Pitfall: Saying “use a quadtree” without discussing workload shape. A strong answer compares R-trees, grids, and BVHs using object distribution, movement frequency, candidate counts, memory, and rebuild/update cost.

Pitfall: Ignoring coordinate spaces and ordering. Explicitly state how screen coordinates become document coordinates, how transforms are applied, and how candidates are resolved by visibility, clipping, and z-order.

Connections

An interviewer may pivot to scene-graph traversal, affine transforms and matrix composition, retained-mode rendering, or concurrency and immutable document snapshots. They may also ask how to virtualize rendering by querying only objects intersecting the current viewport, or how to make index updates undo/redo-safe.