{"_id":"grid-index","_rev":"402667","name":"grid-index","description":"A 2D spatial index for axis-aligned boxes","dist-tags":{"latest":"1.1.0"},"maintainers":[{"name":"jfirebaugh","email":"john.firebaugh@gmail.com"}],"time":{"modified":"2021-08-04T04:36:47.000Z","created":"2016-03-25T01:38:27.913Z","1.1.0":"2019-01-09T00:40:33.655Z","1.0.0":"2016-07-07T23:15:58.611Z","0.1.0":"2016-03-25T01:38:27.913Z"},"users":{},"repository":{"type":"git","url":"git+https://github.com/mapbox/grid-index.git"},"versions":{"1.1.0":{"name":"grid-index","version":"1.1.0","description":"A 2D spatial index for axis-aligned boxes","main":"grid-index.js","scripts":{"test":"node test/index.js"},"repository":{"type":"git","url":"git+https://github.com/mapbox/grid-index.git"},"license":"ISC","bugs":{"url":"https://github.com/mapbox/grid-index/issues"},"homepage":"https://github.com/mapbox/grid-index#readme","devDependencies":{"tap":"^5.7.0"},"gitHead":"326d635014ee31eda95a46a294e6bb555b90c8ba","_id":"grid-index@1.1.0","_npmVersion":"6.4.1","_nodeVersion":"8.14.0","_npmUser":{"name":"ansis","email":"ansis.brammanis@gmail.com"},"dist":{"shasum":"97f8221edec1026c8377b86446a7c71e79522ea7","size":3947,"noattachment":false,"key":"/grid-index/-/grid-index-1.1.0.tgz","tarball":"http://registry.cnpm.dingdandao.com/grid-index/download/grid-index-1.1.0.tgz"},"maintainers":[{"name":"jfirebaugh","email":"john.firebaugh@gmail.com"}],"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/grid-index_1.1.0_1546994433368_0.17378477411309778"},"_hasShrinkwrap":false,"publish_time":1546994433655,"_cnpm_publish_time":1546994433655},"1.0.0":{"name":"grid-index","version":"1.0.0","description":"A 2D spatial index for axis-aligned boxes","main":"grid-index.js","scripts":{"test":"node test/index.js"},"repository":{"type":"git","url":"git+https://github.com/mapbox/grid-index.git"},"license":"ISC","bugs":{"url":"https://github.com/mapbox/grid-index/issues"},"homepage":"https://github.com/mapbox/grid-index#readme","devDependencies":{"tap":"^5.7.0"},"gitHead":"bf809d6ccf27945890f9333335659cf52b3761e9","_id":"grid-index@1.0.0","_shasum":"ad2c5d54ce5b35437faff1d70a9aeb3d1d261110","_from":".","_npmVersion":"2.15.5","_nodeVersion":"4.4.5","_npmUser":{"name":"lucaswoj","email":"lucas@mapbox.com"},"maintainers":[{"name":"jfirebaugh","email":"john.firebaugh@gmail.com"}],"dist":{"shasum":"ad2c5d54ce5b35437faff1d70a9aeb3d1d261110","size":3752,"noattachment":false,"key":"/grid-index/-/grid-index-1.0.0.tgz","tarball":"http://registry.cnpm.dingdandao.com/grid-index/download/grid-index-1.0.0.tgz"},"_npmOperationalInternal":{"host":"packages-16-east.internal.npmjs.com","tmp":"tmp/grid-index-1.0.0.tgz_1467933356075_0.8242481658235192"},"directories":{},"publish_time":1467933358611,"_cnpm_publish_time":1467933358611,"_hasShrinkwrap":false},"0.1.0":{"name":"grid-index","version":"0.1.0","description":"A 2D spatial index for axis-aligned boxes","main":"grid-index.js","scripts":{"test":"node test/index.js"},"repository":{"type":"git","url":"git+https://github.com/mapbox/grid-index.git"},"license":"ISC","bugs":{"url":"https://github.com/mapbox/grid-index/issues"},"homepage":"https://github.com/mapbox/grid-index#readme","devDependencies":{"tap":"^5.7.0"},"gitHead":"aaa4e8dcf20628fc0a32d364fb5295451d9a9a49","_id":"grid-index@0.1.0","_shasum":"3a585312a969244b4c4d5d99e3a568e65b109543","_from":".","_npmVersion":"2.14.12","_nodeVersion":"4.3.2","_npmUser":{"name":"ansis","email":"ansis.brammanis@gmail.com"},"maintainers":[{"name":"jfirebaugh","email":"john.firebaugh@gmail.com"}],"dist":{"shasum":"3a585312a969244b4c4d5d99e3a568e65b109543","size":4712,"noattachment":false,"key":"/grid-index/-/grid-index-0.1.0.tgz","tarball":"http://registry.cnpm.dingdandao.com/grid-index/download/grid-index-0.1.0.tgz"},"_npmOperationalInternal":{"host":"packages-12-west.internal.npmjs.com","tmp":"tmp/grid-index-0.1.0.tgz_1458869905514_0.5811388816218823"},"directories":{},"publish_time":1458869907913,"_cnpm_publish_time":1458869907913,"_hasShrinkwrap":false}},"readme":"# grid-index\n\nGridIndex is a 2D spatial index that is [transferable](https://developer.mozilla.org/en-US/docs/Web/API/Transferable).\n\nPairs of keys and boxes can be inserted into GridIndex. The grid can then be queried to find all the keys that intersect a given box. The grid can be serialized to an ArrayBuffer so that it can be transferred between WebWorkers.\n\n**You should probably use [rbush](https://github.com/mourner/rbush) instead of GridIndex!** It's easier to use and it's as fast or faster in many cases.\n\nGridIndex can be faster in a specific set of cases:\n- the constructed index needs to be transferred between workers\n- the extent of the features is fixed\n- features are somewhat evenly sized and distributed\n- a high number of insertions relative to the number of queries\n\nGridIndex is used by [mapbox-gl-js](https://github.com/mapbox/mapbox-gl-js) for label collision detection and feature picking.\n\n## Example\n\n```js\nvar GridIndex = require('grid-index');\n\nvar grid = new GridIndex(100, 5, 0);\nvar key1 = 1;\nvar key2 = 2;\nvar key3 = 3;\ngrid.insert(key1, 30, 10, 35, 15);\ngrid.insert(key2, 60, 20, 65, 25);\ngrid.insert(key3, 40, 10, 45, 15);\n\nvar keys = grid.query(0, 0, 100, 13);\n// `keys` is now [key1, key3]\n\nvar arrayBuffer = grid.toArrayBuffer();\n// transfer the ArrayBuffer to a different worker\n\nvar grid2 = new GridIndex(arrayBuffer);\nvar keys2 = grid2.query(0, 0, 100, 13);\n// `keys2` is now [key1, key3]\n```\n\n## API\n\n### `GridIndex(extent, n, padding)`\nCreate a new GridIndex.\n\n- **extent**: The width and height of the square area that needs to be indexed, for example `4096`.\n- **n**: The rows and columns the grid will be split into. `4` would divide the grid into 16 cells.\n- **padding**: The number of extra rows and columns that should be added on each side of the main grid square.\n\n\n### `GridIndex(arrayBuffer)`\nUnserialize a GridIndex.\n\n- **arrayBuffer**: an ArrayBuffer produced by `gridIndex.toArrayBuffer()`.\n\n\n### `gridIndex.insert(key, x1, y1, x2, y2)`\n\nInsert a new key, box pair into the grid.\n\n- **key**: An unsigned 32bit integer.\n- **x1**: The x coordinate of the left edge of the box.\n- **y1**: The y coordinate of the bottom edge of the box.\n- **x2**: The x coordinate of the right edge of the box.\n- **y2**: The y coordinate of the top edge of the box.\n\n\n### `gridIndex.query(key, x1, y1, x2, y2, intersectionTest?)`\n\nFind the keys that intersect with the given box.\n\n- **x1**: The x coordinate of the left edge of the box.\n- **y1**: The y coordinate of the bottom edge of the box.\n- **x2**: The x coordinate of the right edge of the box.\n- **y2**: The y coordinate of the top edge of the box.\n- **intersectionTest**: An optional function that can be used to filter results by bbox. If provided, this function is called for each possible result with four arguments: x1, y1, x2, y2. Return true to include the result in the returned value.\n\n**returns** an array of keys.\n\n\n### `gridIndex.toArrayBuffer()`\n\nSerialize a GridIndex to an ArrayBuffer so that it can be transferred between WebWorkers efficiently.\n\n**returns** an ArrayBuffer that can later be deserialized with `new GridIndex(arrayBuffer)`.\n","_attachments":{},"homepage":"https://github.com/mapbox/grid-index#readme","bugs":{"url":"https://github.com/mapbox/grid-index/issues"},"license":"ISC"}