31:T51c,a={ await visibility(); var pal = ["#8ecae6","#73bfdc","#58b4d1","#219ebc","#126782", "#023047","#ffb703","#fd9e02","#fb8500","#fb9017"] const w = width,h = width; const context = DOM.context2d(w, h); context.fillStyle = "#f2f9fc"; context.fillRect(0,0,w,h);context.fillRect(0,0,w,h); clusters2.sort(function (a, b) { return ((a[0]**2+a[1]**2) - (b[0]**2+b[1]**2)); }); for (var cluster of clusters2) { var points = cluster.points; var cities = points.map(function(z) {return {x: z[0],y: z[1]};}); var path = solveTSP(cities); var myColor = pal[Math.floor(Math.random() * pal.length)]; for (var jj=2; jj { const dist = (a, b) => Math.sqrt( Math.pow(cities[a].x - cities[b].x, 2) + Math.pow(cities[a].y - cities[b].y, 2) ); let result = []; for (let i = 0; i < cities.length; i++) { let row = new Float32Array(cities.length); for (let j = 0; j < cities.length; j++) { row[j] = dist(i, j); } result.push(row); } return result; })(); function firstTwoOptImprovement(tour) { const next = current => (current + 1) % tour.length; const pick = d3.randomInt(tour.length - 2); function delta(i, j) { let ni = tour[next(i)]; let nj = tour[next(j)]; let ci = tour[i]; let cj = tour[j]; return ( distances[ci][cj] + distances[ni][nj] - distances[ci][ni] - distances[cj][nj] ); } function move(from, to) { let result = [...tour]; let count = to - from; for (let i = 0; i < count; i++) { result[from + 1 + i] = tour[to - i]; } return result; } for ( let times = 0, start = pick(); times < tour.length; times++, start = next(start) ) { for (let end = start + 2; end < tour.length; end++) { let variation = delta(start, end); if (variation < ESPILON) { return { tour: move(start, end), delta: variation }; } } } return { tour: tour, delta: 0 }; } const random = () => d3.shuffle(d3.range(cities.length)); let current = { tour: random(), delta: Number.MIN_SAFE_INTEGER }; // yield current.tour; console.log("delta " + current.delta); while (current.delta < 0) { //yield current.tour; current = firstTwoOptImprovement(current.tour); } return(current.tour); }33:[] 2f:{"title":"Snakes on a Cartesian Plane 🐍","cells":[{"id":0,"value":"md`\n# Snakes on a Cartesian Plane 🐍 \n## Genuary 2021: Day 1 -- Triple Nested Loop\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":7,"value":"md`I used this notebook to create my entry for [Day 1](https://genuary2021.github.io/prompts) of [Genuary](https://genuary2021.github.io/). _(See my [collection of entries here](https://observablehq.com/collection/@mattdzugan/genuary-2021))_\n\nThe prompt for day 1 is: \\`Triple Nested Loop\\`. Browse the [#genuary2021 hashtag on twitter](https://twitter.com/hashtag/genuary2021?src=hashtag_click) to see some of the fantastic entries from other people!\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":14,"value":"md`Here's a bit of pseudo-code that highlights the **triple nested loop**.\n\\`\\`\\`\ngenerate random points\ncluster points into K groups\nFOR each clustered group\n solve TSP to connect points into a path\n FOR each pair of consecutive segments within a path\n distribute both segments with N points\n FOR each of the N point-pairs\n connect them with a line\n\\`\\`\\`\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":272,"value":"viewof numSankes = slider({\n min: 5, \n max: 100, \n step: 1, \n value: 80, \n title: \"Number of Sankes\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":271,"value":"viewof avgSnakeLen = slider({\n min: 5, \n max: 30, \n step: 1, \n value: 20, \n title: \"Avg # of Segments per Snake\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":60,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":250,"value":"md` ### Generation of sample points and cluster centroids:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":269,"value":"rad = Math.sqrt(width*width/(Math.PI*numSankes*avgSnakeLen*0.41))","pinned":false,"hidden":false,"mode":"ojs"},{"id":34,"value":"samples = [...poissonDiscSampler(width, width, rad)]","pinned":false,"hidden":false,"mode":"ojs"},{"id":43,"value":"clusters2 = {\n var p = [];\n for (var ii = 0; ii < numSankes; ii++) {\n p.push([Math.random() * width, Math.random() * width]);\n }\n assign(p, samples);\n return p;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":261,"value":"md`### import various utilities:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":266,"value":"import {slider} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":19,"value":"import { poissonDiscSampler } from \"@toja/pen-and-ink-stipple-effect\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":29,"value":"import {\n kmeans,\n assign\n} from \"@romaklimenko/finding-palettes-of-dominant-colors-with-the-k-means-cluste\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":111,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":114,"value":"d3 = require('d3', 'd3-random', 'd3-delaunay')","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}