{"action":"created","issue":{"url":"https://api.github.com/repos/Turfjs/turf/issues/241","labels_url":"https://api.github.com/repos/Turfjs/turf/issues/241/labels{/name}","comments_url":"https://api.github.com/repos/Turfjs/turf/issues/241/comments","events_url":"https://api.github.com/repos/Turfjs/turf/issues/241/events","html_url":"https://github.com/Turfjs/turf/issues/241","id":63530775,"number":241,"title":"turf-constrainedtin","user":{"login":"AbelVM","id":9017165,"avatar_url":"https://avatars.githubusercontent.com/u/9017165?v=3","gravatar_id":"","url":"https://api.github.com/users/AbelVM","html_url":"https://github.com/AbelVM","followers_url":"https://api.github.com/users/AbelVM/followers","following_url":"https://api.github.com/users/AbelVM/following{/other_user}","gists_url":"https://api.github.com/users/AbelVM/gists{/gist_id}","starred_url":"https://api.github.com/users/AbelVM/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/AbelVM/subscriptions","organizations_url":"https://api.github.com/users/AbelVM/orgs","repos_url":"https://api.github.com/users/AbelVM/repos","events_url":"https://api.github.com/users/AbelVM/events{/privacy}","received_events_url":"https://api.github.com/users/AbelVM/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":15,"created_at":"2015-03-22T13:13:40Z","updated_at":"2015-03-30T20:55:00Z","closed_at":null,"body":"Looking for a constrained Voronoi/Delaunay method to get tin grids within polygons, found [poly2tri](https://code.google.com/p/poly2tri/), based on the paper **\"Sweep-line algorithm for constrained Delaunay triangulation\"** by V. Domiter and and B. Zalik. This library takes into account concavities and holes, and once you have this tin, its *easy* to get the constrained Voronoi diagram for your polygon.\r\n\r\nThere is a JavaScript port called [poly2tri.js](https://github.com/r3mi/poly2tri.js), and I have made a simple wrapper to make it work with GeoJSON. This is my proposal as a module, but it may/should be merged with [turf-tin](https://github.com/Turfjs/turf-tin) as an overload:\r\n![restrictedtin](http://i62.tinypic.com/9fo7r9.png)\r\n\r\n```javascript\r\n/**\r\n*\tturf.constrainedtin\r\n*\tFunction that gets a {@link Polygon} and make a tin constrained to it\r\n* @requires\thttp://r3mi.github.io/poly2tri.js/dist/poly2tri.js\r\n* @param {Feature<(Polygon)>} poly - single Polygon Feature\r\n* @return {FeatureCollection<(Polygon)>} \r\n* @author\tAbel Vázquez\r\n* @version 1.0.0\r\n*/\r\nturf.constrainedtin = function(poly){\r\n\t\r\n\t// check poly is a polygon\r\n\tif (poly.geometry === void 0 || poly.geometry.type !== 'Polygon' ) throw('\"constrainedtin \" only accepts polygon type input');\r\n\t\r\n\tvar\ttriangles,\r\n\t\t\tctx =  input.geometry.coordinates.map(function(a){\r\n\t\t\t\tvar c = a.map(function(b){\r\n\t\t\t\t\treturn new poly2tri.Point(b[0], b[1])\r\n\t\t\t\t\t});\r\n\t\t\t\tc.pop();\r\n\t\t\t\treturn c;\r\n\t\t\t\t}),\r\n\t\t\tswctx = new poly2tri.SweepContext(ctx.shift()),\r\n\t\t\tfeatures;\r\n\t\t\t\r\n\tif (ctx.length>0) swctx.addHoles(ctx);\r\n\t\r\n\ttriangles = swctx.triangulate().getTriangles();\r\n\t\r\n\tfeatures = triangles.map(function(t){\r\n\t\tvar points =[];\r\n\t\t t.getPoints().forEach(function(p) {\r\n\t\t\tpoints.push([p.x, p.y]);\r\n\t\t});\r\n\t\tpoints.push([t.getPoint(0).x, t.getPoint(0).y])\r\n\t\treturn turf.polygon([points]);\r\n\t});\r\n\t\r\n\treturn turf.featurecollection(features);\r\n\t\r\n}\r\n```\r\n"},"comment":{"url":"https://api.github.com/repos/Turfjs/turf/issues/comments/87828914","html_url":"https://github.com/Turfjs/turf/issues/241#issuecomment-87828914","issue_url":"https://api.github.com/repos/Turfjs/turf/issues/241","id":87828914,"user":{"login":"AbelVM","id":9017165,"avatar_url":"https://avatars.githubusercontent.com/u/9017165?v=3","gravatar_id":"","url":"https://api.github.com/users/AbelVM","html_url":"https://github.com/AbelVM","followers_url":"https://api.github.com/users/AbelVM/followers","following_url":"https://api.github.com/users/AbelVM/following{/other_user}","gists_url":"https://api.github.com/users/AbelVM/gists{/gist_id}","starred_url":"https://api.github.com/users/AbelVM/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/AbelVM/subscriptions","organizations_url":"https://api.github.com/users/AbelVM/orgs","repos_url":"https://api.github.com/users/AbelVM/repos","events_url":"https://api.github.com/users/AbelVM/events{/privacy}","received_events_url":"https://api.github.com/users/AbelVM/received_events","type":"User","site_admin":false},"created_at":"2015-03-30T20:55:00Z","updated_at":"2015-03-30T20:55:00Z","body":"**...it's getting better!**\r\n\r\nAnd faster! But due to its improved accuracy it needs to manage a lot of Delaunay triangles now (today I generate ~700 Delaunay cells where yesterday we had ~40 cells), so it takes a while to retrieve the Voronoi diagram .\r\n![voro](http://i58.tinypic.com/2iagbwn.png)\r\nLimitations of poly2tri itself and the logic behind, force to set aside some of the cells. There are cells that need further proccessing, but **poly2tri** tells me that some points are collinear and that's all, folks. This test case gives me 18 triangles out of 697 that, being Delaunay compliant, can't be used to generate the constrained Voronoi (green cells).\r\n\r\nAs soon as I clean the code, and do some fine tuning, I will commit all this abracadabra stuff and I hope that someone could find the way to refine it even more.\r\n\r\nI'm thinking about init the polygon with midpoints in each segment. That's cheating, I know, but..."}}