[SciPy-Dev] Another Bug in KDTree

[Charles R. Schmidt]

There appears to be a bug in KDTree.query_ball_point, when using
integer points neighbor points that lie on the radius are not always
returned.

Eg, with a 4x4 grid
>>> import scipy.spatial
>>> points = [(0, 0), (0, 1), (0, 2), (0, 3), \
...              (1, 0), (1, 1), (1, 2), (1, 3), \
...              (2, 0), (2, 1), (2, 2), (2, 3), \
...              (3, 0), (3, 1), (3, 2), (3, 3)]
>>> kd=scipy.spatial.KDTree(points)
>>> kd.query_ball_point((2,0),1)
[8, 9, 12]


>>> points = [(0.0, 0.0), (0.0, 1.0), (0.0, 2.0), (0.0, 3.0), \
...              (1.0, 0.0), (1.0, 1.0), (1.0, 2.0), (1.0, 3.0), \
...              (2.0, 0.0), (2.0, 1.0), (2.0, 2.0), (2.0, 3.0), \
...              (3.0, 0.0), (3.0, 1.0), (3.0, 2.0), (3.0, 3.0)]

>>> kd=scipy.spatial.KDTree(points)
>>> kd.query_ball_point((2,0),1)
[4, 8, 9, 12]