@thi.ng/geom-accel - npm Package Compare versions

Comparing version 1.0.2 to 1.1.0

CHANGELOG.md

@@ -6,2 +6,18 @@ # Change Log
 
+# [1.1.0](https://github.com/thi-ng/umbrella/compare/@thi.ng/geom-accel@[e-mail]/geom-accel@1.1.0) (2019-02-05)
+
+
+### Features
+
+* **geom-accel:** add selectVals() impl ([bd1754d](https://github.com/thi-ng/umbrella/commit/bd1754d))
+
+
+### Performance Improvements
+
+* **geom-accel:** optimize single nearest point search, fix select() ([9022d5b](https://github.com/thi-ng/umbrella/commit/9022d5b))
+
+
+
+
+
 ## [1.0.2](https://github.com/thi-ng/umbrella/compare/@thi.ng/geom-accel@[e-mail]/geom-accel@1.0.2) (2019-01-31)
@@ -8,0 +24,0 @@

kdtree.d.ts

 import { ICopy, Pair } from "@thi.ng/api";
+import { ISpatialAccel } from "@thi.ng/geom-api";
 import { ReadonlyVec } from "@thi.ng/vectors";
@@ -22,3 +23,3 @@ export declare class KdNode<K extends ReadonlyVec, V> {
  */
-export declare class KdTree<K extends ReadonlyVec, V> implements ICopy<KdTree<K, V>> {
+export declare class KdTree<K extends ReadonlyVec, V> implements ICopy<KdTree<K, V>>, ISpatialAccel<K, V> {
     root: KdNode<K, V>;
@@ -33,9 +34,10 @@ dim: number;
     add(p: K, v: V, eps?: number): boolean;
-    addAll(pts: Iterable<Pair<K, V>>, eps?: number): this;
+    addAll(pts: Iterable<Pair<K, V>>, eps?: number): boolean;
     addKey(k: Readonly<K>, eps?: number): boolean;
-    addKeys(ks: Iterable<Readonly<K>>, eps?: number): this;
+    addKeys(ks: Iterable<Readonly<K>>, eps?: number): boolean;
     remove(p: Readonly<K>): boolean;
-    find(q: Readonly<K>, eps?: number): KdNode<K, V> | undefined;
+    has(k: Readonly<K>, eps?: number): boolean;
     select(q: Readonly<K>, maxNum: number, maxDist?: number): Pair<K, V>[];
     selectKeys(q: Readonly<K>, maxNum: number, maxDist?: number): K[];
+    selectVals(q: Readonly<K>, maxNum: number, maxDist?: number): V[];
     balanceRatio(): number;
@@ -42,0 +44,0 @@ protected buildSelection(q: Readonly<K>, maxNum: number, maxDist?: number): [number, KdNode<K, V>][];

kdtree.js

 import { Heap } from "@thi.ng/heaps";
 import { EPS } from "@thi.ng/math";
 import { ensureArray } from "@thi.ng/transducers";
-import { distSq, empty } from "@thi.ng/vectors";
+import { distSq } from "@thi.ng/vectors";
 const CMP = (a, b) => b[0] - a[0];
@@ -89,6 +89,7 @@ export class KdNode {
     addAll(pts, eps = EPS) {
+        let ok = true;
         for (let [k, v] of pts) {
-            this.add(k, v, eps);
+            ok = ok && this.add(k, v, eps);
         }
-        return this;
+        return ok;
     }
@@ -99,6 +100,7 @@ addKey(k, eps = EPS) {
     addKeys(ks, eps = EPS) {
+        let ok = true;
         for (let k of ks) {
-            this.add(k, null, eps);
+            ok = ok && this.add(k, null, eps);
         }
-        return this;
+        return ok;
     }
@@ -114,4 +116,4 @@ remove(p) {
     }
-    find(q, eps = EPS) {
-        return find(q, this.root, eps * eps);
+    has(k, eps = EPS) {
+        return this.root && !!nearest1(k, [eps * eps, null], [], this.dim, this.root)[1];
     }
@@ -122,7 +124,13 @@ select(q, maxNum, maxDist) {
         const res = [];
-        const src = this.buildSelection(q, maxNum, maxDist);
-        for (let n = src.length; --n >= 0;) {
-            const nn = src[n][1];
-            nn && res.push([nn.k, nn.v]);
+        if (maxNum === 1) {
+            const sel = nearest1(q, [maxDist != null ? maxDist : Infinity, null], [], this.dim, this.root)[1];
+            sel && res.push([sel.k, sel.v]);
         }
+        else {
+            const sel = this.buildSelection(q, maxNum, maxDist);
+            for (let n = sel.length; --n >= 0;) {
+                const nn = sel[n][1];
+                nn && res.push([nn.k, nn.v]);
+            }
+        }
         return res;
@@ -134,9 +142,32 @@ }
         const res = [];
-        const src = this.buildSelection(q, maxNum, maxDist);
-        for (let n = src.length; --n >= 0;) {
-            const nn = src[n][1];
-            nn && res.push(nn.k);
+        if (maxNum === 1) {
+            const sel = nearest1(q, [maxDist != null ? maxDist : Infinity, null], [], this.dim, this.root)[1];
+            sel && res.push(sel.k);
         }
+        else {
+            const src = this.buildSelection(q, maxNum, maxDist);
+            for (let n = src.length; --n >= 0;) {
+                const nn = src[n][1];
+                nn && res.push(nn.k);
+            }
+        }
         return res;
     }
+    selectVals(q, maxNum, maxDist) {
+        if (!this.root)
+            return [];
+        const res = [];
+        if (maxNum === 1) {
+            const sel = nearest1(q, [maxDist != null ? maxDist : Infinity, null], [], this.dim, this.root)[1];
+            sel && res.push(sel.v);
+        }
+        else {
+            const src = this.buildSelection(q, maxNum, maxDist);
+            for (let n = src.length; --n >= 0;) {
+                const nn = src[n][1];
+                nn && res.push(nn.v);
+            }
+        }
+        return res;
+    }
     balanceRatio() {
@@ -147,12 +178,10 @@ return this._length ?
     }
-    buildSelection(q, maxNum, maxDist) {
+    buildSelection(q, maxNum, maxDist = Infinity) {
         const nodes = new Heap(null, { compare: CMP });
-        if (maxDist) {
-            maxDist *= maxDist;
-            const c = [maxDist, null];
-            for (let i = maxNum; --i >= 0;) {
-                nodes.push(c);
-            }
+        maxDist *= maxDist;
+        const c = [maxDist, null];
+        for (let i = maxNum; --i >= 0;) {
+            nodes.push(c);
         }
-        nearest(q, nodes, this.dim, maxNum, this.root);
+        nearest(q, nodes, [], this.dim, maxNum, this.root);
         return nodes.values.sort(CMP);
@@ -244,7 +273,7 @@ }
 };
-const nearest = (q, acc, dims, maxNum, node) => {
+const nearest = (q, acc, tmp, dims, maxNum, node) => {
     const p = node.k;
     const ndist = distSq(p, q);
     if (!node.l && !node.r) {
-        if (ndist < acc.peek()[0]) {
+        if (!acc.length || ndist < acc.peek()[0]) {
             if (acc.length >= maxNum) {
@@ -260,7 +289,6 @@ acc.pushPop([ndist, node]);
     const ndim = node.d;
-    const tp = empty(q);
     for (let i = dims; --i >= 0;) {
-        tp[i] = i === ndim ? q[i] : p[i];
+        tmp[i] = i === ndim ? q[i] : p[i];
     }
-    const tdist = distSq(p, tp);
+    const tdist = distSq(p, tmp);
     let best = !node.r ?
@@ -273,4 +301,4 @@ node.l :
                 node.r;
-    nearest(q, acc, dims, maxNum, best);
-    if (ndist < acc.peek()[0]) {
+    nearest(q, acc, tmp, dims, maxNum, best);
+    if (!acc.length || ndist < acc.peek()[0]) {
         if (acc.length >= maxNum) {
@@ -283,6 +311,47 @@ acc.pushPop([ndist, node]);
     }
-    if (tdist < acc.peek()[0]) {
+    if (!acc.length || tdist < acc.peek()[0]) {
         best = best === node.l ? node.r : node.l;
-        best && nearest(q, acc, dims, maxNum, best);
+        best && nearest(q, acc, tmp, dims, maxNum, best);
     }
 };
+/**
+ * Optimized version of `nearest()` for single closest point search.
+ *
+ * @param q
+ * @param acc
+ * @param dims
+ * @param node
+ */
+const nearest1 = (q, acc, tmp, dims, node) => {
+    const p = node.k;
+    const ndist = distSq(p, q);
+    if (!node.l && !node.r) {
+        if (ndist < acc[0]) {
+            acc[0] = ndist;
+            acc[1] = node;
+        }
+        return acc;
+    }
+    const ndim = node.d;
+    for (let i = dims; --i >= 0;) {
+        tmp[i] = i === ndim ? q[i] : p[i];
+    }
+    const tdist = distSq(p, tmp);
+    let best = !node.r ?
+        node.l :
+        !node.l ?
+            node.r :
+            q[ndim] < p[ndim] ?
+                node.l :
+                node.r;
+    nearest1(q, acc, tmp, dims, best);
+    if (ndist < acc[0]) {
+        acc[0] = ndist;
+        acc[1] = node;
+    }
+    if (tdist < acc[0]) {
+        best = best === node.l ? node.r : node.l;
+        best && nearest1(q, acc, tmp, dims, best);
+    }
+    return acc;
+};

lib/index.js

@@ -87,6 +87,7 @@ 'use strict';
     addAll(pts, eps = math.EPS) {
+        let ok = true;
         for (let [k, v] of pts) {
-            this.add(k, v, eps);
+            ok = ok && this.add(k, v, eps);
         }
-        return this;
+        return ok;
     }
@@ -97,6 +98,7 @@ addKey(k, eps = math.EPS) {
     addKeys(ks, eps = math.EPS) {
+        let ok = true;
         for (let k of ks) {
-            this.add(k, null, eps);
+            ok = ok && this.add(k, null, eps);
         }
-        return this;
+        return ok;
     }
@@ -112,4 +114,4 @@ remove(p) {
     }
-    find(q, eps = math.EPS) {
-        return find(q, this.root, eps * eps);
+    has(k, eps = math.EPS) {
+        return this.root && !!nearest1(k, [eps * eps, null], [], this.dim, this.root)[1];
     }
@@ -120,7 +122,13 @@ select(q, maxNum, maxDist) {
         const res = [];
-        const src = this.buildSelection(q, maxNum, maxDist);
-        for (let n = src.length; --n >= 0;) {
-            const nn = src[n][1];
-            nn && res.push([nn.k, nn.v]);
+        if (maxNum === 1) {
+            const sel = nearest1(q, [maxDist != null ? maxDist : Infinity, null], [], this.dim, this.root)[1];
+            sel && res.push([sel.k, sel.v]);
         }
+        else {
+            const sel = this.buildSelection(q, maxNum, maxDist);
+            for (let n = sel.length; --n >= 0;) {
+                const nn = sel[n][1];
+                nn && res.push([nn.k, nn.v]);
+            }
+        }
         return res;
@@ -132,9 +140,32 @@ }
         const res = [];
-        const src = this.buildSelection(q, maxNum, maxDist);
-        for (let n = src.length; --n >= 0;) {
-            const nn = src[n][1];
-            nn && res.push(nn.k);
+        if (maxNum === 1) {
+            const sel = nearest1(q, [maxDist != null ? maxDist : Infinity, null], [], this.dim, this.root)[1];
+            sel && res.push(sel.k);
         }
+        else {
+            const src = this.buildSelection(q, maxNum, maxDist);
+            for (let n = src.length; --n >= 0;) {
+                const nn = src[n][1];
+                nn && res.push(nn.k);
+            }
+        }
         return res;
     }
+    selectVals(q, maxNum, maxDist) {
+        if (!this.root)
+            return [];
+        const res = [];
+        if (maxNum === 1) {
+            const sel = nearest1(q, [maxDist != null ? maxDist : Infinity, null], [], this.dim, this.root)[1];
+            sel && res.push(sel.v);
+        }
+        else {
+            const src = this.buildSelection(q, maxNum, maxDist);
+            for (let n = src.length; --n >= 0;) {
+                const nn = src[n][1];
+                nn && res.push(nn.v);
+            }
+        }
+        return res;
+    }
     balanceRatio() {
@@ -145,12 +176,10 @@ return this._length ?
     }
-    buildSelection(q, maxNum, maxDist) {
+    buildSelection(q, maxNum, maxDist = Infinity) {
         const nodes = new heaps.Heap(null, { compare: CMP });
-        if (maxDist) {
-            maxDist *= maxDist;
-            const c = [maxDist, null];
-            for (let i = maxNum; --i >= 0;) {
-                nodes.push(c);
-            }
+        maxDist *= maxDist;
+        const c = [maxDist, null];
+        for (let i = maxNum; --i >= 0;) {
+            nodes.push(c);
         }
-        nearest(q, nodes, this.dim, maxNum, this.root);
+        nearest(q, nodes, [], this.dim, maxNum, this.root);
         return nodes.values.sort(CMP);
@@ -230,7 +259,7 @@ }
 };
-const nearest = (q, acc, dims, maxNum, node) => {
+const nearest = (q, acc, tmp, dims, maxNum, node) => {
     const p = node.k;
     const ndist = vectors.distSq(p, q);
     if (!node.l && !node.r) {
-        if (ndist < acc.peek()[0]) {
+        if (!acc.length || ndist < acc.peek()[0]) {
             if (acc.length >= maxNum) {
@@ -246,7 +275,6 @@ acc.pushPop([ndist, node]);
     const ndim = node.d;
-    const tp = vectors.empty(q);
     for (let i = dims; --i >= 0;) {
-        tp[i] = i === ndim ? q[i] : p[i];
+        tmp[i] = i === ndim ? q[i] : p[i];
     }
-    const tdist = vectors.distSq(p, tp);
+    const tdist = vectors.distSq(p, tmp);
     let best = !node.r ?
@@ -259,4 +287,4 @@ node.l :
                 node.r;
-    nearest(q, acc, dims, maxNum, best);
-    if (ndist < acc.peek()[0]) {
+    nearest(q, acc, tmp, dims, maxNum, best);
+    if (!acc.length || ndist < acc.peek()[0]) {
         if (acc.length >= maxNum) {
@@ -269,9 +297,42 @@ acc.pushPop([ndist, node]);
     }
-    if (tdist < acc.peek()[0]) {
+    if (!acc.length || tdist < acc.peek()[0]) {
         best = best === node.l ? node.r : node.l;
-        best && nearest(q, acc, dims, maxNum, best);
+        best && nearest(q, acc, tmp, dims, maxNum, best);
     }
 };
+const nearest1 = (q, acc, tmp, dims, node) => {
+    const p = node.k;
+    const ndist = vectors.distSq(p, q);
+    if (!node.l && !node.r) {
+        if (ndist < acc[0]) {
+            acc[0] = ndist;
+            acc[1] = node;
+        }
+        return acc;
+    }
+    const ndim = node.d;
+    for (let i = dims; --i >= 0;) {
+        tmp[i] = i === ndim ? q[i] : p[i];
+    }
+    const tdist = vectors.distSq(p, tmp);
+    let best = !node.r ?
+        node.l :
+        !node.l ?
+            node.r :
+            q[ndim] < p[ndim] ?
+                node.l :
+                node.r;
+    nearest1(q, acc, tmp, dims, best);
+    if (ndist < acc[0]) {
+        acc[0] = ndist;
+        acc[1] = node;
+    }
+    if (tdist < acc[0]) {
+        best = best === node.l ? node.r : node.l;
+        best && nearest1(q, acc, tmp, dims, best);
+    }
+    return acc;
+};
 
 exports.KdNode = KdNode;
 exports.KdTree = KdTree;

lib/index.umd.js

@@ -84,6 +84,7 @@ (function (global, factory) {
         addAll(pts, eps = math.EPS) {
+            let ok = true;
             for (let [k, v] of pts) {
-                this.add(k, v, eps);
+                ok = ok && this.add(k, v, eps);
             }
-            return this;
+            return ok;
         }
@@ -94,6 +95,7 @@ addKey(k, eps = math.EPS) {
         addKeys(ks, eps = math.EPS) {
+            let ok = true;
             for (let k of ks) {
-                this.add(k, null, eps);
+                ok = ok && this.add(k, null, eps);
             }
-            return this;
+            return ok;
         }
@@ -109,4 +111,4 @@ remove(p) {
         }
-        find(q, eps = math.EPS) {
-            return find(q, this.root, eps * eps);
+        has(k, eps = math.EPS) {
+            return this.root && !!nearest1(k, [eps * eps, null], [], this.dim, this.root)[1];
         }
@@ -117,7 +119,13 @@ select(q, maxNum, maxDist) {
             const res = [];
-            const src = this.buildSelection(q, maxNum, maxDist);
-            for (let n = src.length; --n >= 0;) {
-                const nn = src[n][1];
-                nn && res.push([nn.k, nn.v]);
+            if (maxNum === 1) {
+                const sel = nearest1(q, [maxDist != null ? maxDist : Infinity, null], [], this.dim, this.root)[1];
+                sel && res.push([sel.k, sel.v]);
             }
+            else {
+                const sel = this.buildSelection(q, maxNum, maxDist);
+                for (let n = sel.length; --n >= 0;) {
+                    const nn = sel[n][1];
+                    nn && res.push([nn.k, nn.v]);
+                }
+            }
             return res;
@@ -129,9 +137,32 @@ }
             const res = [];
-            const src = this.buildSelection(q, maxNum, maxDist);
-            for (let n = src.length; --n >= 0;) {
-                const nn = src[n][1];
-                nn && res.push(nn.k);
+            if (maxNum === 1) {
+                const sel = nearest1(q, [maxDist != null ? maxDist : Infinity, null], [], this.dim, this.root)[1];
+                sel && res.push(sel.k);
             }
+            else {
+                const src = this.buildSelection(q, maxNum, maxDist);
+                for (let n = src.length; --n >= 0;) {
+                    const nn = src[n][1];
+                    nn && res.push(nn.k);
+                }
+            }
             return res;
         }
+        selectVals(q, maxNum, maxDist) {
+            if (!this.root)
+                return [];
+            const res = [];
+            if (maxNum === 1) {
+                const sel = nearest1(q, [maxDist != null ? maxDist : Infinity, null], [], this.dim, this.root)[1];
+                sel && res.push(sel.v);
+            }
+            else {
+                const src = this.buildSelection(q, maxNum, maxDist);
+                for (let n = src.length; --n >= 0;) {
+                    const nn = src[n][1];
+                    nn && res.push(nn.v);
+                }
+            }
+            return res;
+        }
         balanceRatio() {
@@ -142,12 +173,10 @@ return this._length ?
         }
-        buildSelection(q, maxNum, maxDist) {
+        buildSelection(q, maxNum, maxDist = Infinity) {
             const nodes = new heaps.Heap(null, { compare: CMP });
-            if (maxDist) {
-                maxDist *= maxDist;
-                const c = [maxDist, null];
-                for (let i = maxNum; --i >= 0;) {
-                    nodes.push(c);
-                }
+            maxDist *= maxDist;
+            const c = [maxDist, null];
+            for (let i = maxNum; --i >= 0;) {
+                nodes.push(c);
             }
-            nearest(q, nodes, this.dim, maxNum, this.root);
+            nearest(q, nodes, [], this.dim, maxNum, this.root);
             return nodes.values.sort(CMP);
@@ -227,7 +256,7 @@ }
     };
-    const nearest = (q, acc, dims, maxNum, node) => {
+    const nearest = (q, acc, tmp, dims, maxNum, node) => {
         const p = node.k;
         const ndist = vectors.distSq(p, q);
         if (!node.l && !node.r) {
-            if (ndist < acc.peek()[0]) {
+            if (!acc.length || ndist < acc.peek()[0]) {
                 if (acc.length >= maxNum) {
@@ -243,7 +272,6 @@ acc.pushPop([ndist, node]);
         const ndim = node.d;
-        const tp = vectors.empty(q);
         for (let i = dims; --i >= 0;) {
-            tp[i] = i === ndim ? q[i] : p[i];
+            tmp[i] = i === ndim ? q[i] : p[i];
         }
-        const tdist = vectors.distSq(p, tp);
+        const tdist = vectors.distSq(p, tmp);
         let best = !node.r ?
@@ -256,4 +284,4 @@ node.l :
                     node.r;
-        nearest(q, acc, dims, maxNum, best);
-        if (ndist < acc.peek()[0]) {
+        nearest(q, acc, tmp, dims, maxNum, best);
+        if (!acc.length || ndist < acc.peek()[0]) {
             if (acc.length >= maxNum) {
@@ -266,7 +294,40 @@ acc.pushPop([ndist, node]);
         }
-        if (tdist < acc.peek()[0]) {
+        if (!acc.length || tdist < acc.peek()[0]) {
             best = best === node.l ? node.r : node.l;
-            best && nearest(q, acc, dims, maxNum, best);
+            best && nearest(q, acc, tmp, dims, maxNum, best);
         }
     };
+    const nearest1 = (q, acc, tmp, dims, node) => {
+        const p = node.k;
+        const ndist = vectors.distSq(p, q);
+        if (!node.l && !node.r) {
+            if (ndist < acc[0]) {
+                acc[0] = ndist;
+                acc[1] = node;
+            }
+            return acc;
+        }
+        const ndim = node.d;
+        for (let i = dims; --i >= 0;) {
+            tmp[i] = i === ndim ? q[i] : p[i];
+        }
+        const tdist = vectors.distSq(p, tmp);
+        let best = !node.r ?
+            node.l :
+            !node.l ?
+                node.r :
+                q[ndim] < p[ndim] ?
+                    node.l :
+                    node.r;
+        nearest1(q, acc, tmp, dims, best);
+        if (ndist < acc[0]) {
+            acc[0] = ndist;
+            acc[1] = node;
+        }
+        if (tdist < acc[0]) {
+            best = best === node.l ? node.r : node.l;
+            best && nearest1(q, acc, tmp, dims, best);
+        }
+        return acc;
+    };
 
@@ -273,0 +334,0 @@ exports.KdNode = KdNode;

package.json

 {
     "name": "@thi.ng/geom-accel",
-    "version": "1.0.2",
-    "description": "TODO",
+    "version": "1.1.0",
+    "description": "nD spatial indexing data structures",
     "module": "./index.js",
@@ -19,3 +19,3 @@ "main": "./lib/index.js",
         "build:es6": "tsc --declaration",
-        "build:bundle": "../../scripts/bundle-module geomAccel api heaps math transducers vectors",
+        "build:bundle": "../../scripts/bundle-module",
         "test": "rimraf build && tsc -p test/tsconfig.json && nyc mocha build/test/*.js",
@@ -36,16 +36,20 @@ "clean": "rimraf *.js *.d.ts .nyc_output build coverage doc lib internal",
     "dependencies": {
-        "@thi.ng/api": "^5.0.1",
-        "@thi.ng/heaps": "^1.0.1",
-        "@thi.ng/math": "^1.0.1",
-        "@thi.ng/transducers": "^3.0.2",
-        "@thi.ng/vectors": "^2.1.1"
+        "@thi.ng/api": "^5.0.2",
+        "@thi.ng/geom-api": "^0.1.0",
+        "@thi.ng/heaps": "^1.0.2",
+        "@thi.ng/math": "^1.1.0",
+        "@thi.ng/transducers": "^4.0.0",
+        "@thi.ng/vectors": "^2.2.0"
     },
     "keywords": [
+        "2D",
+        "3D",
+        "nD",
+        "data structure",
         "ES6",
         "acceleration",
         "kd-tree",
-        "octree",
         "pointcloud",
-        "quadtree",
-        "spatial indexing",
+        "spatial index",
+        "tree",
         "typescript"
@@ -57,3 +61,3 @@ ],
     "sideEffects": false,
-    "gitHead": "50a5098ac32e9c939d50b02f2207c9df6c623663"
+    "gitHead": "74fb4d83013785ce7a95357c565426a046657e74"
 }

No alert changes

Improved metrics

Total package byte prevSize

74602

increased by20.82%

Lines of code

1042

increased by22.73%

Worsened metrics

Dependency count

6

increased by20%

Dependency changes

• + [e-mail]/geom-api@^0.1.0

• + [e-mail]/geom-api@0.1.12(transitive)

• + [e-mail]/transducers@4.0.1(transitive)

• - [e-mail]/transducers@3.0.2(transitive)

• [e-mail]/api@^5.0.2

• [e-mail]/heaps@^1.0.2

• [e-mail]/math@^1.1.0

• [e-mail]/transducers@^4.0.0

• [e-mail]/vectors@^2.2.0