[Scipy-tickets] [SciPy] #1178: ckdtree, bug in nearest neighbor search

SciPy Trac scipy-tickets@scipy....
Tue May 25 13:56:02 CDT 2010


#1178: ckdtree, bug in nearest neighbor search
-----------------------------------------------+----------------------------
 Reporter:  sega_sai                           |       Owner:  peridot    
     Type:  defect                             |      Status:  new        
 Priority:  high                               |   Milestone:  Unscheduled
Component:  scipy.spatial                      |     Version:  0.7.0      
 Keywords:  kdtree, nearest neighbor, ckdtree  |  
-----------------------------------------------+----------------------------
 The cKDTree code seems to have a bug in the nearest neigbor search code.
 Which leads to the output of completely wrong neighbors.
 The Python KDTree does not seem to have that problem, it provides correct
 results.


 I attach the program which demonstrates the problem. I will probably try
 to make a shorter version of the test case later...

 import numpy,scipy,numpy.random, scipy.spatial

 nel=1000

 #the input dataset is  uniformly distributed in 2D

 xs=numpy.random.uniform(-1,1,size=nel)

 ys=numpy.random.uniform(-1,1,size=nel)

 dat0= numpy.array([xs,ys]).transpose()

 #one tree is constructed using ckdtree the other using Python kdtree

 tree1=scipy.spatial.cKDTree(dat0)

 tree2=scipy.spatial.KDTree(dat0)


 # the dataset to which we want to find nearest neigbors.

 # It is the grid from -1 to 1 in x and y

 xgrid=numpy.linspace(-1,1,100)

 ygrid=numpy.linspace(-1,1,100)

 xgrid2d,ygrid2d=numpy.meshgrid(xgrid,ygrid)

 xgrid2d,ygrid2d=xgrid2d.flatten(),ygrid2d.flatten()

 dat_search=numpy.array([xgrid2d,ygrid2d]).transpose()

 # we look for 10 nearest neighbors

 neib=10

 distances1,inds1=tree1.query(dat_search,neib)

 distances2,inds2=tree2.query(dat_search,neib)

 print distances1-distances2

 # first the distances from ckdtree and kdtree are not equal which is a
 first sign of a bug

 # second the nearest neighbor for ckdtree is sometimes too far away

 print "cKDtree max(delta_x):", numpy.max(xgrid2d-xs[inds1[:,0]])

 print "KDtree max(delta_x):",  numpy.max(xgrid2d-xs[inds2[:,0]])

 #######

 scipy.version =0.7.2

 numpy.version =1.4.2

 python.version=2.6.5

 numpy.test() and scipy.test() work fine

 ARCH=x86_64

-- 
Ticket URL: <http://projects.scipy.org/scipy/ticket/1178>
SciPy <http://www.scipy.org>
SciPy is open-source software for mathematics, science, and engineering.


More information about the Scipy-tickets mailing list