get_n_nearest_neighbors() returns less nodes than n for query close to root

[tenomoto]

In the extreme case of query being the root vantage point, furthest_d becomes zero and no further nodes are searched because d is less than node.left_min. The left subtree should be searched if d < middle where middle = (self.left_max + self.right_min).

References:

• Algorithm 3 of Yianlilos 1993
• Fig. 6 of Fu et al. 2000.

[bruggsy]

Hi, I'm still seeing this issue when trying to use this library. I'm on version 1.1.1, is this the version that has these fixes or am I mistaken? Including some test code below.

Thanks! Happy holidays.

import numpy as np
import vptree

def euclidean(p1, p2):
  return np.sqrt(np.sum(np.power(p2 - p1, 2)))

foo = np.array([[2.5,3.3,2.1],[1.0,1.0,1.0],[4.2,4.0,5.0]])

tree = vptree.VPTree(foo,euclidean)

tree.get_n_nearest_neighbors(foo[1],3)

# [(0.0, array([ 1.,  1.,  1.])), (2.9580398915498081, array([ 2.5,  3.3,  2.1]))]