Delunay with circumcircles by drifkin

Left click to toggle between Delaunay and Voronoi.
Right click to toggle whether the circumcircles are drawn.

Adapted from the Voronoi Tessellation and Delaunay Triangulation examples.

The Delaunay triangulation has the property that each triangle’s circumcircle does not contain any points other than the vertices of its associated triangle.

The Delaunay triangulation is a dual of the Voronoi tessellation: given a Voronoi tessellation, connect vertices that correspond to neighboring polygons to get the Delaunay triangulation.

Built with blockbuilder.org.

index.html

<!DOCTYPE html>
<head>
  <meta charset="utf-8">
  <script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.5/d3.min.js"></script>
  <style>
path {
  fill: #eaeaea;
  stroke: #000;
}

circle.vertex {
  fill: red;
  stroke: none;
  pointer-events: none;
}

circle.circumcircle {
  fill: none;
  stroke: rgba(0, 0, 0, 0.3);
}
  </style>
</head>

<body>
  <script>
var width = 960,
    height = 500;

var numVertices = 30;
var vertices = d3.range(numVertices).map(function(d) {
  return [Math.random() * width, Math.random() * height];
});

var svg = d3.select("body").append("svg")
    .attr("width", width)
    .attr("height", height)
    .on("mousemove", function() { vertices[0] = d3.mouse(this); redraw(); })
    .on("click", function() {
      useVoronoi = !useVoronoi;
      redraw();
    })
    .on("contextmenu", function(e) {
      d3.event.preventDefault();
      drawCircumcircles = !drawCircumcircles;
      redraw();
    });

// Draw vertices on top
var shapeContainer = svg.append("g");
var vertexContainer = svg.append("g");

var path = shapeContainer.append("g").selectAll("path");

var voronoi = d3.geom.voronoi()
    .clipExtent([[0, 0], [width, height]]);

var useVoronoi = false;
var drawCircumcircles = true;
function redraw() {
  vertexContainer.selectAll("circle.vertex")
    .data(vertices)
    .attr("transform", function(d) { return "translate(" + d + ")"; })
  .enter().append("circle")
    .attr("class", "vertex")
    .attr("r", 2);

  var voronoiPolygons = voronoi(vertices);
  var delaunayTriangles = d3.geom.delaunay(vertices);

  var shapesToUse = useVoronoi ? voronoiPolygons : delaunayTriangles;

  path = path
      .data(shapesToUse, polygon);

  path.exit().remove();

  path.enter().append("path")
      .attr("d", polygon);

  path.order();

  var circumcircleData = drawCircumcircles ? delaunayTriangles.map(function(triangle) {
    var a = triangle[0];
    var b = triangle[1];
    var c = triangle[2];

    // get the circumcircle's center point:
    // https://en.wikipedia.org/wiki/Circumscribed_circle#Cartesian_coordinates_2
    var d = 2 * ( a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1]));

    var a2 = a[0] * a[0] + a[1] * a[1];
    var b2 = b[0] * b[0] + b[1] * b[1];
    var c2 = c[0] * c[0] + c[1] * c[1];
    var u_x = ( a2 * (b[1] - c[1]) + b2 * (c[1] - a[1]) + c2 * (a[1] - b[1])) / d;
    var u_y = ( a2 * (c[0] - b[0]) + b2 * (a[0] - c[0]) + c2 * (b[0] - a[0])) / d;

    var xdiff = a[0] - u_x;
    var ydiff = a[1] - u_y;
    var r = Math.sqrt(xdiff * xdiff + ydiff * ydiff);
    return {
      c: [u_x, u_y],
      r: r
    };
  }) : [];

  var circumcircles = shapeContainer.selectAll("circle.circumcircle")
      .data(circumcircleData);

  circumcircles.enter().append("circle")
      .attr("class", "circumcircle");

  circumcircles
      .attr("transform", function(d) { return "translate(" + d.c[0] + ", " + d.c[1] + ")"; })
      .attr("r", function(d) { return d.r });

  circumcircles.exit().remove();
}

function polygon(d) {
  return "M" + d.join("L") + "Z";
}

redraw();
  </script>
</body>