Pure lua kd-tree

[Geoff Leyland <geoff_leyland@...>]

Hi,

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?

Cheers,
Geoff