Capacity Constrained Point Distribution on Data (line chart)

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>

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