search

supercollider-quarks / KDTree

A kd-tree data structure, for efficiently querying large collections of points in Euclidean space (e.g. for nearest-neighbour searches).
1 stars 2 forks source link

knn is not supported #4

Open elgiano opened 2 years ago

elgiano commented 2 years ago

I see this quark is long unmaintained, so probably just a note for future self:

KDTree doesn't do K-Nearest Neighbors: it always returns one item, regardless of k. KNN was planned but never implemented.

dyfer commented 2 years ago

@dmartinp have you maybe implemented such functionality in some of your work?

elgiano commented 2 years ago

@dyfer thanks for reaching out! would be great to have it in there!

just as a note, for now I make up for it with radiusSearch, I guess it would become heavy for large datasets, but for my present use case it works fine!

~doKNN = { |kdtree, query, k = 1, incExact = false|
    var order;
    var nearestDist = kdtree.nearest(query, incExact: incExact)[1];
    var nodesAround = kdtree.radiusSearch(query, nearestDist * 2);
    if (incExact.not) {
        nodesAround = nodesAround.reject { |node| node.location == query }
    };
    order = nodesAround.collect(_.location).order { |a, b|
        pow(a - query, 2).sum < pow(b - query, 2).sum
    };
    nodesAround[order][..(k - 1)]
}