{"_id":"@b3gm/prune-juice","_rev":"4-a64ff13b13f86e200abd115e8963610e","name":"@b3gm/prune-juice","dist-tags":{"latest":"0.0.2"},"versions":{"0.0.1":{"name":"@b3gm/prune-juice","version":"0.0.1","description":"Implementation of sweep and prune","main":"dist/index.js","types":"dist/index.d.ts","scripts":{"build-test":"npx tsc && npx browserify dist/prunejuice-test.js -o dist/prunejuice-test.bundle.js","test":"npx jest","prepublishOnly":"rm -rf dist && npx tsc"},"repository":{"type":"git","url":"git+https://github.com/b3gm/prune-juice.git"},"keywords":["collision_detection","sweep_and_prune"],"author":{"name":"b3gm"},"license":"MIT","bugs":{"url":"https://github.com/b3gm/prune-juice/issues"},"homepage":"https://github.com/b3gm/prune-juice#readme","jest":{"moduleFileExtensions":["ts","js","tsx"],"transform":{"\\.(ts|tsx)$":"ts-jest"},"testRegex":".*\\.test\\.(ts)$","collectCoverage":true},"devDependencies":{"@types/jest":"^24.9.1","browserify":"^16.5.0","jest":"^24.9.0","ts-jest":"^24.3.0","typescript":"^3.8.3"},"gitHead":"5ee8cefdd416196c5ae690f2514a1d80242d9436","_id":"@b3gm/prune-juice@0.0.1","_nodeVersion":"12.16.1","_npmVersion":"6.13.4","dist":{"integrity":"sha512-7cjcjErMzGm8TGW7xrUMYPFKNKhjJVRMtpYPatNOs4/iG7cccvNErNrmssW5Epq4o+5neqHigfhjWMR6bQ04Qw==","shasum":"40858c30ae95c323a45bca406b18cb22ec649668","tarball":"https://registry.npmjs.org/@b3gm/prune-juice/-/prune-juice-0.0.1.tgz","fileCount":62,"unpackedSize":75097,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.4\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJef1xrCRA9TVsSAnZWagAAAEYQAI1uzJhLubc1l9gvIgwb\nnLi6cmU05ZopvKN0GOiNvM525zdU8xXOQjMjKwgH1KB/bo/SLqaP37CExWcQ\nUj+DjgUst7zTD+2Zz9G8Mips3msa3t1WhPkPCvj+8XhF3BJtXbrbZkGCDgoH\n0ldoQ8jx3xMEkR9LUHgpw9iyYbAWYnifs/L/dDDiBDhhT5obfh+mpqeznG9x\nFC2hrasWRToJIDvg1RAuAW2a0G3/1hNnA/lXmxaRvkjRvl8s614ukkltZJP5\nzqSUX58eaOMw//i/rwKE6IOk9OxGv4mKG3wOjJlV8eNtCebRikbd+oV7uoJo\npnafsfrFsRdtEbVh9K5ZJkoLIJ10sfpVD+Zpi4I1R4TWdB5zU3pq2dryY3Ns\nH52dAI3qxh+sfZmAFA4lB6BkJCFHqvX+UWuha+YsbZlv3QhEvq5rnUKhlnT/\nonV7s5V5e43QI0Zl320Z+W+6oXfe0vgUIb3AN43AOH9+1Y+66cwF/X0g+OJu\njjQpO/trbHb75uzL/xXxblUp6QpnhHj58KZcsQIbmubbC2a3TwfBVC7ufT+Y\nHOz1HJsAU8j216XXOJbOzWkxRSGj1NZoG+InRdcqlOFF66cf4mrZPwT9d/yT\nz5gZsR1RmYbMmpB5kREh/OSiSNasl8UMiR60hpSFqj+go2wVUfHz59xSe7BS\nYcO5\r\n=k6x0\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQDGOpZixgp9B/y/2MTGq9DUY/+VEC4kJOdERwAUn+gPrAIgUBThoKjDOL0TLHy94hoaOYsdEFmcPa6I2PIDKG9oDGs="}]},"maintainers":[{"name":"b3gm","email":"b3gmde@gmail.com"}],"_npmUser":{"name":"b3gm","email":"b3gmde@gmail.com"},"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/prune-juice_0.0.1_1585405035530_0.8396679131958116"},"_hasShrinkwrap":false},"0.0.2":{"name":"@b3gm/prune-juice","version":"0.0.2","description":"Implementation of sweep and prune","main":"dist/index.js","types":"dist/index.d.ts","scripts":{"build-test":"npx tsc && npx browserify dist/prunejuice-test.js -o dist/prunejuice-test.bundle.js","test":"npx jest","prepublishOnly":"rm -rf dist && npx tsc"},"repository":{"type":"git","url":"git+https://github.com/b3gm/prune-juice.git"},"keywords":["collision_detection","sweep_and_prune"],"author":{"name":"b3gm"},"license":"MIT","bugs":{"url":"https://github.com/b3gm/prune-juice/issues"},"homepage":"https://github.com/b3gm/prune-juice#readme","jest":{"moduleFileExtensions":["ts","js","tsx"],"transform":{"\\.(ts|tsx)$":"ts-jest"},"testRegex":".*\\.test\\.(ts)$","collectCoverage":true},"devDependencies":{"@types/jest":"^24.9.1","browserify":"^16.5.0","jest":"^24.9.0","ts-jest":"^24.3.0","typescript":"^3.8.3"},"gitHead":"a64923f89d9304da6ea7e073d13bcfcb18ba0527","_id":"@b3gm/prune-juice@0.0.2","_nodeVersion":"12.16.1","_npmVersion":"6.14.4","dist":{"integrity":"sha512-1aiP4Sw72y5UqGOOX+rlW8Jh7crFINIgGs9QED4tKNR4904jVNqLTFpY21m2KBuS4FoCRZQGMnXoGZVIuFjxog==","shasum":"35e9d5a57f2445c65051cc091f03bee716523ebc","tarball":"https://registry.npmjs.org/@b3gm/prune-juice/-/prune-juice-0.0.2.tgz","fileCount":62,"unpackedSize":79012,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.4\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJejPq4CRA9TVsSAnZWagAAxt0P/1Ku2Dmz2tpVadWhq90C\nPX6/G/Gr+h+5x0OEcAgwqqhmLcAQ4mHmZw5tMq6EOmpCOKmt+p0Swou/0p8S\nQMIr4mgsXR4Y/U2VpCiO1srMocHNqG7/X6ii2IfC+ILJco+CDFS4Ihriks5G\nCKWv8v4DUdoOqMAKq98Tx3lnvA/neKAzk5wocI21lQMOnQTTrDIOj/vylBRM\nbo9WVqy0cRyc6nOirvL07v0cLptRr1E3S6d2/rFeQbFdmn7SpokZy9zA1CTW\noXcOe25gS5Fbx2vchlivX64uoCWhdoqcAdvSEu4/BJkQkaQmd7XO0ZCnZT5W\njV18MBytwgyMJkSq4OjBd7Fa4XBP/VPxNM6llnduEJOijKV0i5Unl/exiprb\nsSaa9obp8Csp7ulF/4j1Ku7y1j+VSsqADU5LRn+6cbWtamPgOtfpqmKNB9ck\niMJMGKW9bhruJdFVqRONTO8SRthZcT6q6oAPs11ood+cxLsQXV2Ytpwmw6QJ\nWwxplTUp5a1iUWEkpW2ePefz2aA07WnmE9+irDmmWGebV3uBgY4116abSLQh\nI8BHzCMLPPcMet50LZQto8uKEE8h69qYLYVeKxz+oUO+a78gkFlqMyAoPUVh\nIMTiND24fvigLlAt/kXGUGxJXcNTnKBnzlSVxW0afKqIWqwK9MLbbxXFnBWx\nJy78\r\n=x3e3\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEQCIDilSRQbl+aGoMX8nKo8pDWQN/7UdrufHuSE+e9fphn8AiBlAD/E2fPoGEL1yi2vpUQccCjVjTSboYHkRQA9L2PHnA=="}]},"maintainers":[{"name":"b3gm","email":"b3gmde@gmail.com"}],"_npmUser":{"name":"b3gm","email":"b3gmde@gmail.com"},"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/prune-juice_0.0.2_1586297528446_0.6040970886267947"},"_hasShrinkwrap":false}},"time":{"created":"2020-03-28T14:17:15.299Z","0.0.1":"2020-03-28T14:17:15.659Z","modified":"2022-05-02T11:42:35.444Z","0.0.2":"2020-04-07T22:12:08.558Z"},"maintainers":[{"email":"p.guenther86@gmail.com","name":"pguenther"},{"email":"b3gmde@gmail.com","name":"tmpbigg"}],"description":"Implementation of sweep and prune","homepage":"https://github.com/b3gm/prune-juice#readme","keywords":["collision_detection","sweep_and_prune"],"repository":{"type":"git","url":"git+https://github.com/b3gm/prune-juice.git"},"author":{"name":"b3gm"},"bugs":{"url":"https://github.com/b3gm/prune-juice/issues"},"license":"MIT","readme":"prune-juice\n===========\n\nThis library implements the sweep and prune algorithm for an arbitrary number\nof dimensions.\n\n\nIntroduction\n============\n\nSweep and prune is an algorithm for collision detection between axis *aligned\nbounding boxes* (*AABB*). It has a runtime complexity of `O(d*N)` with `N` being\nthe\nnumber of observed AABBs and `d` being the number of dimensions of the vector\nspace. Even if you're interested in the detection of collisions between more\nintricate objects, sweep and prune can be used as a presolver, to find a list\nof possible collision candidates before filtering those candidate pairs with a\nmore accurate collision detection algorithms.\n\nSweep and prune is best suited, if you're interested in finding all possible\ncolliding pairs in a large set of dynamic AABBs. On the other hand, if you're\nonly interested in the collisions of few dynamic objects with a large set of\nstatic ones, other data structures like R-trees will probably be faster.\n\nBasicUsage\n==========\n\nFor the following examples we will assume that we have a type `MyBox` defined\nlike this:\n\n```typescript\ninterface MyBox {\n    x: number;\n    y: number;\n    width: number;\n    height: number;\n}\n```\n\nFirst an object of type `PruneJuice` has to be constructed. The library makes\nno assumptions about your exact type of AABB. That's why it needs an array of\nso called dimension extractors for construction. A dimension extractor is an\nobject with a getStart and a getEnd method, that takes one of your AABBs and\nreturns its low end and high end coordinates respectively.\n\n```typescript\nimport { PruneJuice } from '@b3gm/prune-juice';\n\nconst pj : PruneJuice<MyBox> = new PruneJuice(\n    [\n        {\n            getStart: (b: MyBox) => b.x,\n            getEnd: (b: MyBox) => b.x + b.width\n        },\n        {\n            getStart: (b: MyBox) => b.y,\n            getEnd: (b: MyBox) => b.y + b.height\n        }\n    ]\n);\n```\n\nNote, that the dimension extractor order corresponds to the order in which\nyour dimensions will be processed. Sweep and Prune works most memory efficient\nif the dimensions in which the AABBs overlap least likely are processed first.\nThink for example of a solar system in which the celestial bodies orbit mostly\nin the `x`-`y` plane of the coordinate system. If we would process the `z` dimension\nfirst, sweep and prune will construct `~N^2` collision candidates, that are then\ngoing to be mostly thrown away again when processing the `x` and `y` dimensions.\n\nAfter that you may register and unregister AABBs, update their positions and\nsizes and check for colliding pairs between them.\n\n```typescript\nmyBoxes.forEach(b => pj.register(b));\n\nfunction loop() {\n    updateBoxes(myBoxes);// move boxes, possibly resize.\n    const candidates: MyBox[][] = pj.getCollisionCandidates();\n    processCollisions(candidates);\n}\n\n// or replace with dedicated game loop:\nsetInterval(loop, 1000.0 / 60.0);\n```\n\nNote however, that adding and removing AABBs from PruneJuice also has O(d*N)\nruntime complexity.\n\nHow does it work\n================\n\nSweep and prune internally keeps a sorted array of the beginning and end markers\nfor the registered AABBs for each dimension between each call to\n`getCollisionCandidates` and resorts them. The key insight here is, that if\neach of the boxes only moves a little bit between each call, this doesn't\ncompletely scramble those internal arrays. That's why a sorting algorithm, that\nworks best on almost sorted arrays like insertion sort, which has linear\nruntime complexity in that case, should be used. After that each of the\ndimensions are being scanned for overlapping bounding boxes. If a pair of\nbounding boxes overlaps in all dimensions, they are being returned as collision\ncandidates.\n\nIf you want to test PruneJuice with a different sorting algorithm, you may\nsupply a custom one as the optional second argument to the PruneJuice \nconstructor. It must have the following interface:\n\n```typescript\ninterface SortFunction {\n    <T>(arr:Array<T>, cmp:(a:T, b:T) => number):void;\n}\n```\n\nSince this function does not return anything, it is expected to modify its\nfirst argument. Sorting should be done according to the second argument\ncomparator.\n","readmeFilename":"README.md"}