Capacity Constrained Point Distributions, an algorithm by Michael Balzer, Thomas Schlömer & Oliver Deussen (University of Konstanz, Germany, 2009).
(Not sure I have implemented it correctly, but it seems to work, albeit slowly.)
Idea found on n-e-r-v-o-u-s.
I made variant with a Delaunay topology to get much faster results. It seems to work quite well in practice.
And here is also a data-based variant.
<!DOCTYPE html>
<meta charset="utf-8">
<style>
.polygons {
fill: none;
stroke: #333;
}
</style>
<svg width="940" height="480"></svg>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script>
var svg = d3.select("svg"),
width = +svg.attr("width"),
height = +svg.attr("height");
var color = d3.scaleOrdinal(d3.schemeCategory20b);
var sites = d3.range(512)
.map(function (d) {
return [Math.random() * width, Math.random() * height];
});
var voronoi = d3.voronoi().size([width, height]),
diagram = voronoi(sites);
var polygon = svg.append("g")
.attr("class", "polygons")
.selectAll("path")
.data(diagram.polygons())
.enter().append("path")
.attr('fill', function (d, i) {
return color(i)
})
.attr('fill-opacity', 0.1)
.attr('stroke-opacity', 0.1);
const capacity = 20;
var points = d3.range(capacity * sites.length)
.map(function (d) {
return [((Math.random() > 0.5 ? -1 : 1) / 4 + (Math.random() - Math.random()) / 4 + 1 / 2) * width, (1 + Math.random() - Math.random()) / 2 * height];
});
function distance2(a, b) {
var dx = a[0] - b[0],
dy = a[1] - b[1];
return /*Math.sqrt*/ (dx * dx + dy * dy);
}
function iterate() {
var changes = 0;
for (var i = 1; i < sites.length; i++) {
for (var j = 0; j < i; j++) {
var Hi = [],
Hj = [],
k, ki, kj;
for (k = 0; k < capacity; k++) {
Hi.push(distance2(points[i * capacity + k], sites[j]) - distance2(points[i * capacity + k], sites[i]));
Hj.push(distance2(points[j * capacity + k], sites[i]) - distance2(points[j * capacity + k], sites[j]));
}
while (Hi.length > 0 && Hj.length > 0 && ((ki = d3.scan(Hi)) || true) && ((kj = d3.scan(Hj)) || true) && (Hi[ki] + Hj[kj] < 0)) {
changes++;
var temp = points[i * capacity + ki];
points[i * capacity + ki] = points[j * capacity + kj];
points[j * capacity + kj] = temp;
Hi = Hi.slice(0, ki).concat(Hi.slice(ki + 1));
Hj = Hj.slice(0, kj).concat(Hj.slice(kj + 1));
}
}
}
return changes;
}
var site = svg.selectAll('circle')
.data(sites)
.enter()
.append('circle')
.attr('transform', function (d) {
return 'translate(' + d + ')';
})
.attr('r', 3)
.attr('fill', function (d, i) {
return color(i);
})
if (false)
svg.selectAll('rect')
.data(points)
.enter()
.append('rect')
.attr('transform', function (d) {
return 'translate(' + d + ')';
})
.attr('width', 2)
.attr('height', 2)
.attr('fill', function (d, i) {
return color(Math.floor(i / capacity));
})
var lastchanges = null;
var interval = d3.interval(function () {
var changes = iterate();
svg.selectAll('circle')
.data(sites)
.attr('transform', function (d) {
return 'translate(' + d + ')';
})
svg.selectAll('rect')
.data(points)
.attr('transform', function (d) {
return 'translate(' + d + ')';
})
diagram = voronoi(sites);
polygon = polygon.data(diagram.polygons())
.attr("d", function (d) {
return d ? "M" + d.join("L") + "Z" : null;
});;
sites = sites.map(function (site, i) {
var pts = points.slice(i * capacity, i * capacity + capacity);
site[0] = d3.mean(pts.map(function (d) {
return d[0];
}));
site[1] = d3.mean(pts.map(function (d) {
return d[1];
}));
return site;
});
console.log("changes", changes);
if (changes == lastchanges) {
console.log("stabilized!")
interval.stop();
polygon
.transition()
.duration(4000)
.attr('fill-opacity', 0)
.attr('stroke-opacity', 0.1);
site.transition()
.duration(4000)
.attr('fill', 'black');
}
lastchanges = changes;
})
</script>