[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: [pygame] Fast kd-tree implementation




On May 10, 2007, at 6:55, John Eikenberry wrote:

Malcolm Ryan wrote:

This documentation is a little sparse. Could you possibly provide a
snippet of example code?

Wikipedia has a decent article on kd-trees. It even has a simple python
implementation and basic example usage.


http://en.wikipedia.org/wiki/Kd-tree

Just a guess: Might there not be quite an overhead in using a tree structure such as this for a relatively simple problem such as range search in 2D? (And for higher dimensionalities there are certainly better structures than the Kd-tree available -- but that's a digression, I guess ;-).


I don't know wha the relative performances might be, but an alternative might be to keep the points in two lists, sorted by x and y coordinate, respectively. When searching use bisection on each and merge the result (using as many built-in Python operations as you can). This approach is not very good for high dimensionalities, but for 2D it might work rather well, and it has verly low overhead in terms of objects created etc. (Easier to implement, as well, if you're going that route.)

Just a thought. (Like Ken Thompson said -- "when in doubt, use brute force" ;-)

--
Magnus Lie Hetland
http://hetland.org