quadtree KNearest search is fickle #112
Description
The algorithm fails to return k distinct values, depending of the input.
the TestQuadtreeKNearest_sorted can be re-write like below and it will fail to return k distinct nodes :
func TestQuadtreeKNearest_sorted(t *testing.T) {
q := quadtree.New(orb.Bound{Max: orb.Point{8, 8}})
q.Add(orb.Point{0, 0})
q.Add(orb.Point{1, 1})
q.Add(orb.Point{2, 2})
q.Add(orb.Point{3, 3})
q.Add(orb.Point{4, 4})
q.Add(orb.Point{5, 5})
q.Add(orb.Point{6, 6})
q.Add(orb.Point{7, 7})
nearest := q.KNearest(nil, orb.Point{5.25, 5.25}, 3)
expected := []orb.Point{{5, 5}, {6, 6}, {4, 4}}
for i, p := range expected {
if n := nearest[i].Point(); !n.Equal(p) {
t.Errorf("incorrect point %d: %v", i, n)
}
}
}
Actually, the algorithm returns this array : [[6 6] [4 4] [4 4]], instead of the correct expected [[5 5] [6 6] [4 4]]