{"_id":"2d-polygon-self-intersections","_rev":"12-625d5b20efbdb81a5bac18238c76f59c","name":"2d-polygon-self-intersections","description":"This library may not be fast, but it is robust. Robust in the fact that it will find all of the self-intersections in a polygon - minus of course shared endpoints.","dist-tags":{"latest":"1.3.1"},"versions":{"1.0.0":{"devDependencies":{"tape":"^4.0.0"},"dependencies":{"exact-segment-intersect":"^1.0.0","robust-estimate-float":"^1.0.0"},"name":"2d-polygon-self-intersections","description":"This library may not be fast, but it is robust. Robust in the fact that it will find all of the self-intersections in a polygon - minus of course shared endpoints.","version":"1.0.0","main":"intersections.js","scripts":{"test":"tape test.js"},"repository":{"type":"git","url":"https://github.com/tmpvar/2d-polygon-self-intersections.git"},"keywords":["2d","polygon","math","intersections","self-intersections","robust"],"author":{"name":"Elijah Insua","email":"tmpvar@gmail.com"},"license":"MIT","bugs":{"url":"https://github.com/tmpvar/2d-polygon-self-intersections/issues"},"homepage":"https://github.com/tmpvar/2d-polygon-self-intersections","gitHead":"bb05848cc1e247221484a1c90bde5bc35b9963e0","_id":"2d-polygon-self-intersections@1.0.0","_shasum":"5fbac63536842963b74417dd50bc8de504b71f0c","_from":".","_npmVersion":"2.7.5","_nodeVersion":"0.10.37","_npmUser":{"name":"tmpvar","email":"tmpvar@gmail.com"},"maintainers":[{"name":"tmpvar","email":"tmpvar@gmail.com"}],"dist":{"shasum":"5fbac63536842963b74417dd50bc8de504b71f0c","tarball":"https://registry.npmjs.org/2d-polygon-self-intersections/-/2d-polygon-self-intersections-1.0.0.tgz","integrity":"sha512-Afs/K7LKgYPQmPzJ11heIUj8rX63HBgmhm3QrUGI7mLFWgiTsYWfTKiWZKcPxjT38lsPbiys9fsoS1i7vg/pyA==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEQCIBQBNekvoIG3MVzvvMODgm8miXzJqNXZvH2uElawN5YlAiAz9ZFXkAt9JHyChPWHUGLqjkl0Ffmg5W+RscTqVmRGLg=="}]}},"1.1.0":{"devDependencies":{"benchmark":"^1.0.0","tape":"^4.0.0"},"dependencies":{"exact-segment-intersect":"^1.0.0","robust-estimate-float":"^1.0.0"},"name":"2d-polygon-self-intersections","description":"This library may not be fast, but it is robust. Robust in the fact that it will find all of the self-intersections in a polygon - minus of course shared endpoints.","version":"1.1.0","main":"intersections.js","scripts":{"test":"tape test.js"},"repository":{"type":"git","url":"https://github.com/tmpvar/2d-polygon-self-intersections.git"},"keywords":["2d","polygon","math","intersections","self-intersections","robust"],"author":{"name":"Elijah Insua","email":"tmpvar@gmail.com"},"license":"MIT","bugs":{"url":"https://github.com/tmpvar/2d-polygon-self-intersections/issues"},"homepage":"https://github.com/tmpvar/2d-polygon-self-intersections","gitHead":"4b603b1cec931b8f7ebfb5c1497d6e6d471065a4","_id":"2d-polygon-self-intersections@1.1.0","_shasum":"94ce896fed2059fe40cbc12fb97bb0214aec8b8a","_from":".","_npmVersion":"2.7.5","_nodeVersion":"0.10.37","_npmUser":{"name":"tmpvar","email":"tmpvar@gmail.com"},"maintainers":[{"name":"tmpvar","email":"tmpvar@gmail.com"}],"dist":{"shasum":"94ce896fed2059fe40cbc12fb97bb0214aec8b8a","tarball":"https://registry.npmjs.org/2d-polygon-self-intersections/-/2d-polygon-self-intersections-1.1.0.tgz","integrity":"sha512-CHCSPWDTxyOwou9tpEBVzOBsPqCngeqvdwkUgsv8vbSTaHbXQkcAH1EuHLTwqbgEQD2fs0cj9XUE1j2QhkGj0A==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEQCIEPi1JCQvzOdTz6CoHURCtISpBrJfkkEt9AjSSbflwB4AiBwaPBcSQeVTjTqcODjEfXG3SyHPxHwRsUX2DRC3XxBHw=="}]}},"1.1.1":{"devDependencies":{"benchmark":"^1.0.0","tape":"^4.0.0"},"dependencies":{"exact-segment-intersect":"^1.0.0","robust-estimate-float":"^1.0.0"},"name":"2d-polygon-self-intersections","description":"This library may not be fast, but it is robust. Robust in the fact that it will find all of the self-intersections in a polygon - minus of course shared endpoints.","version":"1.1.1","main":"intersections.js","scripts":{"test":"tape test.js"},"repository":{"type":"git","url":"https://github.com/tmpvar/2d-polygon-self-intersections.git"},"keywords":["2d","polygon","math","intersections","self-intersections","robust"],"author":{"name":"Elijah Insua","email":"tmpvar@gmail.com"},"license":"MIT","bugs":{"url":"https://github.com/tmpvar/2d-polygon-self-intersections/issues"},"homepage":"https://github.com/tmpvar/2d-polygon-self-intersections","gitHead":"6a3264544ea44754c1e3ae05f8920e0173a6ce01","_id":"2d-polygon-self-intersections@1.1.1","_shasum":"f434b56dea7a606e39d3698b8d46da1badc4b6e3","_from":".","_npmVersion":"2.7.5","_nodeVersion":"0.10.37","_npmUser":{"name":"tmpvar","email":"tmpvar@gmail.com"},"maintainers":[{"name":"tmpvar","email":"tmpvar@gmail.com"}],"dist":{"shasum":"f434b56dea7a606e39d3698b8d46da1badc4b6e3","tarball":"https://registry.npmjs.org/2d-polygon-self-intersections/-/2d-polygon-self-intersections-1.1.1.tgz","integrity":"sha512-zKrwXIVytZXsLQrdmoDhHyvUeZSI5PdJT1soy04ktGK6pLbj5zr6LQYiqJi6T/M08dBDB7T1A2AEnRvKHLvSJA==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQDq9IwytsWG4q4RH0FlkCF6p8q1R0Lf2bCn42g00brsqAIhAL7z/kZETOGUSXzctTO2a1oXh1ZP9mhn+ymYU4dtNoEf"}]}},"1.1.2":{"devDependencies":{"benchmark":"^1.0.0","tape":"^4.0.0"},"dependencies":{"exact-segment-intersect":"^1.0.0","robust-estimate-float":"^1.0.0"},"name":"2d-polygon-self-intersections","description":"This library may not be fast, but it is robust. Robust in the fact that it will find all of the self-intersections in a polygon - minus of course shared endpoints.","version":"1.1.2","main":"intersections.js","scripts":{"test":"tape test.js"},"repository":{"type":"git","url":"https://github.com/tmpvar/2d-polygon-self-intersections.git"},"keywords":["2d","polygon","math","intersections","self-intersections","robust"],"author":{"name":"Elijah Insua","email":"tmpvar@gmail.com"},"license":"MIT","bugs":{"url":"https://github.com/tmpvar/2d-polygon-self-intersections/issues"},"homepage":"https://github.com/tmpvar/2d-polygon-self-intersections","gitHead":"b2571682c8200befa7cc8e0eed0c4291cef4a3ae","_id":"2d-polygon-self-intersections@1.1.2","_shasum":"9ffec8433e2b816be22cd327e40315f6334b6026","_from":".","_npmVersion":"2.7.5","_nodeVersion":"0.10.37","_npmUser":{"name":"tmpvar","email":"tmpvar@gmail.com"},"maintainers":[{"name":"tmpvar","email":"tmpvar@gmail.com"}],"dist":{"shasum":"9ffec8433e2b816be22cd327e40315f6334b6026","tarball":"https://registry.npmjs.org/2d-polygon-self-intersections/-/2d-polygon-self-intersections-1.1.2.tgz","integrity":"sha512-Be4nl7Ahff6tjZEl3vzYT0OlvUvaa0lyANnuuI+k5gk8K/oTR302V1wQ133ztPkzvej+Ddiiek7/2WdKzPZrwA==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQDVBvgzW+htIwO+VuBcJfHB/RK5Bwt76FiljdRls4lFdAIgFcilcIKS7zuXS2CWebGd8NUiYL/OVzvD1SZe0HWQkF4="}]}},"1.2.0":{"devDependencies":{"benchmark":"^1.0.0","tape":"^4.0.0"},"dependencies":{"exact-segment-intersect":"^1.0.0","robust-estimate-float":"^1.0.0"},"name":"2d-polygon-self-intersections","description":"This library may not be fast, but it is robust. Robust in the fact that it will find all of the self-intersections in a polygon - minus of course shared endpoints.","version":"1.2.0","main":"intersections.js","scripts":{"test":"tape test.js"},"repository":{"type":"git","url":"https://github.com/tmpvar/2d-polygon-self-intersections.git"},"keywords":["2d","polygon","math","intersections","self-intersections","robust"],"author":{"name":"Elijah Insua","email":"tmpvar@gmail.com"},"license":"MIT","bugs":{"url":"https://github.com/tmpvar/2d-polygon-self-intersections/issues"},"homepage":"https://github.com/tmpvar/2d-polygon-self-intersections","gitHead":"21dd287e55e8efaad74e1b711c088af8d902712c","_id":"2d-polygon-self-intersections@1.2.0","_shasum":"27c73f62c12eff497ceb8104c9cf4b84dbf86dd9","_from":".","_npmVersion":"2.7.5","_nodeVersion":"0.10.37","_npmUser":{"name":"tmpvar","email":"tmpvar@gmail.com"},"maintainers":[{"name":"tmpvar","email":"tmpvar@gmail.com"}],"dist":{"shasum":"27c73f62c12eff497ceb8104c9cf4b84dbf86dd9","tarball":"https://registry.npmjs.org/2d-polygon-self-intersections/-/2d-polygon-self-intersections-1.2.0.tgz","integrity":"sha512-XFCyI0uOJXa3nCyM30KgyyKqqjRD2xyfTcSyGPA+XRtNpE0C2aTpoP0WCeBBsEwu1oUcuXxCMjyepNscOdSshw==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQDqwYODG/O2rA/RKBZgQQnC7Axx/iY//CYk4avjF1vSFAIgAYTQyYAf/H4D/xePwwsSpWADNf8UAy/1nZv6s+z9we8="}]}},"1.2.1":{"devDependencies":{"benchmark":"^1.0.0","tape":"^4.0.0"},"dependencies":{"exact-segment-intersect":"^1.0.0","robust-estimate-float":"^1.0.0"},"name":"2d-polygon-self-intersections","description":"This library may not be fast, but it is robust. Robust in the fact that it will find all of the self-intersections in a polygon - minus of course shared endpoints.","version":"1.2.1","main":"intersections.js","scripts":{"test":"tape test.js"},"repository":{"type":"git","url":"https://github.com/tmpvar/2d-polygon-self-intersections.git"},"keywords":["2d","polygon","math","intersections","self-intersections","robust"],"author":{"name":"Elijah Insua","email":"tmpvar@gmail.com"},"license":"MIT","bugs":{"url":"https://github.com/tmpvar/2d-polygon-self-intersections/issues"},"homepage":"https://github.com/tmpvar/2d-polygon-self-intersections","gitHead":"dfc563f707b7f6f02f6489fa508b258cbeacb2fb","_id":"2d-polygon-self-intersections@1.2.1","_shasum":"ce3e0139b7fe49da4606fa47953ea8e43a8b4011","_from":".","_npmVersion":"2.7.5","_nodeVersion":"0.10.37","_npmUser":{"name":"tmpvar","email":"tmpvar@gmail.com"},"maintainers":[{"name":"tmpvar","email":"tmpvar@gmail.com"}],"dist":{"shasum":"ce3e0139b7fe49da4606fa47953ea8e43a8b4011","tarball":"https://registry.npmjs.org/2d-polygon-self-intersections/-/2d-polygon-self-intersections-1.2.1.tgz","integrity":"sha512-iiJRS038UPHqpII5gYhpe/5AADCCZP1MdZrL2bIC1QZRyjVzwUtXQX8YbaqxDRMvO3iUZOThs92tYb9LVBpV0g==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEQCIFVzXn0kjwWhrBkWSJikdl1VbmA0pJMggM5nfktVkIj2AiATG6QTsr2pPy6EsDP+v46/65HYjwNMvsZDhdDwhZiW5Q=="}]}},"1.2.2":{"devDependencies":{"benchmark":"^1.0.0","tape":"^4.0.0"},"dependencies":{"exact-segment-intersect":"^1.0.0","robust-estimate-float":"^1.0.0","robust-segment-intersect":"^1.0.1"},"name":"2d-polygon-self-intersections","description":"This library may not be fast, but it is robust. Robust in the fact that it will find all of the self-intersections in a polygon - minus of course shared endpoints.","version":"1.2.2","main":"intersections.js","scripts":{"test":"tape test.js"},"repository":{"type":"git","url":"https://github.com/tmpvar/2d-polygon-self-intersections.git"},"keywords":["2d","polygon","math","intersections","self-intersections","robust"],"author":{"name":"Elijah Insua","email":"tmpvar@gmail.com"},"license":"MIT","bugs":{"url":"https://github.com/tmpvar/2d-polygon-self-intersections/issues"},"homepage":"https://github.com/tmpvar/2d-polygon-self-intersections","gitHead":"78e5ee99600bd6e44b05e6024e8b9cf461fbe60a","_id":"2d-polygon-self-intersections@1.2.2","_shasum":"362eb476cacb250fb63f0aa699d53eab01faf9b7","_from":".","_npmVersion":"2.7.5","_nodeVersion":"0.10.37","_npmUser":{"name":"tmpvar","email":"tmpvar@gmail.com"},"maintainers":[{"name":"tmpvar","email":"tmpvar@gmail.com"}],"dist":{"shasum":"362eb476cacb250fb63f0aa699d53eab01faf9b7","tarball":"https://registry.npmjs.org/2d-polygon-self-intersections/-/2d-polygon-self-intersections-1.2.2.tgz","integrity":"sha512-mxk5gjb7B9SZN2ChGJKRX/nfsQ4YWg2MbIykACxNa1nuROfOw2igLKHAF5/LDcs23JnKPtQ+bZ2CFgCN/jf3FQ==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQC8zkfqBeobPg0bkKzhPVKonjoXXmouGLH7wAIE58+IYAIgKBaqjPDY7N/sNhno8YhOQM2vWNw4CFXW2osWunrYr/Q="}]}},"1.3.1":{"devDependencies":{"benchmark":"^1.0.0","tape":"^4.0.0"},"dependencies":{"exact-segment-intersect":"^2.0.0","robust-estimate-float":"^1.0.0"},"name":"2d-polygon-self-intersections","description":"This library may not be fast, but it is robust. Robust in the fact that it will find all of the self-intersections in a polygon - minus of course shared endpoints.","version":"1.3.1","main":"intersections.js","scripts":{"test":"tape test.js"},"repository":{"type":"git","url":"https://github.com/tmpvar/2d-polygon-self-intersections.git"},"keywords":["2d","polygon","math","intersections","self-intersections","robust"],"author":{"name":"Elijah Insua","email":"tmpvar@gmail.com"},"license":"MIT","bugs":{"url":"https://github.com/tmpvar/2d-polygon-self-intersections/issues"},"homepage":"https://github.com/tmpvar/2d-polygon-self-intersections","gitHead":"43145c3d648d5a0bade53fbb7b7291798f0c8e94","_id":"2d-polygon-self-intersections@1.3.1","_shasum":"a27a5537e761800258a9d4975c6642319a534a88","_from":".","_npmVersion":"2.7.5","_nodeVersion":"0.10.37","_npmUser":{"name":"tmpvar","email":"tmpvar@gmail.com"},"maintainers":[{"name":"tmpvar","email":"tmpvar@gmail.com"}],"dist":{"shasum":"a27a5537e761800258a9d4975c6642319a534a88","tarball":"https://registry.npmjs.org/2d-polygon-self-intersections/-/2d-polygon-self-intersections-1.3.1.tgz","integrity":"sha512-5zBVP8+aN8T88FyZ4SD9WR/5lAASlLKSS6NCZYQR7aHwwHjXtBsF0Gpcq2a3S+jpMLxa+ct1iYWxGNo2kLcz+w==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQCgwpzmZ9Fq86WvzdAiGXQxOPOGLz9z+6vIvQkJ5Y7rrQIhAIaFFJUsuSC8epmUuf1DMAwNsa1wEZcFVi88u2I/tBEe"}]}}},"readme":"# 2d-polygon-self-intersections\n\nfind self-intersections in a 2d polygon\n\nThis library may not be fast, but it is robust. Robust in the fact that it will find all of the self-intersections in a polygon - minus of course shared endpoints.\n\nYou can expect a time complexity of O(n^2)\n\nWhy wouldn't we use [Bentley–Ottmann](http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm)?  We may in the future, but that is going to take some time and having a functional mechanism for detecting self-intersections is far superior to a non-existant one. The api won't have to change for this to happen.\n\n## install\n\n`npm install 2d-polygon-self-intersections`\n\n## use\n\n```javascript\nvar isects = require('2d-polygon-self-intersections');\n\nvar poly = [\n  [0, 0],\n  [10, 0],\n  [0, 10],\n  [10, 10]\n];\n\nvar r = isects(poly);\nconsole.log(r);\n// outputs: [ [ 5, 5 ] ]\n```\n\n### api\n\n__isects__(`polygon`[, `filterFn`])\n\n* `polygon` - an array of 2 component arrays (i.e. a triangle `[[0, 0], [10, 0], [10, 10]]`) or an array of objects: `[{x:0, y:0}, {x:10, y:0}, {x:10, y:10}]`\n* `filterFn` - a filter function called whenever an intersection is found: `filterFn`(`isect`, `start0`, `end0`, `start1`, `end1`, `unique`)\n * `isect` - current intersection (e.g. `[5, 5]`) - mutations in this array get collected\n * `index0` - index of the segment (e.g `1`)\n * `start0` - start of the first segment (e.g `[0, 5]`)\n * `end0` - start of the first segment (e.g `[10, 5]`)\n * `index0` - index of the segment (e.g `3`)\n * `start1` - start of the first segment (e.g `[5, 0]`)\n * `end1` - start of the first segment (e.g `[5, 10]`)\n * `unique` - boolean representing whether or not this intersection point has been seen before\n * __return__ `true` to collect and `false` to discard\n\n__returns__ an empty array if no interesections or an array of 2 component arrays representing the intersection points. \n\n_NOTE_: this library assumes the polygon is closed, so manually adding the start point as the end point has no effect.\n\nAlso note that there are 2 intersections per crossing, this library by default will only report one - all intersections will be unique.  This behavior can be changed with the `filterFn`.\n\n## license\n\n[MIT](LICENSE.txt)\n","maintainers":[{"name":"tmpvar","email":"tmpvar@gmail.com"}],"time":{"modified":"2022-06-12T14:06:53.560Z","created":"2015-05-19T04:16:04.399Z","1.0.0":"2015-05-19T04:16:04.399Z","1.1.0":"2015-05-19T05:18:50.051Z","1.1.1":"2015-05-19T16:56:52.902Z","1.1.2":"2015-05-19T16:57:42.855Z","1.2.0":"2015-05-23T06:15:24.271Z","1.3.0":"2015-05-23T06:33:20.442Z","1.2.1":"2015-05-23T06:42:25.818Z","1.2.2":"2015-05-24T03:11:43.647Z","1.3.1":"2015-05-28T00:20:58.804Z"},"homepage":"https://github.com/tmpvar/2d-polygon-self-intersections","keywords":["2d","polygon","math","intersections","self-intersections","robust"],"repository":{"type":"git","url":"https://github.com/tmpvar/2d-polygon-self-intersections.git"},"author":{"name":"Elijah Insua","email":"tmpvar@gmail.com"},"bugs":{"url":"https://github.com/tmpvar/2d-polygon-self-intersections/issues"},"license":"MIT","readmeFilename":"README.md"}