Package Exports

kd-tree-simple
kd-tree-simple/kd-tree-simple.js

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (kd-tree-simple) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

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;
    }