erlquad provides Erlang quadtrees, a 2D spatial index that recursively subdivides a rectangular region into four quadrants, so that objects can be looked up by location without scanning them all.
This library was archived in 2019; I revived it today. Since I had never announced it in this forum, this is my first post about it.
Use cases
Good for many things in 2D.
- Collision detection: find nearby candidates instead of every pair
- Viewport culling: grab only what’s on screen
- Maps: pins within the current bounds
- Proximity: who/what’s near a point
- Hit-testing: what’s under the click
- Partitioning many actors: bucket lots of entities by region
Example
A 100x100 world, 4 levels deep, holding a few points.
Each object == its coordinate, so the outline function returns the object itself.
Points = [{10, 10}, {90, 90}, {12, 15}],
OutlineFun = fun (P) -> P end,
Q = erlquad:objects_add(Points, OutlineFun, erlquad:new(0, 0, 100, 100, 4)).
“What’s in the bottom-left corner?”
erlquad:area_query(0, 0, 20, 20, Q).
% [{10,10},{12,15}]
^ The far-off {90,90} isn’t looked at