Capacity Constrained Point Distributions

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>

https://d3js.org/d3.v4.min.js