{"_id":"slab-decomposition","_rev":"14-d122db36000ceedef94013e9745f9ce5","name":"slab-decomposition","description":"Slab decomposition data structure for 2D vertical ray queries","dist-tags":{"latest":"1.0.3"},"versions":{"0.0.0":{"name":"slab-decomposition","version":"0.0.0","description":"Slab decomposition data structure for 2D vertical ray queries","main":"slabs.js","directories":{"test":"test"},"dependencies":{"binary-search-bounds":"^0.3.1","functional-red-black-tree":"^0.0.0","robust-orientation":"^1.0.0"},"devDependencies":{"tape":"~2.5.0"},"scripts":{"test":"tape test/*.js"},"repository":{"type":"git","url":"git://github.com/mikolalysenko/slab-decomposition.git"},"keywords":["slab","decomposition","ray","query","line","segment","2d"],"author":{"name":"Mikola Lysenko"},"license":"MIT","bugs":{"url":"https://github.com/mikolalysenko/slab-decomposition/issues"},"homepage":"https://github.com/mikolalysenko/slab-decomposition","_id":"slab-decomposition@0.0.0","dist":{"shasum":"f70c52a2a8d482a3d76d3a0d5b81cc68fd3331f4","tarball":"https://registry.npmjs.org/slab-decomposition/-/slab-decomposition-0.0.0.tgz","integrity":"sha512-8u8RNVWCwPHRSFZP+tx3LS5b2nqc9kja4LKGSNEvMilo21i9XCGXeG0FeROBsGneoWw/pqz12re/OO0JW1eK5A==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQCWDO/LDoGxUVsSZ1Y3zGxdZLh0oskIBIbOmmb7YZdu1gIhAKEcew0rcr90vZElhKWvwD3AZNxVbgqNHSA/b3zSsTTk"}]},"_from":".","_npmVersion":"1.3.14","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}]},"1.0.0":{"name":"slab-decomposition","version":"1.0.0","description":"Slab decomposition data structure for 2D vertical ray queries","main":"slabs.js","directories":{"test":"test"},"dependencies":{"binary-search-bounds":"^0.3.1","functional-red-black-tree":"^1.0.0","robust-orientation":"^1.0.1"},"devDependencies":{"tape":"~2.5.0","uniq":"0.0.2"},"scripts":{"test":"tape test/*.js"},"repository":{"type":"git","url":"git://github.com/mikolalysenko/slab-decomposition.git"},"keywords":["slab","decomposition","ray","query","line","segment","2d"],"author":{"name":"Mikola Lysenko"},"license":"MIT","bugs":{"url":"https://github.com/mikolalysenko/slab-decomposition/issues"},"homepage":"https://github.com/mikolalysenko/slab-decomposition","_id":"slab-decomposition@1.0.0","dist":{"shasum":"664bbbc89f6e96ed379f02d828c7e41ce4f208d9","tarball":"https://registry.npmjs.org/slab-decomposition/-/slab-decomposition-1.0.0.tgz","integrity":"sha512-OabU78msCBuPQYUjBKlS7fTiLo+tUsccHdJpSxhb8VY5h8zy4/gDPk0bioXsHDyB95DUv1LBMKggg8P3FH5TVg==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQCjjCl7UEBHTyy/s2Vi5qpq4W0ShkdUSsWjqK1IqC+xLAIhAJAO/UZPvIEumq/nJYsUwle03cCU+j61QRnzKrceSSHH"}]},"_from":".","_npmVersion":"1.4.3","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}]},"1.0.1":{"name":"slab-decomposition","version":"1.0.1","description":"Slab decomposition data structure for 2D vertical ray queries","main":"slabs.js","directories":{"test":"test"},"dependencies":{"binary-search-bounds":"^0.3.1","functional-red-black-tree":"^1.0.0","robust-orientation":"^1.0.1"},"devDependencies":{"tape":"~2.5.0","uniq":"0.0.2"},"scripts":{"test":"tape test/*.js"},"repository":{"type":"git","url":"git://github.com/mikolalysenko/slab-decomposition.git"},"keywords":["slab","decomposition","ray","query","line","segment","2d"],"author":{"name":"Mikola Lysenko"},"license":"MIT","bugs":{"url":"https://github.com/mikolalysenko/slab-decomposition/issues"},"homepage":"https://github.com/mikolalysenko/slab-decomposition","_id":"slab-decomposition@1.0.1","dist":{"shasum":"a9446b6738e59aa58615aff69cd27d255d934a15","tarball":"https://registry.npmjs.org/slab-decomposition/-/slab-decomposition-1.0.1.tgz","integrity":"sha512-ShRcA8BSmknJk5I5Q28XIOw3jrxIILVcQ+WoyQG57mQd4Vg42UEZQFKzeODNvWLaTA6yONN2Prlzb66wBgSECw==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQC2pnkalybKp7KnNNn1vq0KPyhYKExh9eOqhGaVNugeCQIgOqMBD9YtdTbfzYIQXBXWr397tJ8V+awvm/d/lilERMo="}]},"_from":".","_npmVersion":"1.4.3","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}]},"1.0.2":{"name":"slab-decomposition","version":"1.0.2","description":"Slab decomposition data structure for 2D vertical ray queries","main":"slabs.js","directories":{"test":"test"},"dependencies":{"binary-search-bounds":"^1.0.0","functional-red-black-tree":"^1.0.0","robust-orientation":"^1.1.3"},"devDependencies":{"tape":"~2.5.0","uniq":"0.0.2"},"scripts":{"test":"tape test/*.js"},"repository":{"type":"git","url":"git://github.com/mikolalysenko/slab-decomposition.git"},"keywords":["slab","decomposition","ray","query","line","segment","2d"],"author":{"name":"Mikola Lysenko"},"license":"MIT","bugs":{"url":"https://github.com/mikolalysenko/slab-decomposition/issues"},"homepage":"https://github.com/mikolalysenko/slab-decomposition","_id":"slab-decomposition@1.0.2","dist":{"shasum":"1ded56754d408b10739f145103dfc61807f65134","tarball":"https://registry.npmjs.org/slab-decomposition/-/slab-decomposition-1.0.2.tgz","integrity":"sha512-W4WuIt+xCxGtJbs4W/RJioMZubwuMdDXH6A9ybdN4nn3cug+0kR6id3KVsuiJZCLAzBlbKb7XapQbH0uObHfXw==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEQCIGPGhIBWsC59McMwFEC4Sj21YFHeH5j4M9g3RXWqlG6vAiBWWjq4brM0dQpcxXByCHyHhHadOvVHfolNknWgGRZBxQ=="}]},"_from":".","_npmVersion":"1.4.3","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}]},"1.0.3":{"name":"slab-decomposition","version":"1.0.3","description":"Slab decomposition data structure for 2D vertical ray queries","main":"slabs.js","directories":{"test":"test"},"dependencies":{"binary-search-bounds":"^2.0.0","functional-red-black-tree":"^1.0.0","robust-orientation":"^1.1.3"},"devDependencies":{"tape":"~2.5.0","uniq":"0.0.2"},"scripts":{"test":"tape test/*.js"},"repository":{"type":"git","url":"git://github.com/mikolalysenko/slab-decomposition.git"},"keywords":["slab","decomposition","ray","query","line","segment","2d"],"author":{"name":"Mikola Lysenko"},"license":"MIT","bugs":{"url":"https://github.com/mikolalysenko/slab-decomposition/issues"},"homepage":"https://github.com/mikolalysenko/slab-decomposition","gitHead":"4d2fbf5b1314e84dae7770a00618528c54f003ec","_id":"slab-decomposition@1.0.3","_nodeVersion":"14.15.3","_npmVersion":"6.14.10","dist":{"integrity":"sha512-1EfR304JHvX9vYQkUi4AKqN62mLsjk6W45xTk/TxwN8zd3HGwS7PVj9zj0I6fgCZqfGlimDEY+RzzASHn97ZmQ==","shasum":"0345b3d364d78dad3f400cd5c8e0424547d23e7c","tarball":"https://registry.npmjs.org/slab-decomposition/-/slab-decomposition-1.0.3.tgz","fileCount":12,"unpackedSize":21978,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.13\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJg8FkxCRA9TVsSAnZWagAAEpIP/A63SaLmsVULmWMQLTfY\nO3OEpgZBS2pN6Gmpggf3zUOM+j9qeWnAgvuaZbJJb2NQgrzk4jMV6kg58qL9\nZ3F6k9rRrlDGF7/zPa5Y08Q24JN1rU1J9mSegPNFnEOkyOZRUWliRdciMJgs\nY6l9fuQvjAA1aYuXdbaaxwh47zIvIR7FyZw1+MKrzwlO8rw6q1B/xVcqcIt9\nBxhWeJnUVrE/XoYx+pJ5R0Waa7KoRIyT18uBaSr4uvV83cplT768T4bNJVwV\nBZTA9+zJOftv8KALfWyVTCyZkO5v6QBbM6AgvpHpkFohOZ13ylri6bJx4FJz\nGg4xV03lZg3AG05dSTzbdYm7xYWnFnytYD+2+tD2sHHPk3d0gXXJozehNORA\nSvV3MPzrJRpuZ3fVEAZ3KsjR62obqePUpH2ewzsYnv2NRx67eI4f0822T9+9\nejZlR/Zm54Yu/sVtK87QcodALN8h20+b2tsOpR9T+8bMa2EawUEcPHmKY3GQ\n5Un+hUVbnuZ9IBttGBrC6NWfRMoreE7Th7x5FGR+PCti4EkR92FnK5Amnh+O\nkPeXQKQs8tEZ4vj5uWG4K/YMRCUtJrujy3di91cBsoJgwJ+j1FMnNIeRZngc\nrpnQAgLnuXOrxjIRS8Zw5GAWLW16CjsA7sozd7CsCm7vQcTuRxTPqDyVAugx\noMkb\r\n=Mgh2\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEQCIA0ROU8C6YwghCsISi6yWIN0WxFL6gB69zVSPEd3k2weAiAucgb1sJcGvF7Pl5nK5FTQe4TtvZyTUEH9l4BX2RvwQQ=="}]},"_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/slab-decomposition_1.0.3_1626364209725_0.6475553118316735"},"_hasShrinkwrap":false}},"readme":"slab-decomposition\n==================\nGiven a collection of line segments, constructs a slab decomposition for the purpose of point location queries. This implementation uses a functional red-black tree to store the slabs, requires O(n log(n)) space and answers vertical ray queries in O(log(n)) time.\n\n# Example\n\n```javascript\nvar makeSlab = require(\"slab-decomposition\")\nvar slabs = makeSlab([\n  [[0, 0], [10, 10]],\n  [[10,10], [20, 0]],\n  [[5, 5], [20, 0]]\n])\n\nfor(var i=-10; i<10; ++i) {\n  console.log(slabs.castUp([i, -1]))\n}\n```\n\n# Install\n\n```\nnpm install slab-decomposition\n```\n\n# API\n\n## Constructor\n\n### `var slabs = require(\"slab-decomposition\")(segments)`\nConstructs a slab decomposition from the segments\n\n* `segments` is a collection of line segments which only overlap at their end points\n\n**Returns** A slab decomposition data structure\n\n## Methods\n\n### `slabs.castUp(point)`\nCasts a vertical ray from `point` going upward along `[0,1]`.  Returns the index of the first segment hit.\n\n* `point` is the base point of the ray\n\n**Returns** The index of the first segment hit by point, otherwise -1 if no segment intersects the ray.\n\n# Credits\n(c) 2014 Mikola Lysenko. MIT License","maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}],"time":{"modified":"2022-06-26T20:44:58.541Z","created":"2014-03-01T19:00:04.256Z","0.0.0":"2014-03-01T19:00:05.286Z","1.0.0":"2014-03-30T05:27:13.247Z","1.0.1":"2014-03-30T14:39:19.830Z","1.0.2":"2014-09-19T18:52:41.509Z","1.0.3":"2021-07-15T15:50:09.868Z"},"readmeFilename":"README.md","homepage":"https://github.com/mikolalysenko/slab-decomposition","keywords":["slab","decomposition","ray","query","line","segment","2d"],"repository":{"type":"git","url":"git://github.com/mikolalysenko/slab-decomposition.git"},"author":{"name":"Mikola Lysenko"},"bugs":{"url":"https://github.com/mikolalysenko/slab-decomposition/issues"},"license":"MIT"}