[ANN] lua-kdtree
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: [ANN] lua-kdtree
- From: Geoff Leyland <geoff_leyland@...>
- Date: 2014年1月24日 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