[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Pure lua kd-tree
- From: Geoff Leyland <geoff_leyland@...>
- Date: Fri, 18 Sep 2009 08:59:31 +1200
I've been working on a project that involves displaying and querying
road maps, and needed to be able to work out quickly what to draw and
what the mouse was over. I didn't find much that helped by googling
"lua rtree", so I ended up writing something that turned out to be
fairly primitive a kd-tree. I still haven't found much googling "lua
kdtree", so I've stuck it where you can find it.
It's read-only - you tell it the bounding boxes of all your objects
once and it chugs a while building the tree, and then you can ask it
which objects lie in a box. I'm sure it could be improved both in
code and the algorithm it uses. (for example the query returns a
coroutine iterator, which uses about 4k for every query. Perhaps a
callback interface would be better?)
If anyone's interested it's at http://www.incremental.co.nz/download/kdtree.lua.gz
By the way is there a good place to put snippets of code like this?
It seems a little insignificant for Luaforge or the like. Paste it
into the wiki?