Quadtree

Module defined in lua/common/quadtree.lua. Quadtree spatial data structure for 2D bounding boxes with insert, remove, query, and compression. Query is remove-safe (removing items during iteration doesn't break traversal).

---

Exports

Functions

M.newQuadtree()

Creates a new empty quadtree.

• Returns: quadTree - Quadtree object

M.pointBBox(x, y, radius)

Utility: creates a 2D bounding box from a point and radius.

• Parameters:
  • x, y - number - Point center
  • radius - number - Expansion radius
• Returns: number, number, number, number - xmin, ymin, xmax, ymax

M.lineBBox(x1, y1, x2, y2, radius)

Utility: creates a 2D bounding box from a line segment with radius expansion.

• Returns: number, number, number, number - xmin, ymin, xmax, ymax

Instance Methods

tree:preLoad(itm_id, itm_xmin, itm_ymin, itm_xmax, itm_ymax)

Pre-loads items before building. Used to determine tree canvas bounds.

tree:build(maxDepth)

Builds the quadtree from pre-loaded items.

• Parameters:
  • maxDepth - number|nil - Maximum tree depth (default: 10, root = depth 1)

tree:insert(itm_id, itm_xmin, itm_ymin, itm_xmax, itm_ymax)

Inserts an item after the tree is built. Items outside canvas bounds are still handled.

tree:remove(itm_id, itm_x, itm_y)

Removes an item by ID and approximate center position.

• Parameters:
  • itm_id - any - Item identifier
  • itm_x, itm_y - number - Item center coordinates

tree:query(query_xmin, query_ymin, query_xmax, query_ymax)

Returns an iterator over items intersecting the query box. Safe for nested queries.

• Returns: function, table - Iterator yielding item IDs

tree:queryNotNested(query_xmin, query_ymin, query_xmax, query_ymax)

Faster query reusing internal state; not safe for nesting.

• Returns: function, table - Iterator

tree:compress()

Optimizes memory by trimming pre-allocated but unused node capacity. May slow subsequent inserts.

tree:export() / tree:import(quadTreeData)

Serialization/deserialization.

tree:analytics()

Prints tree statistics.

Internal Notes

• Items stored as 5 consecutive values per item in node tables: itm_id, xmin, xmax, ymin, ymax
• Node table key itemCount tracks the number of value entries (divide by 5 for item count)
• self.children[node_i] gives the tree index of node_i's first child (children are at +0, +1, +2, +3)
• Query traversal uses an explicit stack for remove-safety
• Canvas bounds are fixed after build() - items outside bounds can still be inserted

---

See Also

• cdefDebugDraw Reference - Related reference
• cdefGpuMesh Reference - Related reference
• cdefImgui Reference - Related reference
• Common Libraries Overview - Guide