Web Collision Detection Optimization | Dataford Interview Questions

How would you optimize a collision detection system for hundreds of architectural objects in a web browser?

Implement the collision query for axis-aligned rectangular objects using a uniform spatial hash. Return every pair whose interiors overlap, excluding objects that only touch at an edge or corner.

Input and Output

detect_collisions(objects, cell_size) receives a list of dictionaries with integer id, x, y, width, and height fields. Return sorted [id1, id2] pairs, with each pair ordered by ID.

Constraints

1 <= len(objects) <= 5000
1 <= cell_size <= 10^6
Each object has a unique integer id
0 <= width and height are positive integers
-10^9 <= x, y <= 10^9
Object rectangles are axis-aligned
Return every overlapping pair exactly once

Function Signature

def detect_collisions(objects, cell_size):

Your question is Web Collision Detection Optimization. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem