{"_id":"cdt2d","_rev":"11-d86697ba4dd978a173e4f609a2080a0c","name":"cdt2d","description":"Constrained Delaunay Triangulation in 2D","dist-tags":{"latest":"1.0.0"},"versions":{"0.0.0":{"name":"cdt2d","version":"0.0.0","description":"Constrained Delaunay Triangulation in 2D","main":"index.js","dependencies":{"binary-search-bounds":"^2.0.3","robust-in-sphere":"^1.1.3","robust-orientation":"^1.1.3"},"devDependencies":{"canvas-fit":"^1.4.0","cell-orientation":"^1.0.1","convex-hull":"^1.0.3","delaunay-triangulate":"^1.1.6","flip-orientation":"^1.0.1","gauss-random":"^1.0.1","mouse-change":"^1.2.1","robust-segment-intersect":"^1.0.1","robust-triangle-triangle-2d-intersect":"^1.0.0","segment2":"^0.3.2","signum":"^1.0.0","simplicial-complex-boundary":"^1.0.1","tape":"^4.0.0","uniq":"^1.0.1","vec2":"^1.6.0"},"scripts":{"test":"tape test/*.js"},"repository":{"type":"git","url":"https://github.com/mikolalysenko/cdt2d.git"},"keywords":["constrained","delaunay","triangulation","polygon","planar","graph","vertex","geometry","cdt","2d","triangle","edge","point","robust","exact","constraint","hole","loop"],"author":{"name":"Mikola Lysenko"},"license":"MIT","bugs":{"url":"https://github.com/mikolalysenko/cdt2d/issues"},"homepage":"https://github.com/mikolalysenko/cdt2d","gitHead":"b04edb3d19ecbae9b1cf6623058ed37eaec2dc1b","_id":"cdt2d@0.0.0","_shasum":"41948f10c99a594adf791e04630b411249fb0aa1","_from":".","_npmVersion":"2.7.4","_nodeVersion":"0.12.2","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"dist":{"shasum":"41948f10c99a594adf791e04630b411249fb0aa1","tarball":"https://registry.npmjs.org/cdt2d/-/cdt2d-0.0.0.tgz","integrity":"sha512-cSlUlFPHOFdTVDteifSHfM0y8M8Eyj3ip6cBWFPXeRpJhdC1htyUjJMVpuJJ3l6BkuDF9j+yxQ7SUaiXgS8MeA==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIEHH0v8yHaFRU87d2ASXV0g1YzQUdruUe1+KV47Uz8+yAiEAtWQ8GCzn8lDAfuWX4eEAleYl4V0lFHasn5RkMb0FtWg="}]},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}]},"1.0.0":{"name":"cdt2d","version":"1.0.0","description":"Constrained Delaunay Triangulation in 2D","main":"cdt2d.js","dependencies":{"binary-search-bounds":"^2.0.3","robust-in-sphere":"^1.1.3","robust-orientation":"^1.1.3"},"devDependencies":{"canvas-fit":"^1.4.0","cell-orientation":"^1.0.1","convex-hull":"^1.0.3","delaunay-triangulate":"^1.1.6","flip-orientation":"^1.0.1","gauss-random":"^1.0.1","mouse-change":"^1.2.1","robust-segment-intersect":"^1.0.1","robust-triangle-triangle-2d-intersect":"^1.0.0","segment2":"^0.3.2","signum":"^1.0.0","simplicial-complex-boundary":"^1.0.1","tape":"^4.0.0","uniq":"^1.0.1","vec2":"^1.6.0"},"scripts":{"test":"tape test/*.js"},"repository":{"type":"git","url":"https://github.com/mikolalysenko/cdt2d.git"},"keywords":["constrained","delaunay","triangulation","polygon","planar","graph","vertex","geometry","cdt","2d","triangle","edge","point","robust","exact","constraint","hole","loop"],"author":{"name":"Mikola Lysenko"},"license":"MIT","bugs":{"url":"https://github.com/mikolalysenko/cdt2d/issues"},"homepage":"https://github.com/mikolalysenko/cdt2d","gitHead":"a2aba65b89f048890e8c9c78f40ea403497262d7","_id":"cdt2d@1.0.0","_shasum":"4f212434bcd67bdb3d68b8fef4acdc2c54415141","_from":".","_npmVersion":"2.7.4","_nodeVersion":"0.12.2","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"dist":{"shasum":"4f212434bcd67bdb3d68b8fef4acdc2c54415141","tarball":"https://registry.npmjs.org/cdt2d/-/cdt2d-1.0.0.tgz","integrity":"sha512-pFKb7gVhpsI6onS5HUXRoqbBIJB4CJ+KPk8kgaIVcm0zFgOxIyBT5vzifZ4j1aoGVJS0U1A+S4oFDshuLAitlA==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIFwdXuurGYCcMgOST7X8ZPVWPKGLeejrIl6jqkobikBMAiEA6DRRKrWm+Ku4rAU3w+Xdx65+o0zVXK5/hXTNBUUd4Ag="}]},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}]}},"readme":"cdt2d\n=====\n<img src=\"img/logo.png\">\n\nA robust 2D [constrained Delaunay triangulation](https://en.wikipedia.org/wiki/Constrained_Delaunay_triangulation) library written in JavaScript.\n\n**WORK IN PROGRESS**\n\n# [Demo](https://mikolalysenko.github.io/cdt2d)\n\nTo test out this module, you can open up a demo in your browser with the following link:\n\n[<img src=\"img/demo.png\">](https://mikolalysenko.github.io/cdt2d)\n\n#### [cdt2d demo](https://mikolalysenko.github.io/cdt2d)\n\n* Click to add points\n* Click on a point to remove it\n* Drag one point onto another to add an edge constraint\n* Click on a green edge to remove a constraint\n* Toggle options by clicking on the checkboxes on the left\n* Click reset to clear all points\n\n# Examples\n\n## Simple example\n\nHere is a simple example showing how to invoke `cdt2d`:\n\n```javascript\n//First we need to reqire the module\nvar cdt2d = require('cdt2d')\n\n//Then we define a list of points, represented as pairs of x,y coordinates\nvar points = [\n  [-2,-2],\n  [-2, 2],\n  [ 2, 2],\n  [ 2,-2],\n  [ 1, 0],\n  [ 0, 1],\n  [-1, 0],\n  [ 0,-1]\n]\n\n//Next we can optionally define some edge constraints\n// This set of edges determines a pair of loops\nvar edges = [\n //Outer loop\n [0, 1],\n [1, 2],\n [2, 3],\n [3, 0],\n\n //Inner loop\n [4, 5],\n [5, 6],\n [6, 7],\n [7, 4]\n]\n\n//Finally we call cdt2d with the points and edges\n// The flag {exterior: false} tells  it to remove exterior faces\nconsole.log(cdt2d(points, edges, {exterior: false}))\n```\n\n#### Output\n\nThe above program will output the following triangles:\n\n```javascript\n[ [ 0, 3, 7 ],\n  [ 0, 6, 1 ],\n  [ 0, 7, 6 ],\n  [ 1, 5, 2 ],\n  [ 1, 6, 5 ],\n  [ 2, 4, 3 ],\n  [ 2, 5, 4 ],\n  [ 3, 4, 7 ] ]\n```\n\nEach triangle is represented as an array of 3 indices of points.  We can visualize this data in the following figure:\n\n<img src=\"img/example-cdt.png\">\n\n## Messy graphs\n\nIf your input doesn't satisfy the validity invariants (ie no self intersections, duplicate vertices or t-junctions), then you will need to preprocess it to clean it up.  One way to do this is with the [`clean-pslg` module](https://github.com/mikolalysenko/clean-pslg).  Here is an example showing how to do this:\n\n```javascript\nvar cleanPSLG = require('clean-pslg')\nvar cdt2d = require('cdt2d')\n\nvar points = [\n  [-1, 0],\n  [ 1, 0],\n  [ 0,-1],\n  [ 0, 1]\n]\n\nvar edges = [\n  [0, 1],\n  [1, 2]\n]\n\n//This updates points/edges so that they now form a valid PSLG\ncleanPSLG(points, edges)\n\n//Generate the triangulation\nconsole.log({\n  points: points,\n  edges: edges,\n  triangles: cdt2d(points, edges)\n})\n```\n\n#### Output\n\n**TODO**\n\n## Polygon example\n\nIt is also pretty easy to use this module with polygons, as one would get from a GeoJSON file.  To do this, it is first necessary to convert them into a planar straight line graph.  This can be done using the `poly-to-pslg` module:\n\n```javascript\nvar toPSLG = require('poly-to-pslg')\nvar cdt2d = require('cdt2d')\n\n```\n\n**TODO**\n\n## Polygon with holes example\n\nThe above procedure even works if the polygons have holes:\n\n```javascript\nvar toPSLG = require('poly-to-pslg')\nvar cdt2d = require('cdt2d')\n\n```\n\n**TODO**\n\n## Delaunay triangulation\n\nYou can also use `cdt2d` to generate Delaunay triangulations of arbitrary point sets in the plane:\n\n```javascript\n```\n\n**TODO**\n\n# Install\n\nThis module works in any modern CommonJS environment.  You can install it using [npm](https://docs.npmjs.com/) with the following command:\n\n```\nnpm i cdt2d\n```\n\nYou should be able to then use it in [node](https://nodejs.org/) or on the web with [browserify](http://browserify.org/).\n\n# API\n\n#### `var cells = require('cdt2d')(points[, edges, options])`\nConstructs a constrained Delaunay triangulation of a [planar straight-line graph](https://en.wikipedia.org/wiki/Planar_graph).\n\n* `points` are the vertices of the triangulation, represented by pairs of numbers.\n* `edges` is an optional list of edge constraints which must occur within the triangulation. These constraints are given by pairs of indices of points.  If not specified, then no constraints are used.\n* `options` is an object which takes some optional parameters.\n    + `delaunay` if this flag is set to true, then the resulting triangulation is converted to a [Delaunay triangulation](https://en.wikipedia.org/wiki/Delaunay_triangulation) by edge flipping.  Otherwise if it is false, then an arbitrary triangulation is returned.  (Default `true`)\n    + `interior` if set, only return interior faces. See note. (Default `true`)\n    + `exterior` if set, only return exterior faces. See note. (Default `true`)\n    + `infinity` if set, then the triangulation is augmented with a [point at infinity](https://en.wikipedia.org/wiki/Point_at_infinity) represented by the index `-1`.  (Default `false`)\n\n**Returns** A list of all triangles represented as triples of indices of vertices\n\n**Note on interior/exterior classification** Interior/exterior faces are classified by treating the constraint edges as the boundary and traversing the triangulation. The point at infinity is in the exterior of the set, and other faces are classified by the parity of the path with fewest crossings from the face to the point at infinity.\n\n**Assumptions** This module makes the following assumptions about the points and edge constraints:\n\n* No point in the input is duplicated\n* No pair of edge constraints cross in their relative interior\n* No point is contained in the relative interior of an edge (ie no T-junctions)\n\nIf your input does not satisfy these conditions, you will need to preprocess it first (using [`clean-pslg`](https://github.com/mikolalysenko/clean-pslg) for example) otherwise `cdt2d` may return incorrect results.\n\n**Limitations** Currently there is no way to specify that only some edge constraints are to be included in the boundary.  It is also not possible to add a constraint from a vertex to the point at infinity. If there is enough demand I may add these features or perhaps create a separate module.\n\n# Benchmarks and comparisons\n\nAssertion: `cdt2d` is the only non-broken triangulation library in JavaScript.\n\n* **TODO** Catalogue failing cases for other libraries\n* **TODO** Need to measure performance and finetune\n\nLibraries to compare against:\n\n* `earcut`\n* `poly2tri`\n* `pnltri`\n* `libtess.js`\n\n# License\n(c) 2015 Mikola Lysenko. MIT License\n","maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}],"time":{"modified":"2022-06-13T05:45:46.642Z","created":"2015-06-26T17:33:01.119Z","0.0.0":"2015-06-26T17:33:01.119Z","1.0.0":"2015-06-28T10:09:47.610Z"},"homepage":"https://github.com/mikolalysenko/cdt2d","keywords":["constrained","delaunay","triangulation","polygon","planar","graph","vertex","geometry","cdt","2d","triangle","edge","point","robust","exact","constraint","hole","loop"],"repository":{"type":"git","url":"https://github.com/mikolalysenko/cdt2d.git"},"author":{"name":"Mikola Lysenko"},"bugs":{"url":"https://github.com/mikolalysenko/cdt2d/issues"},"license":"MIT","readmeFilename":"README.md","users":{"urita":true,"vorg":true,"taseenb":true,"codeandcats":true}}