# kd-tree-simple

> simple experimental kd tree for sloppy json objects

Latest version **0.0.132** (published 2023-10-15) · CC0 license · 0 weekly downloads

## Install

```sh
npm install kd-tree-simple
pnpm add kd-tree-simple
yarn add kd-tree-simple
bun add kd-tree-simple
```

## Health

**Score 15/100 (F)** — status: abandoned.

Positive: no vulnerabilities.

Warnings: low downloads; no types; no esm support; pre 1.0.

Negative: abandoned; low maintenance score.

## Facts

| | |
|---|---|
| Version | 0.0.132 |
| Published | 2023-10-15 |
| First published | 2023-07-21 |
| Weekly downloads | 0 |
| License | CC0 |
| TypeScript types | none |
| Module format | CommonJS |
| Dependencies | 1 |
| Unpacked size | 14.8 KB |
| Known vulnerabilities | 0 |
| Install scripts | no |
| Author | stonkpunk |
| Maintainers | stonkpunk |
| Keywords | kd, tree |

## Links

- npm: https://www.npmjs.com/package/kd-tree-simple
- Homepage: https://github.com/stonkpunk/my-npm-modules/tree/main/kd-tree-simple
- npm.io page: https://npm.io/package/kd-tree-simple

## Dependencies (1)

- [js-priority-queue](https://npm.io/package/js-priority-queue.md) ^0.1.5

## Alternatives

- [@mdxeditor/editor](https://npm.io/package/@mdxeditor/editor.md) — 962.4K weekly downloads
- [mmdb-lib](https://npm.io/package/mmdb-lib.md) — 680.9K weekly downloads
- [playcanvas](https://npm.io/package/playcanvas.md) — 36.2K weekly downloads
- [@glw907/cairn-cms](https://npm.io/package/@glw907/cairn-cms.md) — 967 weekly downloads
- [markdown-to-confluence](https://npm.io/package/markdown-to-confluence.md) — 103 weekly downloads

## Recent versions

- 0.0.132 (latest) — 2023-10-15
- 0.0.131 — 2023-08-18
- 0.0.13 — 2023-08-18
- 0.0.12 — 2023-08-18
- 0.0.11 — 2023-07-21
- 0.0.1 — 2023-07-21

## 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

```sh
npm i kd-tree-simple
```

## Usage 

```javascript
// 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`.

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

[//]: # ()
[//]: # (## See Also)

[//]: # ()
[//]: # (- [triangle-triangle-intersection]&#40;https://www.npmjs.com/package/triangle-triangle-intersection&#41; - intersection between 2 triangles)

[//]: # (- [triangle-distance]&#40;https://www.npmjs.com/package/triangle-distance&#41; - distance to triangle)


[![stonks](https://i.imgur.com/UpDxbfe.png)](https://www.npmjs.com/~stonkpunk)

---
_Source: https://npm.io/package/kd-tree-simple · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._