erlquad - quadtrees for the BEAM

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.

Links