K-D Tree (3D)

Module defined in lua/common/kdtreepoint3d.lua. K-d tree implementation for 3D points with range queries AND nearest-neighbor (closest point) queries.

---

Exports

Functions

kdtreepoint3d.new(itemCount)

Creates a new empty 3D point k-d tree.

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

Instance Methods

tree:preLoad(id, x, y, z)

Adds a point to the pre-load buffer.

• Parameters:
  • id - any - Item identifier
  • x, y, z - number - Point coordinates

tree:build()

Constructs the k-d tree from pre-loaded points.

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

Range query - returns iterator over all points within the query box. Safe for nested queries.

• Returns: function, table - Iterator yielding item IDs

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

Faster range query reusing internal state; not safe for nesting.

• Returns: function, table - Iterator

tree:findNearest(x, y, z)

Finds the closest point to the query position.

• Parameters:
  • x, y, z - number - Query point coordinates
• Returns: any, number - ID of nearest item and Euclidean distance to it

tree:export() / tree:import(kdTreeData)

Serialization/deserialization.

tree:analytics()

Prints tree statistics.

Internal Notes

• Items stored as flat array: 4 values per item (x, y, z, id)
• findNearest uses branch-and-bound with the median point as initial best-distance estimate
• Same LEF Select and flat-array structure as the box variants
• Nearest-neighbor search prunes branches when the squared distance to the split plane exceeds best distance

Additional Exports

---

See Also

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