Ported to javascript by Philippe Rivière, from the C++ implementation found at https://github.com/yongyanghz/LAPJV-algorithm-c
See Fil/lap-jv for details, and a simpler example.
xxxxxxxxxx
<head>
<meta charset="utf-8">
<script src="https://d3js.org/d3.v4.min.js"></script>
<style>
body { margin:0;position:fixed;top:0;right:0;bottom:0;left:0; }
</style>
</head>
<body>
<script>
// Feel free to change or delete any of the code you see in this editor!
var svg = d3.select("body").append("svg")
.attr("width", 960)
.attr("height", 500)
const m = 40, n = m * m, w = Math.ceil(480/m);
// const data = d3.range(n).map(k => [Math.floor(100 * m * (2 + Math.cos( k ))/4)/100, Math.floor(100 * m * (2 + Math.sin(k))/4)/100]);
const data = d3.range(n).map(k => [m * Math.random(), m * Math.random()]);
// const data = d3.range(n).map(k => [m * (1 + Math.cos(k))/2, m * (1 + Math.sin(k))/2]);
// const data = d3.range(n).map(k => { const i = k % m, j = (k-i)/m; return [i + Math.random(),j + Math.random()]; });
data.map(d => d.color = d3.rgb(Math.random()*255, Math.random()*255, Math.random()*255));
svg.selectAll('circle')
.data(data)
.enter()
.append('circle')
.attr('r', 3);
svg.selectAll('circle')
.attr('cx', d => w * d[0])
.attr('cy', d => w * d[1])
.attr('fill', d => d.color);
createWorker('worker.js', (worker) => {
const start = performance.now();
worker.postMessage({
m: m,
data: data,
});
worker.onmessage = function (e) {
if (e.data.assign) {
console.log(n + ': ' + Math.ceil(performance.now() - start) + 'ms')
draw(e.data.assign);
}
}
});
function draw(res) {
res.col.map((c, k) => {
const i = k % m, j = (k-i)/m;
data[c].i = i;
data[c].j = j;
});
svg.selectAll('line')
.data(data)
.enter()
.append('line')
.attr('x1', d => w * d[0])
.attr('y1', d => w * d[1])
.attr('x2', d => w * d[0])
.attr('y2', d => w * d[1])
.attr('stroke', d => d.color)
.attr('opacity', 0.8)
.transition()
.duration(1500)
.attr('x2', d => w/2 + w * d.i)
.attr('y2', d => w/2 + w * d.j)
;
setTimeout(function() {
svg.selectAll('circle')
.transition()
.duration(500)
.attr('cx', d => w/2 + w * d.i)
.attr('cy', d => w/2 + w * d.j);
if (false) svg.selectAll('line')
.transition()
.attr('x1', d => w/2 + w * d.i)
.attr('y1', d => w/2 + w * d.j)
.duration(500)
}, 1500);
}
function createWorker(s, cb) {
const worker = new Worker(window.URL.createObjectURL(new Blob([`
importScripts('https://raw.githack.com/Fil/lap-jv/master/lap.js');
self.onmessage = function(e){
const m = e.data.m,
n = m * m,
data = e.data.data;
const costs = function(a, k) {
const d = data[a],
i = k % m,
j = (k-i)/m;
const dx = d[0] - i - 0.5, dy = d[1] - j - 0.5;
return dx * dx + dy * dy;
};
self.postMessage({
assign: lap(n, costs)
});
};`], {
type: "text/javascript"
})));
if (typeof cb == 'function') {
cb(worker);
}
}
</script>
</body>
https://d3js.org/d3.v4.min.js