1 /**

     2 * @param vertices [[x1, y1], [x2, y2], …]

     3 * @returns triangles [[[x1, y1], [x2, y2], [x3, y3]], …]

     4  */

     5 d3.geom.delaunay = function(vertices) {

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

     7       triangles = [];

     8 

     9   // Use the Voronoi tessellation to determine Delaunay edges.

    10   d3_voronoi_tessellate(vertices, function(e) {

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

    12   });

    13 

    14   // Reconnect the edges into counterclockwise triangles.

    15   edges.forEach(function(edge, i) {

    16     var v = vertices[i],

    17         cx = v[0],

    18         cy = v[1];

    19     edge.forEach(function(v) {

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

    21     });

    22     edge.sort(function(a, b) {

    23       return a.angle - b.angle;

    24     });

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

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

    27     }

    28   });

    29 

    30   return triangles;

    31 };