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
