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.
forked from Fil‘s block: Capacity Constrained Point Distributions
<!DOCTYPE html>
<meta charset="utf-8">
<style>
.polygons {
fill: none;
stroke: #333;
}
path {
fill: none;
stroke: #222;
}
</style>
<svg width="940" height="480"></svg>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script>
var color = d3.scaleOrdinal(d3.schemeCategory20b);
var margin = {top: 20, right: 20, bottom: 30, left: 50},
width = 960 - margin.left - margin.right,
height = 500 - margin.top - margin.bottom;
// parse the date / time
var parseTime = d3.timeParse("%d-%b-%y");
// set the ranges
var x = d3.scaleTime().range([0, width]);
var y = d3.scaleLinear().range([height, 0]);
// define the line
var valueline = d3.line()
.x(function(d) { return x(d.date); })
.y(function(d) { return y(d.close); });
// append the svg obgect to the body of the page
// appends a 'group' element to 'svg'
// moves the 'group' element to the top left margin
var svg = d3.select("svg")
.attr("width", width + margin.left + margin.right)
.attr("height", height + margin.top + margin.bottom)
.append("g")
.attr("transform",
"translate(" + margin.left + "," + margin.top + ")");
// Get the data
d3.tsv("data.tsv", function(error, data) {
if (error) throw error;
// format the data
data.forEach(function(d) {
d.date = parseTime(d.date);
d.close = +d.close;
});
// Scale the range of the data
x.domain(d3.extent(data, function(d) { return d.date; }));
y.domain([0, d3.max(data, function(d) { return d.close; })]);
// Add the valueline path.
svg.append("path")
.data([data])
.attr("class", "line")
.attr("d", valueline);
// Add the X Axis
svg.append("g")
.attr("transform", "translate(0," + height + ")")
.call(d3.axisBottom(x));
// Add the Y Axis
svg.append("g")
.call(d3.axisLeft(y));
var sites = d3.range(data.length / 20)
.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 = Math.floor(data.length / sites.length);
var points = data.map(function(d) {
return [x(d.date), y(d.close)];
});
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>