All examples By author By category About

veltman

Full window Github gist

Stippling

Stress testing the stippling application of this capacity-constrained distribution method. By storing everything in a few flat typed arrays, a group of 2000 sites seems possible (though still quite slow) in browser.

See also: Philippe Rivière's neighbors-of-neighbors variation on the algorithm

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="utf-8" />
  <style>
  </style>
</head>
<body>
<canvas width="960" height="400"></canvas>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/4.2.3/d3.min.js"></script>
<script>

var canvas = document.querySelector("canvas"),
    context = canvas.getContext("2d"),
    img = new Image(),
    width = 320,
    height = 400,
    numSites = 2000,
    capacity = 15,
    iterations = 0,
    numPoints = numSites * capacity,
    points = new Float32Array(numPoints * 3),
    sites = new Float32Array(numSites * 2),
    assignments = new Uint32Array(numPoints),
    bisect = d3.bisector(function(d) { return d.diff; }).left;

img.onload = initialize;

img.src = "obama.png";

function initialize() {

context.drawImage(img, 0, 0, width, height);
  generatePoints(context.getImageData(0, 0, width, height).data);
  generateSites();
  initializeAssignments();
  draw();
  requestAnimationFrame(update);

}

function update() {

var stable = true;

for (var i = 0; i < numSites - 1; i++) {
    for (var j = i + 1; j < numSites; j++) {
      if (swapPointsBetween(i, j)) {
        stable = false;
      }
    }
  }

iterations++;

draw();

if (!stable) {
    for (var i = 0; i < numSites; i++) {
      recenter(i);
    }
    requestAnimationFrame(update);
  }

}

function draw() {

var x,
      y,
      pi;

context.clearRect(width, 0, width * 2, height);

for (var i = 0; i < numSites; i++) {

context.fillStyle = d3.schemeCategory20[i % 20];
    context.beginPath();
    for (var p = 0; p < capacity; p++) {

pi = assignments[i * capacity + p];
      x = points[pi * 3] + width;
      y = points[pi * 3 + 1];

context.moveTo(x, y);
      context.arc(x, y, 1, 0, 2 * Math.PI);
    }
    context.fill();

context.fillStyle = "#444";
    context.beginPath();
    x = sites[i * 2] + width * 2;
    y = sites[i * 2 + 1];
    context.moveTo(x, y);
    context.arc(x, y, 1.5, 0, 2 * Math.PI);
    context.fill();

}

function recenter(si) {

var pi,
      x = 0,
      y = 0;

for (var i = 0; i < capacity; i++) {
    pi = assignments[si * capacity + i];
    x += points[pi * 3];
    y += points[pi * 3 + 1];
  }

sites[si * 2] = x / capacity;
  sites[si * 2 + 1] = y / capacity;

}

function swapPointsBetween(si, sj) {

var stable = true,
      hi = [],
      hj = [],
      pi,
      pj,
      diff,
      i;

for (i = 0; i < capacity; i++) {

pi = assignments[si * capacity + i];

diff = points[pi * 3 + 2] - distanceBetweenSiteAndPoint(sj, pi);

if (diff > 0) {
      hi.splice(bisect(hi, { diff: diff }), 0, {
        assignmentIndex: si * capacity + i,
        distanceIndex: pi * 3 + 2,
        diff: diff
      });
    }

pj = assignments[sj * capacity + i];

diff = points[pj * 3 + 2] - distanceBetweenSiteAndPoint(si, pj);

if (diff > 0) {
      hj.splice(bisect(hj, { diff: diff }), 0, {
        assignmentIndex: sj * capacity + i,
        distanceIndex: pj * 3 + 2,
        diff: diff
      });
    }

}

while (hi.length && hj.length) {
    swapPoints(hi.pop(), hj.pop());
    stable = false;
  }

return !stable;

}

function swapPoints(fr, to) {

var swap = assignments[fr.assignmentIndex];

points[fr.distanceIndex] -= fr.diff;
  points[to.distanceIndex] -= to.diff;

assignments[fr.assignmentIndex] = assignments[to.assignmentIndex];
  assignments[to.assignmentIndex] = swap;

}

function initializeAssignments() {

var si;

for (var i = 0; i < numPoints; i++) {

si = Math.floor(i / capacity);

assignments[i] = i;
    points[i * 3 + 2] = distanceBetweenSiteAndPoint(si, i);

}

function generatePoints(density) {

var x,
      y;

for (var i = 0; i < numPoints; i++) {

x = null;

while (x === null) {
      x = Math.random() * width,
      y = Math.random() * height;

if (Math.random() > density[4 * (width * Math.floor(y) + Math.floor(x))] / 255) {
        points[i * 3] = x;
        points[i * 3 + 1] = y;
      } else {
        x = null;
      }
    }

}

function generateSites() {

for (var i = 0; i < numSites; i++) {
    sites[i * 2] = Math.random() * width;
    sites[i * 2 + 1] = Math.random() * height;
  }

}

function distanceBetweenSiteAndPoint(si, pi) {

var dx = (points[pi * 3] - sites[si * 2]),
      dy = (points[pi * 3 + 1] - sites[si * 2 + 1]);

return Math.sqrt(dx * dx + dy * dy);

}

</script>

https://cdnjs.cloudflare.com/ajax/libs/d3/4.2.3/d3.min.js