Re: [pygame] Fast kd-tree implementation

[Magnus Lie Hetland <magnus@xxxxxxxxxxx>]

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