[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: [pygame] Fast kd-tree implementation
On May 10, 2007, at 9:13, Magnus Lie Hetland wrote:
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).
Another of these "dirt simple" options, if you know roughly the size
of your search radius (ballpark figure) you could impose a grid of
about the same order of magnitude on the plane, and directly hash (by
coordinate rounding) the points to their respective grid cell
buckets. When searching you can then calculate which cells are
intersected and ignore all the others. Easy to implement, and under
the right circumstances, highly efficient (you only need to examine a
few, possibly a constant number, of cells; a Kd tree requires O(sqrt
(n)) nodes to be visited under reasonable assumptions, I believe).
--
Magnus Lie Hetland
http://hetland.org