[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: [ANN] lua-kdtree
- From: Geoff Leyland <geoff_leyland@...>
- Date: Fri, 24 Jan 2014 14:06:12 +1300
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