{"_id":"box-intersect","_rev":"9-def8d8c521bcf73fa9d00c3fbc7676cd","name":"box-intersect","description":"Any dimensional box intersection","dist-tags":{"latest":"1.0.2"},"versions":{"1.0.0":{"name":"box-intersect","version":"1.0.0","description":"Any dimensional box intersection","main":"index.js","directories":{"test":"test"},"scripts":{"test":"tape test/*.js"},"repository":{"type":"git","url":"https://github.com/mikolalysenko/box-intersect.git"},"keywords":["box","intersection","collision","detection","aabb","2d","3d"],"author":{"name":"Mikola Lysenko"},"license":"MIT","bugs":{"url":"https://github.com/mikolalysenko/box-intersect/issues"},"homepage":"https://github.com/mikolalysenko/box-intersect","devDependencies":{"array-shuffle":"^1.0.0","dup":"^1.0.0","guarded-array":"^1.0.0","iota-array":"^1.0.0","tape":"^3.4.0","uniq":"^1.0.1"},"dependencies":{"bit-twiddle":"^1.0.2","typedarray-pool":"^1.1.0"},"gitHead":"32783ea3f5ad0e101b30a4fd39efc5b4f6227763","_id":"box-intersect@1.0.0","_shasum":"ddebdf6feaff3b886deb31c2ae97950a29a9126c","_from":".","_npmVersion":"2.1.4","_nodeVersion":"0.10.26","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}],"dist":{"shasum":"ddebdf6feaff3b886deb31c2ae97950a29a9126c","tarball":"https://registry.npmjs.org/box-intersect/-/box-intersect-1.0.0.tgz","integrity":"sha512-e+/E7aSWb157x/LeD1ZjWcCu7UTKWJpjXi+ESlrOc4eV+j5+BnaFO+0uiZ8dgV+HBWqzh5I4uW0vWi/cQvvI+Q==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQCg6vJwBDrlcTLMEL8NVcWj+GLQvXheGdMPOw9999g8rgIhALduRZ3pnxpxqjIWotdggIE+OUIK9rrJg7mcAFMaL+Lj"}]}},"1.0.1":{"name":"box-intersect","version":"1.0.1","description":"Any dimensional box intersection","main":"index.js","directories":{"test":"test"},"scripts":{"test":"tape test/*.js"},"repository":{"type":"git","url":"https://github.com/mikolalysenko/box-intersect.git"},"keywords":["box","intersection","collision","detection","aabb","2d","3d"],"author":{"name":"Mikola Lysenko"},"license":"MIT","bugs":{"url":"https://github.com/mikolalysenko/box-intersect/issues"},"homepage":"https://github.com/mikolalysenko/box-intersect","devDependencies":{"array-shuffle":"^1.0.0","dup":"^1.0.0","guarded-array":"^1.0.0","iota-array":"^1.0.0","tape":"^3.4.0","uniq":"^1.0.1"},"dependencies":{"bit-twiddle":"^1.0.2","typedarray-pool":"^1.1.0"},"gitHead":"b59aebbc4bdfc7cf4d35266bd958ee740f6b7135","_id":"box-intersect@1.0.1","_shasum":"b728a59e3f1a3c73c224933c2660b927aa137902","_from":".","_npmVersion":"2.1.4","_nodeVersion":"0.10.26","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}],"dist":{"shasum":"b728a59e3f1a3c73c224933c2660b927aa137902","tarball":"https://registry.npmjs.org/box-intersect/-/box-intersect-1.0.1.tgz","integrity":"sha512-VIvkRmmYL5sqIyXscyCuDa5gHZKgxqLf5N4SdUZ5WL4seYisSxXQMdXWxM5mraNQd0SLZHJ3IPrQa8HZ6rt2uQ==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQCXnHcZfRUNINsgckHsnLRJoRlHRev21oJvpoihZD9t+wIgSROnK0Wm2CZzQREac2QumuXnGydlYaWGPSkQnlV4ksg="}]}},"1.0.2":{"name":"box-intersect","version":"1.0.2","description":"Any dimensional box intersection","main":"index.js","directories":{"test":"test"},"scripts":{"test":"tape test/*.js"},"repository":{"type":"git","url":"git+https://github.com/mikolalysenko/box-intersect.git"},"keywords":["box","intersection","collision","detection","aabb","2d","3d"],"author":{"name":"Mikola Lysenko"},"license":"MIT","bugs":{"url":"https://github.com/mikolalysenko/box-intersect/issues"},"homepage":"https://github.com/mikolalysenko/box-intersect","devDependencies":{"array-shuffle":"^1.0.0","dup":"^1.0.0","guarded-array":"^1.0.0","iota-array":"^1.0.0","tape":"^3.4.0","uniq":"^1.0.1"},"dependencies":{"bit-twiddle":"^1.0.2","typedarray-pool":"^1.1.0"},"gitHead":"7e6770bab1fb90217a92eec4b8e0f4c293a71801","_id":"box-intersect@1.0.2","_npmVersion":"5.6.0","_nodeVersion":"8.11.1","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"dist":{"integrity":"sha512-yJeMwlmFPG1gIa7Rs/cGXeI6iOj6Qz5MG5PE61xLKpElUGzmJ4abm+qsLpzxKJFpsSDq742BQEocr8dI2t8Nxw==","shasum":"4693ad63e828868d0654b114e09364d6281f3fbd","tarball":"https://registry.npmjs.org/box-intersect/-/box-intersect-1.0.2.tgz","fileCount":10,"unpackedSize":46104,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.4\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJcUtnNCRA9TVsSAnZWagAA03AP/A+HvDE9xf7FEyjM1D32\n3odCcoMnWnBkhUSe9nEGoic00ZzxO5pKuW39vEVKy7XXe8jHNkIjgvvA2vo7\nEa9GpCzJLc9hfOQg2KLWxHhm5JwQenxAPbu976/CWatAxmnWV4VWjrSed3oH\npEFl5Ql7rFCYnFDIuWojWn+IXalCZQMnfMNK48RdHZHUlJWotZaC9fi3nHJW\nyLM4FGmdwTHGhVgd1n3+KBATGa2YTouAuqV24g5o7KLl17AqbVqSoQg3po+O\ni9or/OncD14h41sFrVLMUw+oOI1cX26vEsicvAqgcJPHguXAF52R4PZxUDVW\nr71EWgEfonDCcLKv4M7XJggx2dbLPA6FNq6vfyGUmcOM/otocDyU/bhWZ51m\nTGD698rVj5Y8gz3g9Q73jl5GWCW5vOwu5wl3utw6KDN6L90jS417jc5V4BsD\n0DYHF2SPg+ZyyRVt5kbKP6l1BsKZNT0P80c5NwnnyBidUASAqPzoayV+OvTO\ngrKBAmOKPdzMnjf0zwaxJ4umOb2pt/Di4a2wu6SrqR+v+rIYsFHSOogkpPh+\njhTQ5a7pXL39CNeZWzMW4yCo2UkRk7c9MmBQrkjhq7lVal0Gk8TxzApiUMHe\nCmHgvkrirLitfsfBLVV23q+HVKBah86Mn8vNCWvQLbIuJgTqFrrw7GgY6M7v\nQss2\r\n=JGgq\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEQCIF8tAAoZJ2QRctFGqZ7fejk2+psHn0c/XKUjyh/RttagAiAeByX4hz4XUIipblrgvNAfjtP2BIHmuT0LL5tGl0xmcA=="}]},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/box-intersect_1.0.2_1548933581081_0.8767594679486386"},"_hasShrinkwrap":false}},"readme":"box-intersect\n=============\nThis modules finds all intersection in a set of n boxes in d-dimensions, or between a pair of sets with n and m boxes respectively.  The time taken is O((n+m) log^d(n+m)) and the algorithm uses a temporary scratch memory of size O(n+m).  This memory is pooled so that after the first execution no additional memory is allocated.  Some possible applications of this library include:\n\n* Collision detection\n* Polygon clipping\n* Batched box stabbing queries\n* Mesh boolean operations (CSG)\n\nThe algorithm in this package is based on the one described in the following paper:\n\n* [A. Zomorodian, H. Edelsbrunner. (2000) \"Software for fast box intersections\" In proceedings of SoCG](http://pub.ist.ac.at/~edels/Papers/2002-J-01-FastBoxIntersection.pdf)\n\nA detailed experimental analysis of the performance of this module as well as comparisons with other libraries for box intersection can be found in the following repository: \n\n* [The Great JavaScript Box Intersection Benchmark](https://github.com/mikolalysenko/box-intersect-benchmark)\n\nFor more information on this problem, please see the following series of blog posts:\n\n* [Collision detection (part 1)](http://0fps.net/2015/01/07/collision-detection-part-1/)\n* [Collision detection (part 2)](http://0fps.net/2015/01/18/collision-detection-part-2/)\n* [Collision detection (part 3)](http://0fps.net/2015/01/23/collision-detection-part-3-benchmarks/)\n\n# Example\n\n### Detecting overlaps in a set of boxes\n\nHere is how to detect all pairs of overlapping boxes in a single set of boxes:\n\n```javascript\nvar boxIntersect = require('box-intersect')\n\n//Boxes are listed as flattened 2*d length arrays\nvar boxes = [\n  [1, 1, 2, 2],   //Interpretation: [minX, minY, maxX, maxY]\n  [0, -1, 3, 2],\n  [2, 1, 4, 5],\n  [0.5, 3, 1, 10]\n]\n\n//Default behavior reports list of intersections\nconsole.log('overlaps:', boxIntersect(boxes))\n\n//Note:  Boxes are closed\n\n//Can also use a visitor to report all crossings\nvar result = boxIntersect(boxes, function(i,j) {\n  console.log('overlap:', boxes[i], boxes[j])\n\n  //Can early out by returning any value\n  if(i === 2 || j === 2) {\n    return 2\n  }\n})\n\nconsole.log('early out result:', result)\n```\n\n#### Output\n\n```\noverlap: [ [ 0, 1 ], [ 0, 2 ], [ 1, 2 ] ]\noverlap: [ 1, 1, 2, 2 ] [ 0, -1, 3, 2 ]\noverlap: [ 1, 1, 2, 2 ] [ 2, 1, 4, 5 ]\nearly out result: 2\n```\n\n### Bipartite intersection\n\nYou can also detect all intersections between two different sets of boxes:\n\n```javascript\nvar boxIntersect = require('box-intersect')\n\n//Again, boxes are given as flattened lists of coordinates\nvar red = [\n  [0, 0, 0, 8, 1, 1],  //Format: [minX, minY, minZ, maxX, maxY, maxZ]\n  [0, 0, 0, 1, 8, 1],\n  [0, 0, 0, 1, 1, 8]\n]\n\nvar blue = [\n  [5, 0, 0, 6, 10, 10],\n  [0, 5, 0, 10, 6, 10],\n  [0, 0, 5, 10, 10, 10]\n]\n\n//Report all crossings\nconsole.log('crossings=', boxIntersect(red, blue))\n\n//Again can use a visitor:\nboxIntersect(red, blue, function(r, b) {\n  console.log('overlap:', red[r], blue[b])\n})\n```\n\n#### Output\n\n```\ncrossings= [ [ 0, 0 ], [ 1, 1 ], [ 2, 2 ] ]\noverlap: [ 0, 0, 0, 8, 1, 1 ] [ 5, 0, 0, 6, 10, 10 ]\noverlap: [ 0, 0, 0, 1, 8, 1 ] [ 0, 5, 0, 10, 6, 10 ]\noverlap: [ 0, 0, 0, 1, 1, 8 ] [ 0, 0, 5, 10, 10, 10 ]\n```\n\n# Install\n\nUsing [npm](https://www.npmjs.org/), just run the following command:\n\n```sh\nnpm install box-intersect\n```\n\nThis module works in any reasonable CommonJS environment, such as browsersify, iojs or node.js.\n\n# API\n\n```javascript\nvar boxIntersect = require('box-intersect')\n```\n\n### `boxIntersect(boxes[, otherBoxes, visit])`\n\nFinds all pairs intersections in a set of boxes.  There are two basic modes of operation for this function:\n\n* `complete` which detects all pairs of intersections within a single set of boxes\n* `bipartite` which detects pairs of intersections between two different sets of boxes\n\nThe parameters to the function are as follows:\n\n* `boxes` is a list of boxes.  Boxes are represented as length 2*d arrays where the first d-components are the lower bound of the box and then the next d components are the upper bound.\n* `otherBoxes` is an optional list of boxes which `boxes` is tested against.  If not specified, then the algorithm will report self intersections in `boxes`\n* `visit(i,j)` is a callback which is called once for each overlapping pair of boxes.  If `visit` returns any value not equal to `undefined`, then the search is terminated immediately and this value is returned.  If `visit` is not specified, then a list of intersecting pairs is returned.\n\n**Returns** If `visit` was specified, then the last returned value of `visit`.  Otherwise an array of pairs of intersecting boxes.\n\n**Note** The boxes are treated as cartesian products of *closed* intervals.  For example, the boxes `[1,1,2,2]` and `[0,0,1,1]` will be reported as intersecting by this module.\n\n# License\n\n(c) 2014 Mikola Lysenko. MIT License","maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}],"time":{"modified":"2022-06-13T05:01:12.412Z","created":"2015-01-20T21:44:11.743Z","1.0.0":"2015-01-20T21:44:11.743Z","1.0.1":"2015-03-01T14:14:20.916Z","1.0.2":"2019-01-31T11:19:41.242Z"},"homepage":"https://github.com/mikolalysenko/box-intersect","keywords":["box","intersection","collision","detection","aabb","2d","3d"],"repository":{"type":"git","url":"git+https://github.com/mikolalysenko/box-intersect.git"},"author":{"name":"Mikola Lysenko"},"bugs":{"url":"https://github.com/mikolalysenko/box-intersect/issues"},"license":"MIT","readmeFilename":"README.md","users":{"craigmorton":true}}