{"_id":"@desicochrane/delaunay","_rev":"3-5281a36f2f1b5fc1ab8ad90c3e82bdfb","name":"@desicochrane/delaunay","dist-tags":{"latest":"0.1.2"},"versions":{"0.1.0":{"name":"@desicochrane/delaunay","version":"0.1.0","main":"index.js","scripts":{"test":"nyc --reporter=html --reporter=text mocha --require babel-core/register ./tests/**/*.js","prepublish":"babel -o index.js src/Delaunay.js","coverage":"nyc report --reporter=text-lcov | coveralls"},"babel":{"presets":["env"],"plugins":["transform-object-rest-spread"]},"nyc":{"exclude":["tests"]},"devDependencies":{"babel-core":"^6.26.3","babel-plugin-transform-object-rest-spread":"^6.26.0","babel-preset-env":"^1.7.0","chai":"^4.1.2","coveralls":"^3.0.2","mocha":"^5.2.0","nyc":"^13.0.1"},"gitHead":"a42a924cb2eb89453092f62d47c1df071fac4f77","description":"[![Coverage Status](https://coveralls.io/repos/github/desicochrane/delaunay/badge.svg?branch=master)](https://coveralls.io/github/desicochrane/delaunay?branch=master)","_id":"@desicochrane/delaunay@0.1.0","_shasum":"842960c29b188b22ca2300e68399c8f710a3daba","_from":".","_npmVersion":"3.10.10","_nodeVersion":"6.9.5","_npmUser":{"name":"desicochrane","email":"hello@des.io"},"dist":{"shasum":"842960c29b188b22ca2300e68399c8f710a3daba","tarball":"https://registry.npmjs.org/@desicochrane/delaunay/-/delaunay-0.1.0.tgz","integrity":"sha512-DkT8pfjn7ZUrukyyhCR7N6n+SpOSS3IiJheCvIHXCMBfNAZm0UakajAuJBbWnlA08I2CF5DwGJCPJcBpt1VkdA==","fileCount":34,"unpackedSize":407535,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.4\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJbuLqyCRA9TVsSAnZWagAAD7gP+wbAwpMnb1cwhYI6ot5S\ng85rmPoTG/yNyQqr3TeBNAR5v/lZ9nyAMiachXZtUML9R6XRmMdGoSai3zmA\nq7gdNLX8H9INLwxppndV4huvmzYE8fIZng7fko3rReNWGZOwxuBpOLog4/31\nBVsF1QH7CXKr7ZjGcRo5/m9aIzjN+XXFZitEzsnPxHlRzxtff2lDwP9hcK5/\nGt17LocxltrSF8ZuwNPl7RNJjFqzOyVS4SFK9ovvedEXfsslHCSmYhEVTXe/\nmg7TwmnY7gyXSPhH8Vp/KVWtkh4iQWkql9ZhmBB/CmdDtiYc7sSzEZCe7cJI\nHHnnDHWkhqfnvWSJMMUqgg4jiBmTk5deGrhVmKb/yTgiRLCd6SpSNjsqXHjc\nk2Y+WWoDsUGJzallJTGS2eSoV+kF/ieRbfnDt0yiKcdppjOZYxcfoX3bxlmP\nlntCF7FgaZqQiFetO6yrGZeAZpelpY3XVTd1tmtDQ7cjUF4gJMFH1GdmOA6f\nhmqx8jTxZq2bUADHjWuauKVq9glQNTW6EFZZVQhAfhcYjtZ39blNpnu/7FNC\nfBos1fUCHDQ4Ohxff1MZ6sbbthHdEULoYYr3Hg2R0jPspzOcZRt4CvtZRfDI\nZ2Qkeifyt5B4dw6I20Mf3QdGHxOeXSqDOzZZKMVQmyaoJ9XTjmW0paf33khz\nb9Jv\r\n=jC/m\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQD9cGsJLzXjeJ1fwd5Ik5ohnRBqJpIODCPTaYcyy50vtAIhAPbhiQOre1EDMm4M3fqmOYx3hDUTSv/mW5bzlrLD9eLm"}]},"maintainers":[{"name":"desicochrane","email":"hello@des.io"}],"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/delaunay_0.1.0_1538833072898_0.7470839743549689"},"_hasShrinkwrap":false},"0.1.1":{"name":"@desicochrane/delaunay","version":"0.1.1","main":"index.js","scripts":{"test":"nyc --reporter=html --reporter=text mocha --require babel-core/register ./tests/**/*.js","prepublish":"babel -o index.js src/Delaunay.js","coverage":"nyc report --reporter=text-lcov | coveralls"},"babel":{"presets":["env"],"plugins":["transform-object-rest-spread"]},"nyc":{"exclude":["tests"]},"devDependencies":{"babel-core":"^6.26.3","babel-plugin-transform-object-rest-spread":"^6.26.0","babel-preset-env":"^1.7.0","chai":"^4.1.2","coveralls":"^3.0.2","mocha":"^5.2.0","nyc":"^13.0.1"},"gitHead":"d0c1abdd977f362f306e01f528d42b2a69fa9f98","description":"[![Coverage Status](https://coveralls.io/repos/github/desicochrane/delaunay/badge.svg?branch=master)](https://coveralls.io/github/desicochrane/delaunay?branch=master)","_id":"@desicochrane/delaunay@0.1.1","_shasum":"89e8533a4748c92d361bdda984cd288f3564c994","_from":".","_npmVersion":"3.10.10","_nodeVersion":"6.9.5","_npmUser":{"name":"desicochrane","email":"hello@des.io"},"dist":{"shasum":"89e8533a4748c92d361bdda984cd288f3564c994","tarball":"https://registry.npmjs.org/@desicochrane/delaunay/-/delaunay-0.1.1.tgz","integrity":"sha512-WYK+qumDupWUPTNy1NAiGHEd6fd4fUull5OVo642tKswhzdYUKKzHBGQjCzRBcJQUFU1Z+mAaqLXlNfd55BkoA==","fileCount":34,"unpackedSize":407535,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.4\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJbuLu9CRA9TVsSAnZWagAA7XMQAILCTuxHHiCVBbCAU0xq\nOmw4RHRPv5RTu/P7H05n74L1y/zLTnky12xojzm0mAk6QldHJ+qikudWh9/m\neWN5A4eXarjo6XCg44NUb2P/MGW6DqzM/jeE3pchE4+TsNBweT9W/jlIyJKA\nhX6aWJAS5tGfy9Th/+6hayc/Owoa6P2IhoafhNt15iBwCOjtg8PMISV+bvOo\nHL3VPtoSxPOPghYa4djgKrGXTqJfnViBN9NOlOEvKXuSo76Sb4tUwp7czSUv\nWMG8oOai/93M7+ZZ7oRxb8MLgbIwsjszBnoKpzhCbWigEI7tHxhxoyx1D8yX\nd9L8LAbmzexM0g+vJvQ95qh/IMcosqS+tTdWAUnET1xXuOkYzfwuPv9kMyTV\n+nPrM3u4SdKBXtExNhNA6tVpwr8x0imXyqo4E/mX5XfbGTMSxooAtXP8yMFz\nGvQbCvtNu05SnrDjEThNXYSTh4kOZVRldCEvoBkMv6rsZ+yL/5nxwvFPYH8R\nBdXp05mvDbO+ldFwNKIs7YdeLRHmOV27uGYu2Bql/73KCGzd4KeBpFV1PJfk\n6yoJ6Bzl7faashR3mt1ylXROqRiYqH6NujId4R8FO4SfH2aiZ1fyMVz3QfKL\nmjrKMsO2FO0iG/Wc/kMjXaWEdU98e3DV/tu9LMYKk/3aica2sHzl1IuakJxr\nyaeQ\r\n=B164\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQDPSesnSQYhO8Kxzv/oMf3/S258HzDPSGHeJb0Qak3opgIhAPZsJMTAtPFCVvEG2+x3heLPqV+xlYlaDAD55QewXA9d"}]},"maintainers":[{"name":"desicochrane","email":"hello@des.io"}],"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/delaunay_0.1.1_1538833340810_0.657186487583808"},"_hasShrinkwrap":false},"0.1.2":{"name":"@desicochrane/delaunay","version":"0.1.2","main":"index.js","scripts":{"test":"jest","prepublish":"babel -o index.js src/Delaunay.js","coverage":"jest --coverage --coverageReporters=text-lcov | coveralls"},"babel":{"presets":["env"]},"devDependencies":{"@types/jest":"^23.3.3","babel-core":"^6.26.3","babel-jest":"^23.6.0","babel-preset-env":"^1.7.0","coveralls":"^3.0.2","jest":"^23.6.0"},"gitHead":"5404984f4f9bb9f1bc61525ed5e9a79343698093","description":"[![Coverage Status](https://coveralls.io/repos/github/desicochrane/delaunay/badge.svg?branch=master)](https://coveralls.io/github/desicochrane/delaunay?branch=master)","_id":"@desicochrane/delaunay@0.1.2","_shasum":"2e31cb9f0e9e7ccdec9e2795b714e559fac6d13e","_from":".","_npmVersion":"3.10.10","_nodeVersion":"6.9.5","_npmUser":{"name":"desicochrane","email":"hello@des.io"},"dist":{"shasum":"2e31cb9f0e9e7ccdec9e2795b714e559fac6d13e","tarball":"https://registry.npmjs.org/@desicochrane/delaunay/-/delaunay-0.1.2.tgz","integrity":"sha512-m57OPqoKtfGge6GQHPGU2r6nmC7LMey8d+pJUm9chqJw1lcOR0Wp03Lu6Ibu24f2yW7Nqf6In854nrffoMJkfQ==","fileCount":33,"unpackedSize":68824,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.4\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJbubalCRA9TVsSAnZWagAABn0QAKGZkWD8OvlIVWWCOGiy\nwEM+Eq5ff155Nu7GsbdeE0JmMViMgj1A4noof4C5jI3Ja5CqJ8bA/FcH5NKP\nwPHxfN5Lm9oMHEJuJOMBflVhTijCBDbCXWYkBvY7mQmFON6GQe6EFfIP6BmM\nxxAKaZYOuOPb3t/i9bTAOP6kRIJu16Ld8Iq+bm5xrHLq/d9UM/fvtPii1JVR\nQRMPeGfHSVrV740tg091H/stR4G2HOguvWm4yLFdpotVlZE6wYmmBrJwZoCa\n8CQCfavpinu0tqqJtBAsfcXFKWSzMm5RhMTsvWxFhnXzifFr+vFZmYA60SEc\noqWKb0EgnD/4VRyG36GO6Ovmq9iHsD3zOugikuSm/ERBjB3HagfgKVLecY+K\nU/nu3pLTHmQDFvFsbynp73SUOONp/JaPASgcV3TNxXhuBzZmcnt+7cXfFr0u\nGatbVHRpRceyUFOvCF8Y1E5+hTLq22S7wu98Kkt+K1UWHjEdDjDqVLuoT0ll\nMXqqf31jO9sJZVr0KFtRlJN19jXuNCwDF99Im45tcNl7sQur6SGUSrH1o1Kc\nbC2L3gl/go3PGT81Wh4a9XkkJfBW/oTgtL+HrbIt+dJHN9fCMgILUGfxVGmX\n/qVkc4aHsA0P8TXFbv4NtiYnQyb+uRUnoo/WIsRAinB40nCFzD0TuX5AQf9O\nErOs\r\n=zVkF\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQD82xnNu3Z4+L4ej6jArKiL+TJbwhEm45Doer+8Jham6QIgQSvCVJl4XPiYYxG0MVvID/7/BtYUIdPBtfRT3tzjqTI="}]},"maintainers":[{"name":"desicochrane","email":"hello@des.io"}],"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/delaunay_0.1.2_1538897572866_0.39017442498978117"},"_hasShrinkwrap":false}},"time":{"created":"2018-10-06T13:37:52.734Z","0.1.0":"2018-10-06T13:37:53.713Z","modified":"2022-04-05T03:49:41.604Z","0.1.1":"2018-10-06T13:42:20.976Z","0.1.2":"2018-10-07T07:32:53.044Z"},"maintainers":[{"name":"desicochrane","email":"hello@des.io"}],"description":"[![Coverage Status](https://coveralls.io/repos/github/desicochrane/delaunay/badge.svg?branch=master)](https://coveralls.io/github/desicochrane/delaunay?branch=master)","readme":"# Delaunay\n\n[![Coverage Status](https://coveralls.io/repos/github/desicochrane/delaunay/badge.svg?branch=master)](https://coveralls.io/github/desicochrane/delaunay?branch=master)\n\nDependency-free implementation of the divide-and-conquer Delaunay Triangulation algorithm.\n\n# Getting started\n1. `npm i @desicochrane/delaunay`\n1. import and triangulate your point set:\n    ```js\n    import Delaunay, {UniqueEdges} from '@desicochrane/delaunay'\n\n    // define your point set\n    const pts = [ [1,1], [1,2], [3,4], [4,5] ]\n \n    // compute triangulation graph\n    const graph = Delaunay(pts)\n \n   // get unique edges from graph\n   const edges = UniqueEdges(graph)\n   ```\n\n\n# The Algorithm\nThis package takes a divide-and-conquer approach in the same flavor as merge-sort, the basic idea goes something like:\n\n1. Sort the points left to right\n1. Divide the points into halves until point set has size 2 or 3\n1. Triangulate the 2 or 3 point sets manually\n1. Merge the triangulations together\n\n\nA sample code of the main routine would look something like this:\n\n```js\nfunction Delaunay(pts) {\n    // the output will be an adjacency list of edges\n    const edges = {}\n    \n    // pass edges into the recursive procedure\n    delaunay(edges, pts.sort(PointSort), 0, pts.length-1)\n    \n    return edges\n}\n\nfunction delaunay(edges, pts, min, max) {\n    // how many points are we triangulating\n    const size = max-min+1\n    \n    // zero or 1 point is the trivial delaunay triangulation \n    if (size < 1) return edges\n    \n    // 2 points can be computed easily\n    if (size == 2) return Triangulate2(edges, pts[min], pts[max])\n    \n    // 3 points can be computed easily\n    if (size == 3) return Triangulate3(edges, pts[min], pts[min+1], pts[max])\n    \n    // otherwise we divide into halves:\n    const mid = min+((max-min)>>>1)\n    \n    delaunay(edges, pts, min, mid)\n    delaunay(edges, pts, mid+1, max)\n    \n    // and then merge the results\n    return Merge(adj, mid, mid+1)\n}\n```\n\nWhat remains then is to specify the subroutines `PointSort`, `Triangulate2`, `Triangulate3`, and `Merge`.\n\n#### PointSort Subroutines\n```todo```\n\n#### Triangulate2+3 Subroutines\n```todo```\n\n#### Merge Subroutine\n```todo```\n\n## Geometry Prerequisites\nThe implementation depends on the following geometric concepts and properties:\n\n#### PseudoAngle\n```todo```\n\n#### RightOf\n```todo```\n\n#### Circumscribed\n```todo```\n\n#### Convex Hull\n```todo```\n\n\n## Data Structures\nThe efficiency depends heavily on being able to traverse the triangulation efficiently, to do so we construct a `Vertex Cycle` data structure which is effectively a specialised `Cyclic Linked List`.\n\n#### Cyclic Linked List\n```todo```\n\n#### Vertex Cycle\n```todo```\n","readmeFilename":"README.md"}