d3/src/geom/delaunay.js at master · blehman/d3

Repository navigation

import "geom";

import "voronoi";

// @deprecated; use d3.geom.voronoi links instead.

d3.geom.delaunay = function(vertices) {

var edges = vertices.map(function() { return []; }),

triangles = [];

// Use the Voronoi tessellation to determine Delaunay edges.

d3_geom_voronoiTessellate(vertices, function(e) {

edges[e.region.l.index].push(vertices[e.region.r.index]);

});

// Reconnect the edges into counterclockwise triangles.

edges.forEach(function(edge, i) {

var v = vertices[i],

cx = v[0],

cy = v[1];

edge.forEach(function(v) {

v.angle = Math.atan2(v[0] - cx, v[1] - cy);

});

edge.sort(function(a, b) {

return a.angle - b.angle;

});

for (var j = 0, m = edge.length - 1; j < m; j++) {

triangles.push([v, edge[j], edge[j + 1]]);

}

});

return triangles;

};