Voronoi Lookup by syntagmatic

index.html

<!DOCTYPE html>
<meta charset="utf-8">
<body>
<script src="//d3js.org/d3.v3.js"></script>
<script>

var width = 960,
    height = 500;

var k = 20 // number of candidates to consider per point
    m = 10, // initial number of points to add per frame
    n = 2500, // remaining number of points to add
    newPoint = bestPointGenerator(32),
    points = [],
    voronoi = d3.geom.voronoi().clipExtent([[-1, -1], [width + 1, height + 1]]),
    cells = voronoi(points),
    quadtree = d3.geom.quadtree().extent([[0, 0], [width, height]])([]);


var canvas = d3.select("body").append("canvas")
    .attr("width", width)
    .attr("height", height)
    .on("mousemove", function(x) {
      if (cells.length < 1) return;

      var pos = d3.mouse(this);
      var closestPoint = [Infinity, Infinity];
      var minDistance = Infinity;

      // search for closest point
      quadtree.visit(function(quad, x1, y1, x2, y2) {
        var rx1 = pos[0] - minDistance,
            rx2 = pos[0] + minDistance,
            ry1 = pos[1] - minDistance,
            ry2 = pos[1] + minDistance;
        if (p = quad.point) {
          var p,
              dx = pos[0] - p[0],
              dy = pos[1] - p[1],
              d2 = dx * dx + dy * dy,
              d = Math.sqrt(d2);
          if (d < minDistance) {
            closestPoint = p;
            minDistance = d;
          }
        }
        return x1 > rx2 || x2 < rx1 || y1 > ry2 || y2 < ry1; // bounding box outside closest point
      });

      // render highlighted point
      var closestPointIndex = points.indexOf(closestPoint);
      context.fillStyle = "#aaa";
      drawCell(cells[closestPointIndex]);
      context.fillStyle = "#fff";
    });

var context = canvas.node().getContext("2d");

context.strokeStyle = "#999";
context.fillStyle = "#fff";

d3.timer(function() {
  var n0 = points.length;

  for (var i = 0; i < m && --n >= 0; ++i) {
    points.push(newPoint(k));

    // As we add more circles, gradually reduce circles per frame.
    if (m > 1) m *= .998;
  }

  cells = voronoi(points);

  for (var n1 = points.length, cell; n0 < n1; ++n0) {
    drawCell(cells[n0]);
  }

  return !n;
});

function drawCell(cell) {
  context.beginPath();
  context.moveTo(cell[0][0], cell[0][1]);
  for (var i = 1, l = cell.length; i < l; ++i) context.lineTo(cell[i][0], cell[i][1]);
  context.closePath();
  context.fill();
  context.stroke();
};

function bestPointGenerator(searchRadius) {
  return function(k) {
    var bestX, bestY, bestDistance = 0;

    for (var i = 0; i < k; ++i) {
      var x = Math.random() * width,
          y = Math.random() * height,
          rx1 = x - searchRadius,
          rx2 = x + searchRadius,
          ry1 = y - searchRadius,
          ry2 = y + searchRadius,
          minDistance = searchRadius; // minimum distance for this candidate

      quadtree.visit(function(quad, x1, y1, x2, y2) {
        if (p = quad.point) {
          var p,
              dx = x - p[0],
              dy = y - p[1],
              d2 = dx * dx + dy * dy,
              d = Math.sqrt(d2);
          if (d < minDistance) {
            minDistance = d;
            rx1 = x - d;
            rx2 = x + d;
            ry1 = y - d;
            ry2 = y + d;
          }
        }
        return x1 > rx2 || x2 < rx1 || y1 > ry2 || y2 < ry1; // or outside search radius
      });

      if (minDistance > bestDistance) bestX = x, bestY = y, bestDistance = minDistance;
    }

    var best = [bestX, bestY];
    quadtree.add(best);
    return best;
  };
}

</script>