Published
Edited
Apr 28, 2019
Importers
20 stars
Hello, A5Chandrupatla’s root-finding methodSidi’s root-finding methodRegular numbersDruidJS workerNatural breaksDistance to a segmentRay out of a convex hullWord Tour: 40k words and their friendsHello, @thi.ng/grid-iteratorsHead/tail breaksPseudo-blue noise shaderHow fast does walk-on-spheres converge?AoC 12: shortest path under constraintsKDE estimationPlot: Correlation heatmapPoisson Finish 2Poisson disk sampling functionsWoS with transportSimple and surprising sortLocal medianTime series topological subsamplingUnion-FindLevel set experiment 1Mean value coordinatesPoisson potentialMiddle-squareWorld of squares (spherical)World of squaresLargest Inscribed SquareHello, PyWaveletsGeothmetic meandianHello, Reorder.jsGeometric MedianImage FFTTransport to a mapDisc TransportTP3: Power Diagram and Semi-Discrete Optimal TransportThe blue waveHello, genetic-jsSliced Optimal TransportDruidJSSelf-Organizing Maps meet DelaunayHello, polygon-clippingseedrandom, minimalWalk on Spheres 2Walk on SpheresHello, AutoencoderKaprekar’s numberVoronoiMap2DHello, ccwt.jsPolygon TriangulationQuantile.invert?Linear congruential generatorHue blurNeedle in a haystackMoving average blurApollo 11 implementation of trigonometric functions, by Margaret H. Hamilton (march 1969)2D curves intersectionThe 2D approximate Newton-Raphson methodInverting Lee’s Tetrahedral projectionLinde–Buzo–Gray stipplingMean shift clustering with kd-tree2D point distributionsShortest pathKahan SummationHello, delatinDijkstra’s algorithm in gpu.jsLloyd’s relaxation on a graphManhattan DiameterManhattan VoronoiMobility landscapes — an introductionDijkstra’s shortest-path treeH3 odditiesProtein MatrixConvex Spectral WeightsSort stuff by similarityKrigingDelaunay.findTrianglen-dimensions binning?UMAP-o-MaticMNIST & UMAP-jsHello UMAP-jsMean shift clusteringLevenshtein transitionRd quasi-random sequencesAutomated label placement (countries)Phyllotaxis explainedMotionrugsPlanar hull (Andrew’s monotone chain algorithm)South Africa’s medial axisTravelling salesperson approximation with t-SNEDistance to shoreWorkerngraph: pagerank, louvain…t-SNE VoronoiCloud ContoursCircular function drawingKruskal MazeMyceliumTravelling salesperson approximation on the globe, with t-SNEtsne.jstsne.js & worker
Travelling with a self-organizing map
points = (replay,
Array.from({ length: 300 }, (_, i) =>
Object.assign([Math.random(), Math.random()], { index: i })
))
order = {
const D = d3.Delaunay.from(som.neurons);
const order = points.map(d => D.find(d[0], d[1]));
// return the new order — if something goes wrong (we receive -1), use the previous value
return order[0] === -1 ? this : order;
/*
// Quadtree version
const D = d3
.quadtree()
.addAll(som.neurons.map((d, i) => Object.assign(d, { index: i })));
const order = points.map(d => D.find(d[0], d[1]).index);
return order[0] === -1 ? this : order;
*/
}
som = {
const tsp = new TravelingSalesman();
tsp.maxCycles = 400;
tsp.createFirstNeuron();
tsp.cities = points.map((d, i) => ({ x: d[0], y: d[1] }));
var done, pos;
do {
done = tsp.surveyRun();
let n = tsp.neurons.start;
pos = [[n.x, n.y]];
for (let i = 0; i < tsp.neurons.length; i++) {
n = n.right;
pos.push([n.x, n.y]);
}
if (tsp.cycle > 3)
yield {
cycle: tsp.cycle,
length: tsp.neurons.tourLength(),
neurons: pos
};
} while (!done && tsp.cycle < tsp.maxCycles);
yield {
cycle: tsp.cycle,
length: tsp.neurons.tourLength(),
neurons: pos
};
}
TravelingSalesman = {
// copy-pasted from github.com/kifj/tsp-js
const $ = "we don't jQuery and a lot of this code is just ignored";
/* Sample of a city */
function Sample() {
this.x = 0.0;
this.y = 0.0;
}
Sample.prototype.draw = function(canvas) {
var centerX = this.x * canvas.width;
var centerY = canvas.height - this.y * canvas.height;
var ctx = canvas.ctx;
ctx.fillStyle = "#C06060";
ctx.beginPath();
ctx.arc(centerX, centerY, 3, 0, Math.PI * 2, true);
ctx.closePath();
ctx.fill();
};
/* a node in the neural network */
function Node(x, y) {
this.x = x;
this.y = y;
this.right = this;
this.left = this;
this.life = 3;
this.inhibitation = 0;
this.isWinner = 0;
}
/* the distance of the euklidian points */
Node.prototype.potential = function(sample) {
return (
(sample.x - this.x) * (sample.x - this.x) +
(sample.y - this.y) * (sample.y - this.y)
);
};
/* moves a single node in direction to the sample */
Node.prototype.move = function(city, value) {
this.x += value * (city.x - this.x);
this.y += value * (city.y - this.y);
};
/* computes the number of nodes between the to nodes on the ring */
Node.prototype.distance = function(other, length) {
var right = 0;
var left = 0;
var current = other;
while (current != this) {
current = current.left;
left++;
}
right = length - left;
return left < right ? left : right;
};
Node.prototype.draw = function(canvas) {
var centerX = this.x * canvas.width + 0.5;
var centerY = canvas.height - this.y * canvas.height + 0.5;
var ctx = canvas.ctx;
ctx.fillStyle = "#208020";
ctx.fillRect(centerX, centerY, 1, 1);
if (this.right != null) {
ctx.lineTo(
this.right.x * canvas.width + 0.5,
canvas.height - this.right.y * canvas.height + 0.5
);
}
};
/* the neural network as a ring of neurons */
function Ring(start) {
this.start = start;
this.length = 1;
}
/* moves all nodes to in direction of the sample */
Ring.prototype.moveAllNodes = function(city, gain) {
var current = this.start;
var best = this.findMinimum(city);
for (var i = 0; i < this.length; i++) {
current.move(city, this.f(gain, best.distance(current, this.length)));
current = current.right;
}
};
/* finds the node with the least distance to the sample */
Ring.prototype.findMinimum = function(city) {
var actual;
var node = this.start;
var best = node;
var min = node.potential(city);
for (var i = 1; i < this.length; i++) {
node = node.right;
actual = node.potential(city);
if (actual < min) {
min = actual;
best = node;
}
}
best.isWinner++;
return best;
};
/* deletes a node */
Ring.prototype.deleteNode = function(node) {
var previous = node.left;
var next = node.right;
if (previous != null) {
previous.right = next;
}
if (next != null) {
next.left = previous;
}
if (next == node) {
next = null;
}
if (this.start == node) {
this.start = next;
}
this.length--;
};
/* a node is duplicated & inserted into the ring */
Ring.prototype.duplicateNode = function(node) {
var newNode = new Node(node.x, node.y);
var next = node.left;
next.right = newNode;
node.left = newNode;
node.inhibitation = 1;
newNode.left = next;
newNode.right = node;
newNode.inhibitation = 1;
this.length++;
};
/* length of tour */
Ring.prototype.tourLength = function() {
var dist = 0.0;
var current = this.start;
var previous = current.left;
for (var i = 0; i < this.length; i++) {
dist += Math.sqrt(
(current.x - previous.x) * (current.x - previous.x) +
(current.y - previous.y) * (current.y - previous.y)
);
current = previous;
previous = previous.left;
}
return dist;
};
Ring.prototype.f = function(gain, n) {
return 0.70710678 * Math.exp(-(n * n) / (gain * gain));
};
/* the simulator containing all the data */
function TravelingSalesman() {
this.N = 100; /* Number of cities. */
this.cycle = 0; /* Number of complete survey done */
this.maxCycles = 1000; /* Number of complete suerveys */
this.cities = null; /* the samples */
this.neurons = null; /* the neurons */
this.alpha = 0.05; /* learning rate */
this.gain = 50.0; /* gain */
this.lastLength = null; /* length of tour */
this.isRunning = false;
this.update = 5; /* screen update */
}
/* creates the first node (ring) */
TravelingSalesman.prototype.createFirstNeuron = function() {
var start = new Node(0.5, 0.5);
this.neurons = new Ring(start);
};
/* deletes all nodes */
TravelingSalesman.prototype.deleteAllNeurons = function() {
if (this.neurons != null) {
while (this.neurons.start != null) {
this.neurons.deleteNode(this.neurons.start);
}
this.neurons = null;
}
};
/* prints positions of cities & nodes */
TravelingSalesman.prototype.print = function() {
console.log(
"TSP: N= " +
this.N +
", cycle=" +
this.cycle +
", lastLength=" +
this.lastLength
);
for (var i = 0; i < this.cities.length; i++) {
var c = this.cities[i];
console.log("City: " + i + " (" + c.x + "," + c.y + ")");
}
var n = this.neurons.start;
for (i = 0; i < this.neurons.length; i++) {
console.log("Node: " + i + "(" + n.x + "," + n.y + ")");
n = n.right;
}
};
/* creates & displaces randomly a given number of cities, returns the first */
TravelingSalesman.prototype.createRandomCities = function() {
this.cities = new Array(this.N);
for (var i = 0; i < this.N; i++) {
var c = new Sample();
c.x = Math.random();
c.y = Math.random();
this.cities[i] = c;
}
};
TravelingSalesman.prototype.stop = function() {
this.isRunning = false;
this.repaint();
this.cities = null;
this.deleteAllNeurons();
};
TravelingSalesman.prototype.start = function() {
this.stop();
this.init();
this.isRunning = true;
this.run();
};
TravelingSalesman.prototype.init = function() {
this.cycle = 0;
this.lastLength = null;
this.createFirstNeuron();
this.createRandomCities();
this.canvas = new Canvas(document.getElementById("canvas"));
this.repaint();
};
TravelingSalesman.prototype.run = function() {
if (this.neurons != null) {
if (this.cycle < this.maxCycles && this.isRunning) {
var done = this.surveyRun();
if (!done) {
var self = this;
window.setInterval(function() {
self.run();
}, 100);
return;
}
}
if (this.isRunning) {
//this.print();
this.isRunning = false;
this.repaint();
}
}
};
/* one cycle in the simulation */
TravelingSalesman.prototype.surveyRun = function() {
var done = false;
if (this.neurons != null) {
for (var i = 0; i < this.cities.length; i++) {
this.neurons.moveAllNodes(this.cities[i], this.gain);
}
}
this.surveyFinish();
this.gain = this.gain * (1 - this.alpha);
if (this.cycle++ % this.update == 0) {
var length = this.neurons.tourLength();
//this.print();
this.repaint();
if (length == this.lastLength) {
done = true;
} else {
this.lastLength = length;
}
}
return done;
};
/* after moving creating & deleting is done */
TravelingSalesman.prototype.surveyFinish = function() {
if (this.neurons == null) {
return;
}
var node = this.neurons.start;
for (var i = 0; i < this.neurons.length; i++) {
node.inhibitation = 0;
switch (node.isWinner) {
case 0:
node.life--;
if (node.life == 0) {
this.neurons.deleteNode(node);
}
break;
case 1:
node.life = 3;
break;
default:
node.life = 3;
this.neurons.duplicateNode(node);
break;
}
node.isWinner = 0;
node = node.right;
}
};
TravelingSalesman.prototype.repaint = function() {
if (!this.canvas) {
return;
}
this.canvas.ctx.clearRect(0, 0, this.canvas.width, this.canvas.height);
if (this.cities) {
for (var i = 0; i < this.cities.length; i++) {
var c = this.cities[i];
c.draw(this.canvas);
}
}
if (this.neurons) {
this.canvas.ctx.strokeStyle = "#80D080";
this.canvas.ctx.beginPath();
var n = this.neurons.start;
this.canvas.ctx.moveTo(
n.x * this.canvas.width + 0.5,
this.canvas.height - n.y * this.canvas.height + 0.5
);
for (i = 0; i < this.neurons.length; i++) {
n.draw(this.canvas);
n = n.right;
}
this.canvas.ctx.lineWidth = 1;
this.canvas.ctx.stroke();
this.canvas.ctx.closePath();
}
$("#cycle").val(this.cycle);
$("#length").val(this.lastLength);
$("#done").prop("checked", !this.isRunning);
if (this.isRunning) {
$("#run").attr("disabled", "disabled");
$("#stop").removeAttr("disabled");
} else {
$("#stop").attr("disabled", "disabled");
$("#run").removeAttr("disabled");
}
};
TravelingSalesman.prototype.setupForm = function() {
var self = this;
$("#cities").val(this.N);
$("#maxCycles").val(this.maxCycles);
$("#alpha").val(this.alpha);
$("#gain").val(this.gain);
$("#run").bind("click", function(event) {
self.N = $("#cities").val();
self.maxCycles = $("#maxCycles").val();
self.alpha = $("#alpha").val();
self.gain = $("#gain").val();
self.start();
});
$("#stop").bind("click", function(event) {
self.stop();
});
};
function Canvas(elem) {
this.elem = elem;
this.ctx = elem.getContext("2d");
this.height = elem.height;
this.width = elem.width;
}
return TravelingSalesman;
}
d3 = require("d3-scale@2", "d3-geo@1", "d3-delaunay@4")
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
