Nearest function not operating as intended

[sciatti]

I am trying to use this library to solve the all-nearest-neighbors problem in a function I am using, but I am receiving unexpected output from the library. I have attached a codepen showing my process and the output of the codepen is wrong unless I am using this library incorrectly.

Thank you!

[benmaier]

the library reorders the original point-array in-place, so it's best if you pass a copy of the point array to the tree, such that it can mess it up all it wants without you having to deal with the aftermath. Just use a .slice() to make a copy:

const tree = new kdTreeJavascript.kdTree(points.slice(), distance, dimensions);

Also, removing and adding an element is, for large systems, probably more costly than finding the closest two elements and then filtering for distance. I'd do this for the loop:

for (let i = 0; i < points.length; i++) {
  let x = (tree.nearest(points[i], 2)).filter(el=> el[1]>0);
  console.log("point: ", points[i]," distance: ", x[0][1]);
}

This should give you the right output: https://codepen.io/sciatti/pen/wvXoJmp

[benmaier]

also refer to my comment in #16

[sciatti]

Thank you for your help, unfortunately when moving this into my large scale set of data (50k+ points) I seem to be hitting a call stack error and exceeding the maximum callstack size. Is there a fix for this or is this just a limitation of the library and/or my javascript runtime?

[benmaier]

I see. no idea then! Maybe adding an index to your data points as I did in #16 might help. Other than that I fear there's no other way than reimplementing kd-trees yourself or go into the existing code and fix it. good luck! (note that I'm not affiliated with this library, I'm just a user myself)

[sciatti]

Thanks for your help! I have vetted a different solution for now but will keep an eye on this to see if there's any luck on that callstack bug. Thanks again.