Imagine we have a set of N artworks, each randomly "closest" (connected by an edge) to n other artworks. The algorithm works as follows:
| <!DOCTYPE html> | |
| <meta charset="utf-8"> | |
| <style> | |
| </style> | |
| <body> | |
| <script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.6/d3.min.js"></script> | |
| <script> | |
| var width = 960, | |
| height = 500, | |
| n = 50, // number of points | |
| s = 5, // number of neighbors per point | |
| delay = 500, // | |
| beam_ix = 0, // start with the first node | |
| neighbor_ixs = undefined; // or neighbors | |
| var svg = d3.select("body").append("svg") | |
| .attr("width", width) | |
| .attr("height", height); | |
| var particles = new Array(n); | |
| for (var i = 0; i < n; ++i) { | |
| particles[i] = { | |
| x: width * Math.random(), | |
| y: height * Math.random(), | |
| r: 3 //height * .01 * Math.random() | |
| }; | |
| } | |
| // node and edge selections | |
| var nodes = svg.selectAll(".dot") | |
| .data(particles); | |
| var edges = svg.selectAll(".edge") | |
| .data(particles); | |
| // choose initial neighbors | |
| var choices = d3.range(particles.length); | |
| var neighbors = particles.map(function(el, ix){ | |
| return d3.shuffle(choices).slice(0, s); | |
| }) | |
| function initialize(j){ | |
| nodes.enter() | |
| .append("circle") | |
| .attr("cx", function(d){ return d.x; }) | |
| .attr("cy", function(d){ return d.y; }) | |
| .attr("r", function(d){ return d.r; }) | |
| d3.range(s).forEach(function(_el, j){ | |
| edges.enter().append("line") | |
| .attr("x1", function(d, ix){ return d.x }) | |
| .attr("y1", function(d, ix){ return d.y }) | |
| .attr("x2", function(d, ix){ return lookup(ix, j).x }) | |
| .attr("y2", function(d, ix){ return lookup(ix, j).y }) | |
| .attr("stroke", "grey") | |
| .classed('edge_' + j, true); | |
| }) | |
| } | |
| function update_neighbors(){ | |
| var first_degree_ixs, | |
| neighbors_as_particles, | |
| distances, | |
| distance_ixs, | |
| closest; | |
| beam_ix = (beam_ix >= n - 1) ? 0 : beam_ix + 1; | |
| // grab the neighbors of the node in the beam | |
| first_degree_ixs = neighbors[beam_ix]; | |
| // grab the neighbors of those neighbors, removing | |
| // any that might be duplicates or the node itself. | |
| // (merge flattens an array of arrays) | |
| neighbor_ixs = uniq_fast(d3.merge( | |
| first_degree_ixs.map(function(el){ | |
| return neighbors[el] } | |
| )) | |
| .concat(first_degree_ixs)); | |
| neighbors_as_particles = neighbor_ixs.map(function(el){ return particles[el] }) | |
| distances = neighbors_as_particles.map(function(p) { | |
| return euclideanDistance(p, particles[beam_ix]) | |
| }); | |
| distance_ixs = d3.range(distances.length); | |
| distance_ixs.sort(function(a,b){ | |
| return distances[a] < distances[b] ? 1 : -1 } | |
| ); | |
| closest = distance_ixs.slice(0, s); | |
| neighbors[beam_ix] = closest.map(function(i) { return neighbor_ixs[i] }) | |
| } | |
| function update(){ | |
| // color nodes | |
| nodes.transition().duration(delay) | |
| .attr("r", function(d, ix){ return (ix == beam_ix) ? 20 : | |
| (neighbor_ixs.indexOf(ix) > -1) ? 10 : 3 }) | |
| .attr("fill", function(d, ix){ return (ix == beam_ix) ? "red" : "grey" }) | |
| // move edges | |
| d3.range(s).forEach(function(el, j){ | |
| d3.selectAll('.edge_' + j).transition().duration(delay) | |
| .attr("x2", function(d, ix){ return lookup(ix, j).x }) | |
| .attr("y2", function(d, ix){ return lookup(ix, j).y }) | |
| }) | |
| } | |
| function update_step(){ | |
| update_neighbors(); | |
| update(); | |
| setTimeout(update_step, delay); | |
| } | |
| initialize(); | |
| setTimeout(update_step, 500); | |
| // helpers | |
| function lookup(i, j){ | |
| return particles[neighbors[i][j]] | |
| } | |
| function euclideanDistance(p1, p2) { | |
| sum_of_squares = 0; | |
| sum_of_squares += Math.pow(p1.x - p2.x, 2); | |
| sum_of_squares += Math.pow(p1.y - p2.y, 2); | |
| return 1.0 / (1 + Math.sqrt(sum_of_squares)); | |
| } | |
| function uniq_fast(a) { | |
| var seen = {}; | |
| var out = []; | |
| var len = a.length; | |
| var j = 0; | |
| for(var i = 0; i < len; i++) { | |
| var item = a[i]; | |
| if(seen[item] !== 1) { | |
| seen[item] = 1; | |
| out[j++] = item; | |
| } | |
| } | |
| return out; | |
| } | |
| </script> |