kd-tree-simple

simple experimental kd tree for sloppy json objects

non-numeric [NaN] fields are ignored

we have not tested it very thoroughly so use at your own risk

Installation

npm i kd-tree-simple

Usage

// quick rundown:

// var {KDTree} = require('kd-tree-simple');
// const kdTree = new KDTree();
// kdTree.add(myObj); //obj can be arbitrary [see Distance Functions section below]
// kdTree.kNearestNeighbors(k, queryObj, distanceFunc=kdTree.distanceEuclidean, addDistanceField=true) //or kdTree.distanceMSE
// var neighboringObjs = kdTree.kNearestNeighbors(2, {x:0, y:0, z:0});

// experimental kdTree.rangeQuery(range) range like {x: [minX, maxX], y: [minY, maxY]} ==> return list of objects -- all keys must be numeric! 

//bigger rundown:

//function to generate random pts {x,y,z} -- note the kdtree can take objects with arbitrary fields
function generatePts(nPts=1000){
    var res = [];
    var s = 5.0;
    for(var i=0; i<nPts; i++){
        res.push(
            {
                x: Math.random()*s-s/2,
                y: Math.random()*s-s/2,
                z: Math.random()*s-s/2
            }
        )
    }
    return res;
}

var {KDTree} = require('kd-tree-simple');
const kdTree = new KDTree();

var pts = generatePts();
pts.forEach(function(pt){
    kdTree.add(pt);
});

var k = 10; //number of nearest neighbors to get
var doAddDistanceField = true; //add .distance to results
var kNearestNeighbors = kdTree.kNearestNeighbors(k,{x: 0, y: 0, z:0}, kdTree.distanceEuclidean, doAddDistanceField);
console.log(kNearestNeighbors[0]);
// {
//     x: 0.012055808991457084,
//     y: 0.08365982534562777,
//     z: 0.12121469453873823,
//     distance: 0.14777452784366815
// }

//notice how if we leave out a field / dimension, it is ignored by the distance function
//we do not need to set a default value, it is as if the field is ignored
var kNearestNeighbors2 = kdTree.kNearestNeighbors(10,{x: 0, y: 0}, kdTree.distanceEuclidean, doAddDistanceField);
console.log(kNearestNeighbors2[0]);
// {
//     x: -0.13236073516600477,
//     y: 0.026111540644320197,
//     z: -0.6416465917338776,
//     distance: 0.13491173695607525 // <<< notice how this distance no longer includes the contribution of the z coordinate
// }

//we can also use kdTree.distanceMSE

Distance functions:

You can specify your own distance function, here's the included ones. Notice how they are apathetic to missing fields and how we can specify a field to be ignored, default index.

    distanceEuclidean(object1, object2,  ignoreObjFields = {"index":0}) { //any fields in ignoreObjFields are not included in the distance 
        let sum = 0;
    
        for (let key in object1) {
            if (!ignoreObjFields.hasOwnProperty(key) && object2.hasOwnProperty(key)) {
                sum += Math.pow(object1[key] - object2[key], 2);
            }
        }
    
        return Math.sqrt(sum);
    }
    
    distanceMSE(a, b,  ignoreObjFields = {"index":0}) {  //any fields in ignoreObjFields are not included in the distance 
        let totalError = 0;
        let n = 0;
        const errorPow = 2; //2 = normal mse
    
        for (let key in a) {
            if (!ignoreObjFields.hasOwnProperty(key) && b.hasOwnProperty(key)) {
                let error = a[key] - b[key];
                totalError += Math.abs(Math.pow(error,errorPow));
                n++;
            }
        }
    
        var mse = n === 0 ? Infinity : totalError / n;
        return mse;
    }