The libkdtree from liuslnlp

find_k_nearests() not returning the right values

I believe I have found a bug. For some data-sets find_k_nearests() doesn't seems to return the right result. Using the repo example with different data for instance :

#include "kdtree.h"
#include <stdio.h>
#include <stdlib.h>

int main() {
  float datas[108] = { 0, 0, 0,
                        0.333333, 0, 0,
                        0.333333, 0.333333, 0,
                        0, 0.333333, 0,
                        0.333333, 0, 0,
                        0.666667, 0, 0,
                        0.666667, 0.333333, 0,
                        0.333333, 0.333333, 0,
                        0.666667, 0, 0,
                        1, 0, 0,
                        1, 0.333333, 0,
                        0.666667, 0.333333, 0,
                        0, 0.333333, 0,
                        0.333333, 0.333333, 0,
                        0.333333, 0.666667, 0,
                        0, 0.666667, 0,
                        0.333333, 0.333333, 0,
                        0.666667, 0.333333, 0,
                        0.666667, 0.666667, 0,
                        0.333333, 0.666667, 0,
                        0.666667, 0.333333, 0,
                        1, 0.333333, 0,
                        1, 0.666667, 0,
                        0.666667, 0.666667, 0,
                        0, 0.666667, 0,
                        0.333333, 0.666667, 0,
                        0.333333, 1, 0,
                        0, 1, 0,
                        0.333333, 0.666667, 0,
                        0.666667, 0.666667, 0,
                        0.666667, 1, 0,
                        0.333333, 1, 0,
                        0.666667, 0.666667, 0,
                        1, 0.666667, 0,
                        1, 1, 0,
                      0.666667, 1, 0};
  
  
  float labels[100];
  for (size_t i = 0; i < 36; ++i)
    labels[i] = (float)i;
  tree_model *model = build_kdtree(datas, labels, 12, 3, 2);
  float test[3] = {0, 0.666667, 0};
  size_t args[100] = { 0 };
  float dists[100] = {-1};
  find_k_nearests(model, test, 1, args, dists); // This only searches for K neighbors of (3,3,3)
  
  printf("K-Nearest: \n");
  for (size_t i = 0; i < 5; ++i) {
    printf("ID %d, Dist %.2f\n", args[i], dists[i]);
  }
  
  //    tree_node *root = model->root;
  
  
  free(ans);
  free_tree_memory(model->root);
  
  return 0;
}

outputs:

K-Nearest:

ID 11, Dist 0.333334
ID 0, Dist 0
ID 0, Dist 0
ID 0, Dist 0
ID 0, Dist 0

While it should return:

ID 15, Dist 0
ID 0, Dist 0
ID 0, Dist 0
ID 0, Dist 0
ID 0, Dist 0

or:

ID 24, Dist 0
ID 0, Dist 0
ID 0, Dist 0
ID 0, Dist 0
ID 0, Dist 0

三元运算符

p = coor[p->split] <= GetDimVal(p->id, p->split) ? p = p->left : p = p->right;
应该是这样吧: p = coor[p->split] <= GetDimVal(p->id, p->split) ? p->left : p->right;
虽然那么写执行的结果是一样的，但是多了两次赋值，而且阅读代码时会让人感到困惑。

bug : find_k_nearests will return the largest one in the first

printf("K-Nearest: \n");
    for (size_t i = 0; i < 5; ++i) {
        printf("ID %lu, Dist %.2f\n", args[i], dists[i]);
    }
ID 44, Dist 13.04
ID 13, Dist 12.08
ID 8, Dist 11.66
ID 39, Dist 7.00
ID 47, Dist 3.61

the distances is desc , which I think is an error.
std::tuple<size_t, float> FindNearest(const float *coor, size_t k) { return FindKNearests(coor, k)[0]; }
this function also will return the largest distance in k node, not the smallest one.

liuslnlp / libkdtree Goto Github PK

libkdtree's People

Contributors

Stargazers

Watchers

Forkers

libkdtree's Issues

find_k_nearests() not returning the right values

三元运算符

bug : find_k_nearests will return the largest one in the first

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent