DrBwts DrBwts - 2 months ago 12
Python Question

KD Tree gives different results to brute force method

I have an array of 1000 random 3D points & I am interested in the closest 10 points to any given point. In essence the same as this post.

I checked the 2 solutions offered by J.F. Sebastian, namely a brute force approach & a KD Tree approach.

Although both give me the same indices for the closest points, they give different results for the distances

import numpy as np
from scipy.spatial import KDTree

a = 100 * np.random.rand(1000,3)
point = a[np.random.randint(0, 1001)] # point chosen at random

# KD Tree
tree = KDTree(a, leafsize=a.shape[0]+1)
dist_kd, ndx_kd = tree.query([point], k=10)

# Brute force
distances = ((a-point)**2).sum(axis=1) # compute distances
ndx = distances.argsort() # indirect sort
ndx_brt = ndx[:10]
dist_brt = distances[ndx[:10]]

# Output
print 'KD Tree:'
print ndx_kd
print dist_kd
print
print 'Brute force:'
print ndx_brt
print dist_brt


My output,


KD Tree:
[[838 860 595 684 554 396 793 197 652 330]]
[[ 0. 3.00931208 8.30596471 9.47709122 10.98784209
11.39555636 11.89088764 12.01566931 12.551557 12.77700426]]

Brute force:
[838 860 595 684 554 396 793 197 652 330]

[ 0. 9.05595922 68.9890498 89.81525793 120.73267386
129.8587047 141.3932089 144.37630888 157.54158301 163.25183793]


So what is the issue here? Am I calculating the distance wrong?

Answer

KDTree algorithm is computing the nearest points based on the square-root of the same distance used by Brute-force algorithm.

Basically KDtree uses: sqrt(x^2+y^2+z^2) and Brute-force algorithm uses: x^2+y^2+z^2

Comments