{"_id":"static-kdtree","_rev":"17-884c599f85202b1ab208c6c291adb750","name":"static-kdtree","description":"A kdtree data structure","dist-tags":{"latest":"1.0.2"},"versions":{"0.0.0":{"name":"static-kdtree","version":"0.0.0","description":"A kdtree data structure","main":"kdtree.js","directories":{"test":"test"},"dependencies":{"bit-twiddle":"~0.0.2","inorder-tree-layout":"~0.0.8","ndarray-pack":"~1.1.0","ndarray-scratch":"~1.0.0","ndarray-select":"~1.0.0","typedarray-pool":"~1.0.0","ndarray-ops":"~1.2.1","ndarray":"~1.0.13"},"devDependencies":{"async":"~0.7.0","dup":"~0.0.0","tape":"~2.12.3","look-alike":"~1.0.1","kdtree":"~0.0.10","iota-array":"~0.0.1","ndarray-unpack":"~0.0.0","beefy":"^1.1.0","browserify":"^3.44.0"},"scripts":{"test":"tape test/*.js","bench":"node bench/run.js","bench-browser":"beefy bench/run.js --open"},"repository":{"type":"git","url":"git://github.com/mikolalysenko/static-kdtree.git"},"keywords":["kdtree","static","pure","javascript","range","orthogonal","bounding","box","point","sphere","query","nearest","neighbor","knn","nn","rnn","searching","closest","query"],"author":{"name":"Mikola Lysenko"},"license":"MIT","bugs":{"url":"https://github.com/mikolalysenko/static-kdtree/issues"},"homepage":"https://github.com/mikolalysenko/static-kdtree","_id":"static-kdtree@0.0.0","dist":{"shasum":"10aceb901d58e0870fa698c8bd37b8de815bf7c7","tarball":"https://registry.npmjs.org/static-kdtree/-/static-kdtree-0.0.0.tgz","integrity":"sha512-wAZvgp6iMgmRc/ZVi2K/cJgQMP/6o+jqZ4fdz7WzK0QCnoisemcfJ2TLVcg6lNeFf9YtLI3/QQS3A5EqI1FUkA==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIDtxZNxR7HT9Z1LpNP0BCdG8L4kUk5KjjBJB7uEjmlzMAiEAgJ9bnNRaFa+kTQlnzxkzwSyfrC4QwtM81XsNqE5FgKM="}]},"_from":".","_npmVersion":"1.4.3","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}]},"0.0.1":{"name":"static-kdtree","version":"0.0.1","description":"A kdtree data structure","main":"kdtree.js","directories":{"test":"test"},"dependencies":{"bit-twiddle":"~0.0.2","inorder-tree-layout":"~0.0.8","ndarray-pack":"~1.1.0","ndarray-scratch":"~1.0.0","ndarray-select":"~1.0.0","typedarray-pool":"~1.0.0","ndarray-ops":"~1.2.1","ndarray":"~1.0.13"},"devDependencies":{"async":"~0.7.0","dup":"~0.0.0","tape":"~2.12.3","look-alike":"~1.0.1","kdtree":"~0.0.10","iota-array":"~0.0.1","ndarray-unpack":"~0.0.0","beefy":"^1.1.0","browserify":"^3.44.0"},"scripts":{"test":"tape test/*.js","bench":"node bench/run.js","bench-browser":"beefy bench/run.js --open"},"repository":{"type":"git","url":"git://github.com/mikolalysenko/static-kdtree.git"},"keywords":["kdtree","static","pure","javascript","range","orthogonal","bounding","box","point","sphere","query","nearest","neighbor","knn","nn","rnn","searching","closest","query"],"author":{"name":"Mikola Lysenko"},"license":"MIT","bugs":{"url":"https://github.com/mikolalysenko/static-kdtree/issues"},"homepage":"https://github.com/mikolalysenko/static-kdtree","_id":"static-kdtree@0.0.1","dist":{"shasum":"2dfa42a9020f94402da2124c774295a42c14e421","tarball":"https://registry.npmjs.org/static-kdtree/-/static-kdtree-0.0.1.tgz","integrity":"sha512-XodYqkMvNNsdOE+EnwaDpafbNRhaz1bC2/zt/iKB/aUX/RDFMQyGWFKLJmT+h3fotEfljfsiGDN+HPPZ1hiiJg==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEQCIBQ7WnvUKCaU0hOcFarSWynG544tqpeX3YNV/Sd7mCXiAiAq98Xp9QBEzOuujRDbYU8WTBuwM3qYSn+9AjUM2lJ63g=="}]},"_from":".","_npmVersion":"1.4.3","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}]},"1.0.0":{"name":"static-kdtree","version":"1.0.0","description":"A kdtree data structure","main":"kdtree.js","directories":{"test":"test"},"dependencies":{"bit-twiddle":"^1.0.0","inorder-tree-layout":"^1.0.0","ndarray-pack":"^1.1.0","ndarray-scratch":"^1.0.0","ndarray-select":"^1.0.0","typedarray-pool":"^1.0.0","ndarray-ops":"^1.2.1","ndarray":"^1.0.13"},"devDependencies":{"async":"~0.7.0","dup":"~0.0.0","tape":"~2.12.3","look-alike":"~1.0.1","kdtree":"~0.0.10","iota-array":"~0.0.1","ndarray-unpack":"~0.0.0","beefy":"^1.1.0","browserify":"^3.44.0"},"scripts":{"test":"tape test/*.js","bench":"node bench/run.js","bench-browser":"beefy bench/run.js --open"},"repository":{"type":"git","url":"git://github.com/mikolalysenko/static-kdtree.git"},"keywords":["kdtree","static","pure","javascript","range","orthogonal","bounding","box","point","sphere","query","nearest","neighbor","knn","nn","rnn","searching","closest","query"],"author":{"name":"Mikola Lysenko"},"license":"MIT","bugs":{"url":"https://github.com/mikolalysenko/static-kdtree/issues"},"homepage":"https://github.com/mikolalysenko/static-kdtree","_id":"static-kdtree@1.0.0","dist":{"shasum":"361e66bd4696e3b5ee6e5bd83b6dd4a249c14222","tarball":"https://registry.npmjs.org/static-kdtree/-/static-kdtree-1.0.0.tgz","integrity":"sha512-+1lQdkhSOic6gIG3gG0oDJeb8dv3yihRSnbHLT4H1UKd9AI78DaAMWIvFBt7074GCYMoMh/xIE/TYRAY1uwl8w==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQDciSIDqgFUez+ka8WXQVR64emUI/i3Jpnq8IuB75ieqgIhAL4S/YMRsiKomxMdqb9945csRzKvODI/gbZPqjwjX4Uo"}]},"_from":".","_npmVersion":"1.4.3","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}]},"1.0.1":{"name":"static-kdtree","version":"1.0.1","description":"A kdtree data structure","main":"kdtree.js","directories":{"test":"test"},"dependencies":{"bit-twiddle":"^1.0.0","inorder-tree-layout":"^1.0.0","ndarray-pack":"^1.1.0","ndarray-scratch":"^1.0.0","ndarray-select":"^1.0.0","typedarray-pool":"^1.0.0","ndarray-ops":"^1.2.1","ndarray":"^1.0.13"},"devDependencies":{"async":"~0.7.0","dup":"~0.0.0","tape":"~2.12.3","look-alike":"~1.0.1","kdtree":"~0.0.10","iota-array":"~0.0.1","ndarray-unpack":"~0.0.0","beefy":"^1.1.0","browserify":"^3.44.0"},"scripts":{"test":"tape test/*.js","bench":"node bench/run.js","bench-browser":"beefy bench/run.js --open"},"repository":{"type":"git","url":"git://github.com/mikolalysenko/static-kdtree.git"},"keywords":["kdtree","static","pure","javascript","range","orthogonal","bounding","box","point","sphere","query","nearest","neighbor","knn","nn","rnn","searching","closest","query"],"author":{"name":"Mikola Lysenko"},"license":"MIT","bugs":{"url":"https://github.com/mikolalysenko/static-kdtree/issues"},"homepage":"https://github.com/mikolalysenko/static-kdtree","_id":"static-kdtree@1.0.1","dist":{"shasum":"41c3cee0ccb16bde8014d8473c7cc31ee69b6374","tarball":"https://registry.npmjs.org/static-kdtree/-/static-kdtree-1.0.1.tgz","integrity":"sha512-yZ/YyQAxOyHzlg/2uyzxieOMUHXGGqvx0jc9Uiyz0chn2ztvWVtxxc4p9zgODy17jrWqnp7Sbh4ELJygkH6dqA==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQDUBz7jlMdyV21Fm+OQhIhXw2PLoEbUt9F0UsaF6TOomgIhAICvMhWon2kBa3HsLweSnS7QglERbgwfF3a7nxUingJ9"}]},"_from":".","_npmVersion":"1.4.3","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}]},"1.0.2":{"name":"static-kdtree","version":"1.0.2","description":"A kdtree data structure","main":"kdtree.js","directories":{"test":"test"},"dependencies":{"bit-twiddle":"^1.0.0","inorder-tree-layout":"^1.0.0","ndarray-pack":"^1.1.0","ndarray-scratch":"^1.0.0","ndarray-select":"^1.0.0","typedarray-pool":"^1.0.0","ndarray-ops":"^1.2.1","ndarray":"^1.0.13"},"devDependencies":{"async":"~0.7.0","dup":"~0.0.0","tape":"~2.12.3","look-alike":"~1.0.1","kdtree":"~0.0.10","iota-array":"~0.0.1","ndarray-unpack":"~0.0.0","beefy":"^1.1.0","browserify":"^3.44.0"},"scripts":{"test":"tape test/*.js","bench":"node bench/run.js","bench-browser":"beefy bench/run.js --open"},"repository":{"type":"git","url":"git://github.com/mikolalysenko/static-kdtree.git"},"keywords":["kdtree","static","pure","javascript","range","orthogonal","bounding","box","point","sphere","query","nearest","neighbor","knn","nn","rnn","searching","closest","query"],"author":{"name":"Mikola Lysenko"},"license":"MIT","bugs":{"url":"https://github.com/mikolalysenko/static-kdtree/issues"},"homepage":"https://github.com/mikolalysenko/static-kdtree","testling":{"files":"test/*.js","browsers":["ie/8..latest","firefox/17..latest","firefox/nightly","chrome/22..latest","chrome/canary","opera/12..latest","opera/next","safari/5.1..latest","ipad/6.0..latest","iphone/6.0..latest","android-browser/4.2..latest"]},"gitHead":"9bbc8397ca81c5bf2233776310206ed779a83c2e","_id":"static-kdtree@1.0.2","_npmVersion":"5.3.0","_nodeVersion":"8.5.0","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"dist":{"integrity":"sha512-0EnWbb9V5TKZp+SvS59wzXGDFzA02YTpOfE73R1Exj2MK7fNyJELtAeSMW/p23nc2HFV1HqHxTS19aflt6f83g==","shasum":"571c120e1bf8254207eff839f09620ef26f081c2","tarball":"https://registry.npmjs.org/static-kdtree/-/static-kdtree-1.0.2.tgz","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEQCIHWFJpb2hjSOJhIXI7hnVXEhOxXKXxLZ44mVyFCtDnbVAiAZXt+Fw5/qdjzb2IT9L8vKkJmDmcPtgyNeXHeGJr1ujw=="}]},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/static-kdtree-1.0.2.tgz_1513325307489_0.3544807417783886"}}},"readme":"static-kdtree\n=============\n[kd-trees](http://en.wikipedia.org/wiki/K-d_tree) are a [compact](http://en.wikipedia.org/wiki/Succinct_data_structure) data structure for answering orthogonal range and nearest neighbor queries on higher dimensional point data in linear time.  While they are not as efficient at answering orthogonal range queries as [range trees](http://en.wikipedia.org/wiki/Range_tree) - especially in low dimensions - kdtrees consume exponentially less space, support k-nearest neighbor queries and are relatively cheap to construct. This makes them useful in small to medium dimensions for achieving a modest speed up over a linear scan.\n\nNote that kd-trees are not the best data structure in all circumstances. If you want to do range searching, here is a chart to help you select one which is appropriate for a given dimension:\n\n| Dimension | Preferred Data Structure | Complexity | Size |\n|-----------|--------------------------|------------|------|\n|     1     | [Binary search tree](http://en.wikipedia.org/wiki/Binary_search_tree)       |  O(log(n)) | O(n) |\n|    2-3    | [Range tree](http://en.wikipedia.org/wiki/Range_tree)               | O(log^(d-1)(n)) | O(n log^(d-1) (n)) |\n|   Medium  | [kd-tree](http://en.wikipedia.org/wiki/K-d_tree)                  | O(d*n^(1-1/d)) | O(n) |\n|   Big     | [Array](http://en.wikipedia.org/wiki/Array_data_structure)                    | O(n)       | O(n) |\n\nAnd for nearest neighbor searching, here is a survey of some different options:\n\n| Dimension | Preferred Data Structure | Complexity | Size |\n|-----------|--------------------------|------------|------|\n|     1     | [Binary search tree](http://en.wikipedia.org/wiki/Binary_search_tree)       |  O(log(n)) | O(n) |\n|    2    | [Voronoi diagram](http://en.wikipedia.org/wiki/Voronoi_diagram) | O(log(n)) | O(n) |\n|   Medium  | [kd-tree](http://en.wikipedia.org/wiki/K-d_tree)                  | O(n) (but maybe better) | O(n) |\n|   Big     | [Array](http://en.wikipedia.org/wiki/Array_data_structure)                    | O(n)       | O(n) |\n\nIt is also worth mentioning that for approximate nearest neighbor queries or queries with a fixed size radius, [grids](http://en.wikipedia.org/wiki/Regular_grid) and [locality sensitive hashing](http://en.wikipedia.org/wiki/Locality_sensitive_hashing) are strictly better options.  In these charts the transition between \"Medium\" and \"Big\" depends on how many points there are in the data structure.  As the number of points grows larger, the dimension at which kdtrees become practical goes up.\n\nThis module works both in node.js and with [browserify](http://browserify.org/).\n\n[![testling badge](https://ci.testling.com/mikolalysenko/static-kdtree.png)](https://ci.testling.com/mikolalysenko/static-kdtree)\n\n[![build status](https://secure.travis-ci.org/mikolalysenko/static-kdtree.png)](http://travis-ci.org/mikolalysenko/static-kdtree)\n\n# Example\n\n```javascript\n//Import library\nvar createKDTree = require(\"static-kdtree\")\n\n//Create a bunch of points\nvar points = [\n  [0, 1, 100],\n  [-5, 0.11, Math.PI],\n  [0, 10, -13],\n\n  // ...\n\n  [4, 3, 1]\n]\n\n//Create the tree\nvar tree = createKDTree(points)\n\n//Iterate over all points in the bounding box\ntree.range([-1, -1, -1], [10, 1, 2], function(idx) {\n  console.log(\"visit:\", idx)  //idx = index of point in points array\n})\n\n//Can also search in spheres\ntree.rnn([0,0,0], 10, function(idx) {\n  console.log(\"point \" + idx + \" is in sphere at origin with radius=10\")\n})\n\n//Nearest neighbor queries\nconsole.log(\"index of closest point to [0,1,2] is \", tree.nn([0,1,2]))\n\n//And k-nearest neighbor queries\nconsole.log(\"index of 10 closest points to [0,1,2] are \", tree.knn([0,1,2], 10))\n\n//For performance, be sure to delete tree when you are done with it\ntree.dispose()\n```\n\n# Install\n\n```sh\nnpm install static-kdtree\n```\n\n# API\n\n```javascript\nvar createKDTree = require(\"static-kdtree\")\n```\n\nBy convention, let `n` denote the number of points and `d` denote the dimension of the kdtree.\n\n## Constructor\n\n#### `var kdt = createKDTree(points)`\nCreates a kdtree from the given collection of points.\n\n* `points` is either an array of arrays of length `d`, or else an [`ndarray`](https://github.com/mikolalysenko/ndarray) with shape `[n,d]`\n\n**Returns** A kdtree data structure\n\n**Time Complexity** This operation takes O(n log(n))\n\n#### `var kdt = createKDTree.deserialze(data)`\nRestores a serialized kdtree.\n\n* `data` is a JavaScript object as produced by calling `kdt.serialize`\n\n**Returns** A kdtree data structure equivalent to the one which was serialized.\n\n**Time Complexity** `O(n)`\n\n## Properties\n\n#### `kdt.dimension`\nThe dimension of the tree\n\n#### `kdt.length`\nThe number of points in the tree\n\n## Methods\n\n#### `kdt.range(lo, hi, visit)`\nExecutes an orthogonal range query on the kdtree\n\n* `lo` is a lower bound on the range\n* `hi` is an upper bound\n* `visit(idx)` is a visitor function which is called once for every point contained in the range `[lo,hi]`. If `visit(idx)` returns any value `!== undefined`, then termination is halted.\n\n**Returns** The last returned value of `visit`\n\n**Time Complexity** `O(d*n^(1-1/d) + k)`, where `k` is the number of points in the range.\n\n#### `kdt.rnn(point, radius, visit)`\nVisit all points contained in the sphere of radius `r` centered at `point`\n\n* `point` is the center point for the query, represented by a length `d` array\n* `radius` is the radius of the query sphere\n* `visit(idx)` is a function which is called once for every point contained in the ball.  As in the case of `kdt.range`, if `visit(idx)` returns a not undefined value, then iteration is terminated.\n\n**Returns** The last returned value of `visit`\n\n**Time Complexity** `O(n + k)`, where `k` is the number of points in the sphere, though perhaps much less than `n` depending on the distribution of the points.\n\n#### `kdt.nn(point[, maxDistance])`\nReturns the index of the closest point to `point`\n\n* `point` is a query point\n* `maxDistance` is an upper bound on the distance to search for nearest points. Default `Infinity`\n\n**Returns** The index of the closest point in the tree to `point`, or `-1` if the tree is empty.\n\n**Time Complexity** `O(n log(n))` in the worst case, but in practice much faster if the points are uniformly distributed.\n\n#### `kdt.knn(point, k[, maxDistance])`\nReturns a list of the k closest points to point in the tree.\n\n* `point` is the point which is being queried\n* `k` is the number of points to query\n* `maxDistance` bounds the distance of the returned points. Default is `Infinity`\n\n**Returns** A list of indices for the `k` closest points to `point` in the `tree` which are within distance `< maxDistance`.  The indices are ordered by distance to `point`.\n\n**Time Complexity** `O((n + k) log(n + k))`, but may be faster if the points in the tree are uniformly distributed\n\n#### `kdt.serialize()`\nReturns a serializable JSON object encoding the state of the kdtree.  This can be passed to `deserialize()` to restore the kdtree.\n\n#### `kdt.dispose()`\nRelease all resources associated with the kdtree.  This is not necessary, but can reduce garbage collector pressure over time.\n\n**Time Complexity** `O(1)`\n\n# Comparisons\n\nTo test the performance of this module, experiments were performed against two other kdtree libraries ([Ubilabs kdtree](https://github.com/ubilabs/kd-tree-javascript) and [node-kdtree](https://github.com/justinethier/node-kdtree)), as well as a naive brute force algorithm.  Ubilabs kdtree is pure JavaScript, and supports only kNN queries and does not correctly implement rNN queries.  node-kdtree is a wrapper over the native C++ library, [libkdtree](https://code.google.com/p/kdtree/), and only supports rNN and NN queries.  Neither library implements range queries.  These libraries were tested in node.js 0.10.26 and Chrome 34 on a MacBook Pro, Core i7 2.3GHz with 8GB of RAM.  The results from these experiments can be found here:\n\n* [node 0.10.26](https://github.com/mikolalysenko/static-kdtree/blob/master/bench/node-0.10-results.md#results-for-node-01026)\n* [Chrome 34](https://github.com/mikolalysenko/static-kdtree/blob/master/bench/chrome-34-results.md#chrome-34)\n\nAnd the code for these experiments can be found in the bench/ subdirectory of this repository.\n\n## Observations\n\nUp to 1000 points or so brute force searching is the fastest method for answering any query, so for small data sets it is probably better to not use a kdtree or any data structure in the first place.\n\nThe latest version of v8 in Chrome is strictly faster than node.js for all test cases and modules.  Because of native C++ dependencies, node-kdtree cannot run in a browser, but even so the Chrome version of static-kdtree is 2-3x faster.  static-kdtree is also up to an order of magnitude faster than Ubilabs kdtree at all operations, making it by far the best choice in the browser.\n\nIn node.js, the situation is slightly more ambiguous.  node-kdtree has the fastest construction time, and also answers 1-nearest neighbor queries faster.  Both Ubilabs kdtree and static-kdtree take about the same amount of time on nearest neighbors queries.  On all other queries static-kdtree is again strictly faster.  It is unclear why the performance of nearest neighbor queries is slightly slower in node.js, but perhaps it may be related to node.js' v8 engine being several versions behind Chrome.  In future updates this situation may start to look more like Chrome, making static-kdtree likely to be the better option for long term.\n\n# Credits\n(c) 2014 Mikola Lysenko. MIT License\n","maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}],"time":{"modified":"2022-06-27T00:03:31.561Z","created":"2014-04-19T02:21:22.877Z","0.0.0":"2014-04-19T02:21:22.877Z","0.0.1":"2014-04-19T03:52:06.399Z","1.0.0":"2014-04-29T01:14:44.274Z","1.0.1":"2014-05-12T18:09:29.125Z","1.0.2":"2017-12-15T08:08:27.617Z"},"homepage":"https://github.com/mikolalysenko/static-kdtree","keywords":["kdtree","static","pure","javascript","range","orthogonal","bounding","box","point","sphere","query","nearest","neighbor","knn","nn","rnn","searching","closest","query"],"repository":{"type":"git","url":"git://github.com/mikolalysenko/static-kdtree.git"},"author":{"name":"Mikola Lysenko"},"bugs":{"url":"https://github.com/mikolalysenko/static-kdtree/issues"},"license":"MIT","readmeFilename":"README.md","users":{"ptx":true,"dschwertfeger":true,"vorg":true,"vbarbarosh":true,"ja.superior":true}}