| height: 400 |
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> |
