lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


Hi,

kdtree [1] is an implementation of a kdtree spatial index [2].  A kdtree is a data structure that allows you to quickly find which objects intersect with a given query box.  I use them to quickly query geospatial data, but I believe they’re also used in 3D scene drawing.

Particular features of this implementation are that:
 - it has a nice, efficient iterator interface
 - it’s n-dimensional (not just 2 dimensional)
 - objects contained in the tree can be boxes, not just points (I don’t know why, but I’ve seen quite a few implementations that only contain points)
 - it’s read-only (that’s not necessarily a good feature)
 - it can read and write the tree to a text file
 - if you use LuaJIT, it uses C structures and malloced memory to allow you to construct larger trees without running into memory space constraints
 - if you use LuaJIT and have ljsyscall and lua-mmapfile, it can read and write the tree to binary files for very rapid tree loading.

Cheers,
Geoff


[1] https://github.com/geoffleyland/kdtree
[2] http://en.wikipedia.org/wiki/K-d_tree
[3] https://github.com/justincormack/ljsyscall
[4] https://github.com/geoffleyland/lua-mmapfile