The remove method has errors (not really removing some nodes)

[santoxi]

After having removed some nodes, they can still be found in the kdTree in some situations.

Here is an example of the remove method errors:

https://gist.github.com/santoxi/ba8d283f9a21523fa45d23d8e9c3046e

as a temporary work-around, I added a fourth argument to "nearest" to pass a predicate to filter the matched nodes, which might be also useful to add:

    this.nearest = function (point, maxNodes, maxDistance, predicate) {
            predicate = predicate || (x => true);
....
        linearDistance = metric(linearPoint, node.obj);

        if (node.right === null && node.left === null) {
          if (predicate(node.obj) && (bestNodes.size() < maxNodes || ownDistance < bestNodes.peek()[1])) {
            saveNode(node, ownDistance);
          }
          return;
        }
....
        nearestSearch(bestChild);

        if (predicate(node.obj) && (bestNodes.size() < maxNodes || ownDistance < bestNodes.peek()[1])) {
          saveNode(node, ownDistance);
        }

[mariosgit]

I did a fix for that in my fork, commented it in pull request #31 .

[jnromero]

I believe the problem may be caused when inserting a list of points when initializing the tree.

Here is an example where I get an error when initializing the kdTree with an array of points (number of items in tree remains at 2 even after removing):

https://jsfiddle.net/shj5xkfp/1/

When I change to inserting the points individually, there is no problem anymore (number of items goes from 2 to 1 to 0 after removal):

https://jsfiddle.net/shj5xkfp/

It also appears that (in this example at least, on my computer) that adding the points individually is faster than adding the points as an array on initialization:

https://jsfiddle.net/1un5mpc3/

[mariosgit]

For reference.. my usecase looks like this https://jsfiddle.net/rphak8ut/36/

Back in the day.. the remove function did not remove points and my search for the next nearest always returned the same point.

However in the fiddle it works !? The method of inserting the points as suggested by @jnromero does not make a difference.