{"_id":"poly-decomp","_rev":"10-f97929b3d9821b4a7fab3eb6b598b931","name":"poly-decomp","description":"Convex decomposition for 2D polygons","dist-tags":{"latest":"0.3.0"},"versions":{"0.1.0":{"name":"poly-decomp","version":"0.1.0","description":"Convex decomposition in 2D","author":{"name":"Stefan Hedman","email":"schteppe@gmail.com","url":"http://steffe.se"},"keywords":["convex","decomposition","polygon","2d"],"engines":{"node":"*"},"main":"./src/index.js","repository":{"type":"git","url":"https://github.com/schteppe/poly-decomp.js.git"},"bugs":{"url":"https://github.com/schteppe/poly-decomp.js/issues"},"licenses":[{"type":"MIT"}],"devDependencies":{},"dependencies":{"grunt":"~0.4.0","grunt-contrib-uglify":"~0.4.0","grunt-browserify":"~2.0.8","browserify":"~3.44.2"},"homepage":"https://github.com/schteppe/poly-decomp.js","_id":"poly-decomp@0.1.0","dist":{"shasum":"bded53573e6648e11fa1cfa8d0198ace2fdf9d77","tarball":"https://registry.npmjs.org/poly-decomp/-/poly-decomp-0.1.0.tgz","integrity":"sha512-KTmBEXl1fFeiCUyd+6KkkXT7uKZtLRaiHpOKwVwUuI2bBHmBmG1p+IM+Y0qi5gHL3D7ZHKQPXCadYu4hHpyjjA==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQCgYET68SLO0+ISUJ2HichPqd5rRnvcVQIxzodkBZMpfQIhAPWvDIz8UG0/UCtQ55lwtgKNydwhPPkItVr/4BWhYyEk"}]},"_from":".","_npmVersion":"1.4.3","_npmUser":{"name":"schteppe","email":"schteppe@gmail.com"},"maintainers":[{"name":"schteppe","email":"schteppe@gmail.com"}],"directories":{}},"0.1.1":{"name":"poly-decomp","version":"0.1.1","description":"Convex decomposition in 2D","author":{"name":"Stefan Hedman","email":"schteppe@gmail.com","url":"http://steffe.se"},"keywords":["convex","decomposition","polygon","2d"],"engines":{"node":"*"},"main":"./src/index.js","repository":{"type":"git","url":"git+https://github.com/schteppe/poly-decomp.js.git"},"bugs":{"url":"https://github.com/schteppe/poly-decomp.js/issues"},"licenses":[{"type":"MIT"}],"dependencies":{},"devDependencies":{"grunt":"~0.4.0","grunt-contrib-uglify":"~0.4.0","grunt-browserify":"~2.0.8","browserify":"~3.44.2"},"gitHead":"c60d5f5129b419c35c276cf26b479b0456412ee2","homepage":"https://github.com/schteppe/poly-decomp.js#readme","_id":"poly-decomp@0.1.1","scripts":{},"_shasum":"9f68c4fa558663791c9ba4c2df7283f3096c23c9","_from":".","_npmVersion":"2.14.7","_nodeVersion":"4.2.2","_npmUser":{"name":"schteppe","email":"schteppe@gmail.com"},"maintainers":[{"name":"schteppe","email":"schteppe@gmail.com"}],"dist":{"shasum":"9f68c4fa558663791c9ba4c2df7283f3096c23c9","tarball":"https://registry.npmjs.org/poly-decomp/-/poly-decomp-0.1.1.tgz","integrity":"sha512-clSDtuC48FR2PL2z/+VIRhfnxC7776GlJgDNAh1ZIqYOiaGqrINB+xGIWQypLgpz6Z/Ht/w7rTFEGFRNuSPOuA==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQCeLbQHy7eAZFpMID1/KwcmVmrlEigGx8GK0Fxy0JQZIQIgCmXxblMY+r38tZlUIH/9H4ndxTff3qCTAUsm/bIceJs="}]},"directories":{}},"0.2.0":{"name":"poly-decomp","version":"0.2.0","description":"Convex decomposition for 2D polygons","author":{"name":"Stefan Hedman","email":"schteppe@gmail.com","url":"http://steffe.se"},"keywords":["convex","decomposition","polygon","2d"],"engines":{"node":"*"},"main":"./src/index.js","repository":{"type":"git","url":"git+https://github.com/schteppe/poly-decomp.js.git"},"bugs":{"url":"https://github.com/schteppe/poly-decomp.js/issues"},"license":"MIT","dependencies":{},"devDependencies":{"browserify":"^3.44.2","grunt":"^1.0.1","grunt-browserify":"^2.0.8","grunt-contrib-nodeunit":"^1.0.0","grunt-contrib-uglify":"^0.4.1","nodeunit":"^0.9.1"},"gitHead":"7009273dd4d031aa32ee0e6ec1c8a4511dd2c393","homepage":"https://github.com/schteppe/poly-decomp.js#readme","_id":"poly-decomp@0.2.0","scripts":{},"_shasum":"df3e6718c9ca76c4bfe7442a956edf9e243d6a96","_from":".","_npmVersion":"3.10.7","_nodeVersion":"4.1.1","_npmUser":{"name":"schteppe","email":"schteppe@gmail.com"},"dist":{"shasum":"df3e6718c9ca76c4bfe7442a956edf9e243d6a96","tarball":"https://registry.npmjs.org/poly-decomp/-/poly-decomp-0.2.0.tgz","integrity":"sha512-iwpWGGg7HNKZSXG2Cu+Pd/jT7gGd7Bdk28aHzf1ZoVMSbGhLJTDzbA+jQYJ+/RfbMKdRwwL9CCIV/RpEE4zSmQ==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIEW7MSqQkxGWa2VbIkC8CklEYDUsmtqS2jMw3UkeT2IEAiEA0y3Ok+BwdfjTvHvE3R5TDUfyuc0V47aLjAOfwYkwlv4="}]},"maintainers":[{"name":"schteppe","email":"schteppe@gmail.com"}],"_npmOperationalInternal":{"host":"packages-16-east.internal.npmjs.com","tmp":"tmp/poly-decomp-0.2.0.tgz_1471510035864_0.6386044370010495"},"directories":{}},"0.2.1":{"name":"poly-decomp","version":"0.2.1","description":"Convex decomposition for 2D polygons","author":{"name":"Stefan Hedman","email":"schteppe@gmail.com","url":"http://steffe.se"},"keywords":["convex","decomposition","polygon","2d"],"engines":{"node":"*"},"main":"./src/index.js","repository":{"type":"git","url":"git+https://github.com/schteppe/poly-decomp.js.git"},"bugs":{"url":"https://github.com/schteppe/poly-decomp.js/issues"},"license":"MIT","dependencies":{},"devDependencies":{"browserify":"^3.44.2","grunt":"^1.0.1","grunt-browserify":"^2.0.8","grunt-contrib-nodeunit":"^1.0.0","grunt-contrib-uglify":"^0.4.1","nodeunit":"^0.9.1"},"gitHead":"6d388678f21ae9b86b8428afecca0bd857074fd3","homepage":"https://github.com/schteppe/poly-decomp.js#readme","_id":"poly-decomp@0.2.1","scripts":{},"_shasum":"a5cc4088e9e2974070fa1ee23c7e3f2fc5b516d8","_from":".","_npmVersion":"3.10.7","_nodeVersion":"4.1.1","_npmUser":{"name":"schteppe","email":"schteppe@gmail.com"},"dist":{"shasum":"a5cc4088e9e2974070fa1ee23c7e3f2fc5b516d8","tarball":"https://registry.npmjs.org/poly-decomp/-/poly-decomp-0.2.1.tgz","integrity":"sha512-MRT1Povp45G71+YFk/ZoLtB02Fpldv3BLDYa/A82IVVSZ6rAdNKfpeZPw3jkov2bvDxfrAvRfNv/9ixo3V+eRQ==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQDA2d3hyKCDi6sv5wEYtdLV2/Dh5TbObwuigZ4bWC/QKQIgDtgA6Uwno/luPMYU59/abHaLshAAX5oo/DMXjI9btG0="}]},"maintainers":[{"name":"schteppe","email":"schteppe@gmail.com"}],"_npmOperationalInternal":{"host":"packages-16-east.internal.npmjs.com","tmp":"tmp/poly-decomp-0.2.1.tgz_1471945344028_0.01735282875597477"},"directories":{}},"0.3.0":{"name":"poly-decomp","version":"0.3.0","description":"Convex decomposition for 2D polygons","author":{"name":"Stefan Hedman","email":"schteppe@gmail.com","url":"http://steffe.se"},"keywords":["convex","decomposition","polygon","2d"],"engines":{"node":"*"},"main":"./src/index.js","repository":{"type":"git","url":"git+https://github.com/schteppe/poly-decomp.js.git"},"bugs":{"url":"https://github.com/schteppe/poly-decomp.js/issues"},"license":"MIT","dependencies":{},"devDependencies":{"browserify":"^3.44.2","grunt":"^1.0.1","grunt-browserify":"^2.0.8","grunt-contrib-nodeunit":"^1.0.0","grunt-contrib-uglify":"^0.4.1","nodeunit":"^0.9.1"},"gitHead":"fdbd8edf4972a1694333eb12286dcd37d48aeeeb","homepage":"https://github.com/schteppe/poly-decomp.js#readme","_id":"poly-decomp@0.3.0","_npmVersion":"5.6.0","_nodeVersion":"8.10.0","_npmUser":{"name":"schteppe","email":"schteppe@gmail.com"},"dist":{"integrity":"sha512-hWeBxGzPYiybmI4548Fca7Up/0k1qS5+79cVHI9+H33dKya5YNb9hxl0ZnDaDgvrZSuYFBhkCK/HOnqN7gefkQ==","shasum":"aa499289bbc1a4ca2213e966587fa5bffc1ca5f5","tarball":"https://registry.npmjs.org/poly-decomp/-/poly-decomp-0.3.0.tgz","fileCount":12,"unpackedSize":120390,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.4\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJbVumACRA9TVsSAnZWagAATQQQAJWoj0U9UftO5IPgB+Ns\nJSvS8nC1eU9VCdpcIhVjdNLOvSGZn0vIhHfiNz5zjixvygC8aewfGoUL6eUT\n2ktZWenSRWFjhOkBJuTzhvPV53FMGcOaNblITK8t/6sM7JwNw4b0rTCoLtxG\nG4nVf0m0Dtnbrmyu1KYg8LnG2Rc1tTO6ZR3+zw6SNS1B61rD/8sPzjdsqa3P\n2OqnXjILl2pu8ASocn43Z6ycN1+ARQ9nXoekaivNRzerV8AGZew9AHAo3Ztb\nRx1r3CnfThEVcBS04H1r+VzlRJAZTZQzcUWXeeNI56r1/lzQG1iq5BZqBoGW\nvtE1XufQJrAr1/5mEiU6FaJLsJYiXLHDA35rq+r5ntXPeskoQTaC/MR7bjwo\nI5mz8mFHCdCzbQajl4ggSZEfSzsGreKV/S5OkSjmpYaodcKQSQoLXaAnylNf\nfQ+IlH1CCDxFSTvpW/O+fImTtAKXbsgQMIpIYQ7ldHtg2pMOTWCTZpNV/W45\nO8YZFG3/UlzznrQCOId+luOFBAC8ZQasUs/1HQwF/d/cHdp4UspxAaaHv5uC\nSbc5sCcFu6gMdxjc+NQ83wiBjcESWrklMkLXez8dIkLRdQPA5e8wCnKQz86Q\n4aCs4feiC+KxwzPaABwt2Vt6at4WHgIXvJHedxKytoD2iaba4GMJ9GnYmojU\nYmoa\r\n=oFm3\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIFr5saMcgRJiL/HuMTQNNrgDrlGJUlL5MGSFKXQvuFIXAiEAmeRr5Oj70GmriEl5n4xtamSkjbmHpfFi3CbbJ/D09Ug="}]},"maintainers":[{"name":"schteppe","email":"schteppe@gmail.com"}],"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/poly-decomp_0.3.0_1532422528087_0.12521771267698"},"_hasShrinkwrap":false}},"readme":"poly-decomp.js\n==============\n\nLibrary for decomposing a 2D polygon into convex pieces.\n\n![Decomposing a convcave polygon into convex regions](https://cloud.githubusercontent.com/assets/1063152/18008563/edccfe86-6ba8-11e6-9e20-a090c1812c95.gif)\n\n[Launch the demo!](http://schteppe.github.io/poly-decomp.js/)\n\nThe library implements two algorithms, one optimal (but slow) and one less optimal (but fast).\nIt's is a manual port of the C++ library [Poly Decomp](https://mpen.ca/406/bayazit) by [Mark Penner](https://mpen.ca). \n\n### Install\n##### Browser\nDownload [decomp.js](build/decomp.js) or [decomp.min.js](build/decomp.min.js) and include the script in your HTML:\n```html\n<script src=\"decomp.js\" type=\"text/javascript\"></script>\n<!-- or: -->\n<script src=\"decomp.min.js\" type=\"text/javascript\"></script>\n```\n\nThen you can use the ```decomp``` global.\n\n##### Node.js\n```\nnpm install poly-decomp\n```\n\nThen require it like so:\n\n```js\nvar decomp = require('poly-decomp');\n```\n\n### Basic usage\n```js\n// Create a concave polygon\nvar concavePolygon = [\n  [ -1,   1],\n  [ -1,   0],\n  [  1,   0],\n  [  1,   1],\n  [0.5, 0.5]\n];\n\n// Make sure the polygon has counter-clockwise winding. Skip this step if you know it's already counter-clockwise.\ndecomp.makeCCW(concavePolygon);\n\n// Decompose into convex polygons, using the faster algorithm\nvar convexPolygons = decomp.quickDecomp(concavePolygon);\n\n// ==> [  [[1,0],[1,1],[0.5,0.5]],  [[0.5,0.5],[-1,1],[-1,0],[1,0]]  ]\n\n// Decompose using the slow (but optimal) algorithm\nvar convexPolygons = decomp.decomp(concavePolygon);\n\n// ==> [  [[-1,1],[-1,0],[1,0],[0.5,0.5]],  [[1,0],[1,1],[0.5,0.5]]  ]\n```\n\n### Advanced usage\n```js\n// Get user input as an array of points.\nvar polygon = getUserInput();\n\n// Check if the polygon self-intersects\nif(decomp.isSimple(polygon)){\n    \n    // Reverse the polygon to make sure it uses counter-clockwise winding\n    decomp.makeCCW(polygon);\n    \n    // Decompose into convex pieces\n    var convexPolygons = decomp.quickDecomp(polygon);\n    \n    // Draw each point on an HTML5 Canvas context\n    for(var i=0; i<convexPolygons.length; i++){\n        var convexPolygon = convexPolygons[i];\n        \n        ctx.beginPath();\n        var firstPoint = convexPolygon[0];\n        ctx.moveTo(firstPoint[0], firstPoint[1]);\n        \n        for(var j=1; j<convexPolygon.length; j++){\n            var point = convexPolygon[j];\n            var x = point[0];\n            var y = point[1];\n            c.lineTo(x, y);\n        }\n        ctx.closePath();\n        ctx.fill();\n    }\n}\n```\n\n### Documentation\n\n#### quickDecomp(polygon: Array&lt;Point&gt;): Array&lt;Array&lt;Point&gt;&gt;\n\n```js\nvar convexPolygons = decomp.quickDecomp(polygon);\n```\n\nSlices the polygon into convex sub-polygons, using a fast algorithm. Note that the input points objects will be re-used in the result array.\n\n#### decomp(polygon: Array&lt;Point&gt;): Array&lt;Array&lt;Point&gt;&gt;\n\n```js\nvar convexPolygons = decomp.quickDecomp(polygon);\n```\n\nDecomposes the polygon into one or more convex sub-polygons using an optimal algorithm. Note that the input points objects will be re-used in the result array.\n\n#### isSimple(polygon: Array&lt;Point&gt;): boolean\n\n```js\nif(decomp.isSimple(polygon)){\n    // Polygon does not self-intersect - it's safe to decompose.\n    var convexPolygons = decomp.quickDecomp(polygon);\n}\n```\n\nReturns true if any of the line segments in the polygon intersects. Use this to check if the input polygon is OK to decompose.\n\n#### makeCCW(polygon: Array&lt;Point&gt;): void\n\n```js\nconsole.log('Polygon with clockwise winding:', polygon);\ndecomp.makeCCW(polygon);\nconsole.log('Polygon with counter-clockwise winding:', polygon);\n```\n\nReverses the polygon, if its vertices are not ordered counter-clockwise. Note that the input polygon array will be modified in place.\n\n#### removeCollinearPoints(polygon: Array&lt;Point&gt;, thresholdAngle: number): void\n\n```js\nvar before = polygon.length;\ndecomp.removeCollinearPoints(polygon, 0.1);\nvar numRemoved = before - polygon.length;\nconsole.log(numRemoved + ' collinear points could be removed');\n```\n\nRemoves collinear points in the polygon. This means that if three points are placed along the same line, the middle one will be removed. The ```thresholdAngle``` is measured in radians and determines whether the points are collinear or not. Note that the input array will be modified in place.\n\n#### removeDuplicatePoints(polygon: Array&lt;Point&gt;, precision: number): void\n\n```js\nvar polygon = [\n    [0,0],\n    [1,1],\n    [2,2],\n    [0,0]\n];\ndecomp.removeDuplicatePoints(polygon, 0.01);\n\n// polygon is now [[1,1],[2,2],[0,0]]\n```\n\n### Change log\n##### 0.3.0\n* Added `removeDuplicatePoints`.\n* `makeCCW` now returns true if the polygon was changed.\n* Fixed case 5 mentioned [here](https://mpen.ca/406/bayazit) and discussed [here](https://github.com/schteppe/poly-decomp.js/issues/8).\n\n##### 0.2.1\n* Fixed bug in the collinear point removal, after this fix the algorithm is more agressive and more correct.\n\n##### 0.2.0\n* Rewrote the class based API to a minimal array-based one. See docs.\n\n##### 0.1\n* Added method ```Polygon.prototype.removeCollinearPoints```.\n* Added optional parameter ```thresholdAngle``` to ```Point.collinear(a,b,c,thresholdAngle)```.\n\n### Contribute\nMake sure you have git, [Node.js](http://nodejs.org), NPM and [grunt](http://gruntjs.com/) installed.\n```\ngit clone https://github.com/schteppe/poly-decomp.js.git; # Clone the repo\ncd poly-decomp.js;\nnpm install;                                     # Install dependencies\n                                                 # (make changes to source)\ngrunt;                                           # Builds build/decomp.js\n```\nThe most recent commits are currently pushed to the ```master``` branch. Thanks for contributing!\n","maintainers":[{"name":"schteppe","email":"schteppe@gmail.com"}],"time":{"modified":"2022-06-24T06:48:25.319Z","created":"2014-04-27T09:01:31.099Z","0.1.0":"2014-04-27T09:01:31.099Z","0.1.1":"2015-11-21T18:15:13.955Z","0.2.0":"2016-08-18T08:47:16.638Z","0.2.1":"2016-08-23T09:42:26.191Z","0.3.0":"2018-07-24T08:55:28.179Z"},"homepage":"https://github.com/schteppe/poly-decomp.js#readme","keywords":["convex","decomposition","polygon","2d"],"repository":{"type":"git","url":"git+https://github.com/schteppe/poly-decomp.js.git"},"author":{"name":"Stefan Hedman","email":"schteppe@gmail.com","url":"http://steffe.se"},"bugs":{"url":"https://github.com/schteppe/poly-decomp.js/issues"},"readmeFilename":"README.md","license":"MIT","users":{"monsterkodi":true}}