K-D Tree (2D Boxes)

Module defined in lua/common/kdtreebox2d.lua. K-d tree implementation for 2D axis-aligned bounding boxes (4 dimensions: xmin, ymin, xmax, ymax). Supports efficient spatial range queries with both nested and non-nested iteration.

---

Exports

Functions

kdtreebox2d.new(itemCount)

Creates a new empty 2D box k-d tree.

• Parameters:
  • itemCount - number|nil - Expected item count for pre-allocation
• Returns: kdTree - Tree object

Instance Methods

tree:preLoad(id, xmin, ymin, xmax, ymax)

Adds an item to the pre-load buffer before building the tree.

• Parameters:
  • id - any - Item identifier (returned during queries)
  • xmin, ymin, xmax, ymax - number - Bounding box coordinates

tree:build()

Constructs the k-d tree from all pre-loaded items. Must be called after all preLoad calls.

tree:clear()

Clears all data from the tree, resetting it for reuse.

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

Returns an iterator over all items whose bounding boxes intersect the query area. Safe for nested queries (allocates new state).

• Parameters:
  • query_xmin, query_ymin, query_xmax, query_ymax - number - Query bounding box
• Returns: function, table - Iterator function and state (use in for id in tree:query(...) do)

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

Like query but reuses internal state - faster but cannot be nested.

• Returns: function, table - Iterator

tree:export()

Exports the tree data for serialization.

• Returns: table - {tree, nonLeafLimIdx, items, itemCount}

tree:import(kdTreeData)

Imports previously exported tree data.

• Parameters:
  • kdTreeData - table - Data from export()

tree:analytics()

Prints tree statistics (depth, node count, items per leaf).

Internal Notes

• Items stored as flat array: 5 values per item (xmin, ymin, xmax, ymax, id)
• Uses a custom linear-time median selection algorithm (LEF Select) for balanced tree construction
• Tree nodes stored in a flat array with 4 values each (lmin, lmax, rmin, rmax)
• Leaf nodes store item index ranges instead of splitting further
• Query uses an explicit stack for iterative traversal (no recursion)

Additional Exports

---

See Also

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