{"_id":"k-dimensional_tree","_rev":"2-041314cf0729093d6eab5476eef9158f","name":"k-dimensional_tree","dist-tags":{"latest":"0.0.2"},"versions":{"0.0.1":{"name":"k-dimensional_tree","version":"0.0.1","description":"kdtree data structure","homepage":"https://github.com/Spagiari/kdtreejs#readme","repository":{"type":"git","url":"git+https://github.com/Spagiari/kdtreejs.git"},"main":"index.js","scripts":{"test":"jest"},"keywords":["kdtree","cluster","geospatial","range searches","nearest neighbor searches","2D","3D"],"author":{"name":"Eduardo Spagiari"},"license":"ISC","devDependencies":{"cz-conventional-changelog":"^3.1.0","eslint":"^6.8.0","eslint-config-airbnb-base":"^14.1.0","eslint-plugin-import":"^2.20.2","@sucrase/jest-plugin":"^2.0.0","eslint-config-prettier":"^6.10.0","eslint-plugin-prettier":"^3.1.2","jest":"^25.1.0","prettier":"^1.19.1","faker":"^4.1.0"},"config":{"commitizen":{"path":"./node_modules/cz-conventional-changelog"}},"gitHead":"b8b1dc1e76cc6943eaa7a20ff3ee3bda29c8ef10","bugs":{"url":"https://github.com/Spagiari/kdtreejs/issues"},"_id":"k-dimensional_tree@0.0.1","_nodeVersion":"10.17.0","_npmVersion":"6.11.3","dist":{"integrity":"sha512-DAYg48DeeherFi243A5P//Ca7oVIef+EOIFEmILdqoMUnparsvZH+kzejSUOHaCoqMlSfYfY9WvBGgoAlO476A==","shasum":"2a721e06cda448629a84c08ccf2c6da45fc81932","tarball":"https://registry.npmjs.org/k-dimensional_tree/-/k-dimensional_tree-0.0.1.tgz","fileCount":16,"unpackedSize":31084,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.4\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJe6AW+CRA9TVsSAnZWagAA8pgP/j7qasGQXWYv3Z2MvThV\na4iRenrSH5FH4Sk53wJ/Idr57gFrARlb/CA3/59J032xaxyZz8qFUY33mDs/\nJCe7rVu8DlgST9Or8N8lBlLyoQpgw177BLTVqefw9H2+VDvairsFwQgjIadY\nGhb/v8oqTDe1NUq/34hef2jSKh9jC9DR0wYV87hUGoN+QxU9felZgLsoYl6c\n2uyrpZ7Xj4d25KW34n2qm/Ta7e6vhm8WgqvpyQPixpS56AgKNAHfUF2z1EyJ\nVKZ91ofiNRhQiSXPLTfsPfGpTXSs9p6z6wcs7Nef4Y1VCmxmUsyTQqVyGZO1\nraHLpiZGdr54qCaws3r6swSmcWb52hdIGusN0CcW0yGuOFOgi2fUhceugueW\n+itrpx4rivhFl1uOEqSky1/hyWwVKFmkGOv9rp8izcfmhvobA3rpKwHIp2wO\noS/6Ab4tONJlgQLl0WGkqIK6xgZ2izf9GN45aV+/UPuK0kESmrHyJx9HE0Nz\nf3uzhHdYOp9wRhYMZdlC+QxD/rZlsndyv3N6yieOUsGSkwg/f9xqI5JGa2JO\nyGlw3Ll8eIMxSkAaHkkC1db3cvZaWXxaNCzra5umuHHXnNOk90N13eHZebT+\nJnUTduMyoTalFdfhAfb69G/3QXlqJ7sEGwD5liCuhg1MRjDwq9Q9uzo7GxVJ\nS9iW\r\n=aV1s\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIHDNlnapUZz1UWPhdY/8pdJmLJuSDEmD41SgJkjhH+FvAiEApAY5jGaabo5MXmj4YUOK9zwdgC6lEq5GIebTQr+khvo="}]},"maintainers":[{"name":"spagiari","email":"e.spagiari@gmail.com"}],"_npmUser":{"name":"spagiari","email":"e.spagiari@gmail.com"},"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/k-dimensional_tree_0.0.1_1592264126334_0.07465612083462125"},"_hasShrinkwrap":false},"0.0.2":{"name":"k-dimensional_tree","version":"0.0.2","description":"kdtree data structure","homepage":"https://github.com/Spagiari/kdtreejs#readme","repository":{"type":"git","url":"git+https://github.com/Spagiari/kdtreejs.git"},"main":"index.js","scripts":{"test":"jest"},"keywords":["kdtree","cluster","geospatial","range searches","nearest neighbor searches","2D","3D"],"author":{"name":"Eduardo Spagiari"},"license":"ISC","devDependencies":{"cz-conventional-changelog":"^3.1.0","eslint":"^6.8.0","eslint-config-airbnb-base":"^14.1.0","eslint-plugin-import":"^2.20.2","@sucrase/jest-plugin":"^2.0.0","eslint-config-prettier":"^6.10.0","eslint-plugin-prettier":"^3.1.2","jest":"^25.1.0","prettier":"^1.19.1","faker":"^4.1.0"},"config":{"commitizen":{"path":"./node_modules/cz-conventional-changelog"}},"gitHead":"fec12bd69ee6f1d516c79b8ca7fc6312d246bba2","bugs":{"url":"https://github.com/Spagiari/kdtreejs/issues"},"_id":"k-dimensional_tree@0.0.2","_nodeVersion":"10.17.0","_npmVersion":"6.11.3","dist":{"integrity":"sha512-59kPL94M62X5SJbT3YFWqz8fmPrMVIqCpoy1bm/sb7L4XD2taBklMZ4c0xbBhFgqUrinbTNsJZiPVBNhoyo7Lg==","shasum":"14ea5435fb639cdfbb82e4c88afe9fcf443f961b","tarball":"https://registry.npmjs.org/k-dimensional_tree/-/k-dimensional_tree-0.0.2.tgz","fileCount":16,"unpackedSize":31091,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.4\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJe6AcHCRA9TVsSAnZWagAANi8P/2sM7LUOZeBAOF3zfYWZ\nAsO1k68Sa3y2SwqTGMcaGQximgJ3PVTQi9+ylqSZ+5ll54QxboCPMKHOhlbu\n6a80iw7+ojJwdaYSdcR6QGJ2wYRKnuifpx/bjdi//xHULekvCMtZGWGWk32k\n5ZRat7++2nGnvc5YztDSf2L4Ij3lo5L96IpXvscxQIHQR5SW2ZdHUr3nJlMa\nyYo/Gb3nkFTi9ca4IIQC/Mvqbm9MN9jjXEVMJWqW+Dpw9QEHZvmzv/f557B+\nY9PejCr58O21uEAIOEz735t5g1VHxHu0NwXUVSxh354cxfacPBsNFPsrI0Nc\nOc4Efbzfs64gPWNYf6By+M2fvyTydW0Igbc+3rCTfi5WPOGTAgwVOD8Zg5zD\nHqeRmnXU9TzWY+CKvMaPJXucawykfoF41fsllQ3ZXmQmBW8ngOBWCOGg7aXP\n7kILHifaA/TppAgnA9T/vu0lThzBsqimssQtgrM6Ujo2Y0KIaxGFO8EVNdCE\n6lx2WeYAUyCldoyEAVPIV4O5m3FL7NsKiIcIMtW0sUmb2fpjNd0I8osRpBBv\nrEcVtqfx7n5i1pn0oPtnx4oHlrVoc+gQAB3J+ZQ7ylEd1J6Y4X2H/SdYZiGt\n6zycF+NPm93d5McfohNmmvUuFx+X4eSZhK8gthzYtd2Ei3Id0KEbOTq7hmOO\nePHm\r\n=cG4J\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQDoa+3U1yoHS0zWzHvnroxG/z841KOmPp7TPRyzISfL6QIhAK8jz6qylPp73tCtN01JwoddObl2fVTJgVm0a78hrFGy"}]},"maintainers":[{"name":"spagiari","email":"e.spagiari@gmail.com"}],"_npmUser":{"name":"spagiari","email":"e.spagiari@gmail.com"},"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/k-dimensional_tree_0.0.2_1592264454841_0.7589917933634085"},"_hasShrinkwrap":false}},"time":{"created":"2020-06-15T23:35:26.334Z","0.0.1":"2020-06-15T23:35:26.438Z","modified":"2022-05-07T02:35:25.875Z","0.0.2":"2020-06-15T23:40:54.967Z"},"maintainers":[{"name":"spagiari","email":"e.spagiari@gmail.com"}],"description":"kdtree data structure","homepage":"https://github.com/Spagiari/kdtreejs#readme","keywords":["kdtree","cluster","geospatial","range searches","nearest neighbor searches","2D","3D"],"repository":{"type":"git","url":"git+https://github.com/Spagiari/kdtreejs.git"},"author":{"name":"Eduardo Spagiari"},"bugs":{"url":"https://github.com/Spagiari/kdtreejs/issues"},"license":"ISC","readme":"# k-dimensional tree\nImplementation of [k-dimensional tree](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.160.335&rep=rep1&type=pdf) with no dependencies for multi purpose. Common uses are: search in multisemensional spaces (range searches and nearest neighbor searches).\n\n# Introduction\nk-dimensional tree in data structure is a type of binary tree in which each leaf of the tree represents a point in a space of k dimensions.\n\nThis structure allows for very useful kinds of operations with an interesting computational cost. For instance, finding the post office closest to a certain point can be a hard task if the number of post offices is very large. A search for the nearest neighbor in a k-dimensional solves this problem with a computational cost of O (log n) in the average case.\n\n## Usage\n\n```bash\n$ npm i k-dimensional_tree\n```\n\n```javascript\nconst {KdTree, Point, Rect} = require('k-dimensional_tree');\n\n// makes a KdTree for two dimensions\nconst kdt = new KdTree(2);\n\nkdt.insert(new Point([0.5, 0.3]));\nkdt.insert(new Point([0.4, 0.01]));\n\nconsole.log(kdt.nearest(new Point([0.01, 2])));\nconsole.log(kdt.range(new Rect(new Point([0.01, 0.1]), new Point([0.5, 0.35]))));\nconsole.log(kdt.pointsInRadius(new Point([0.01, 2]), 0.075));\n\n```\n\n## API\n\n#### insert\nCreate point in tree\n```javascript\nkdt.insert(new Point([0.5, 0.3]));\n```\n#### contains \nCheck if point p exists in k-dimention tree\n```javascript\nkdt.contains(new Point([0.5, 0.3]));\n```\n#### size \nGet numbet of points in k-dimentional tree\n```javascript\nkdt.contains();\n```\n#### isEmpty\nCheck if k-dimention tree is empty\n```javascript\nkdt.isEmpty();\n```\n#### nodes\nGet all points in k-dimentional tree\n```javascript\nkdt.nodes();\n```\n#### nearest\nGet nearest neighbor point of p point\n```javascript\nkdt.nearest(new Point([0.01, 2]));\n```\n#### Range searchs\n\n###### range\nQuery points inside rectangle\n```javascript\nkdt.range(new Rect(new Point([0.01, 0.1], new Point([0.5, 0.35]))));\n```\n###### pointsInRadius\nQuery all points inside radius from a p point\n```javascript\nkdt.pointsInRadius(new Point([0.01, 2]), 0.075)\n```","readmeFilename":"README.md"}