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.
Today I revived this library, after I had archived it in 2019. 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}]
outline_fun = fn p -> p end
q = :erlquad.objects_add(points, outline_fun, :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.
