30:T405,md` # TSP Art *TSP Art* generates a continuous line drawing from a given image. It first samples points from the image in a way that darker regions have more packed points. Then it solves the [*Traveling Salesman Problem*](https://en.wikipedia.org/wiki/Travelling_salesman_problem) using those points as cities. The resulting tour is a continuous closed path that, when drawn, ressembles the initial picture. The technique was presented by [Kaplan and Bosch in 2005](http://www.cgl.uwaterloo.ca/csk/papers/bridges2005b.html) in a revision of an earlier work by [Bosch and Herman in 2004](http://www.xavierdupre.fr/enseignement/initiation/Continuous%20line%20drawings%20via%20the%20traveling%20salesman%20problem.pdf). This notebook attempts to present the main steps of TSP Art. More information about the topic can be found in [Kaplan's page](http://www.cgl.uwaterloo.ca/csk/projects/tsp/) and around the web. You can also try the nice implementation provided by [StippleGen](https://wiki.evilmadscientist.com/StippleGen).. `31:T87c,reorderPoints = function(samples, image, iterations) { //Cloning the sampled points const result = samples.map(pt => ({ ...pt })); //Storing sampled points in a typed array for use with delaunay const coordinates = new Float64Array(2 * result.length); for (let i = 0; i < result.length; i++) { coordinates[2 * i] = result[i].x; coordinates[2 * i + 1] = result[i].y; } // Current cell centroids const centroids = new Float64Array(coordinates.length); // Weights for centroid translation const weight = new Float64Array(result.length); const delaunay = new d3.Delaunay(coordinates); const voronoi = delaunay.voronoi([0, 0, image.width, image.height]); const regionHasPoints = new Array(result.length); return { [Symbol.iterator]: function*() { for (let iteration = 0; iteration < iterations; iteration++) { centroids.fill(0); weight.fill(0); regionHasPoints.fill(false); // Computing the weight for each centroid for (let y = 0, region = 0; y < image.height; y++) { for (let x = 0; x < image.width; x++) { let color = 1 - levelat(image, x, y) / 255.0; region = delaunay.find(x, y, region); regionHasPoints[region] = true; centroids[2 * region] += color * x; centroids[2 * region + 1] += color * y; weight[region] += color; } } // Moving centroids for (let i = 0; i < weight.length; i++) { if (regionHasPoints[i]) { let wc = weight[i] + 0.0001; coordinates[2 * i] = centroids[2 * i] / wc; coordinates[2 * i + 1] = centroids[2 * i + 1] / wc; } } voronoi.update(); for (let i = 0; i < result.length; i++) { result[i].x = coordinates[2 * i]; result[i].y = coordinates[2 * i + 1]; if (result[i].x === 0 || result[i].y === 0) { console.log( `0 result at index: ${i} x: ${coordinates[2 * i]} y:${ coordinates[2 * i + 1] }` ); } } yield result; } } }; }32:T700,solveTSP = function*(cities) { const ESPILON = -0.001; let distances = (() => { const dist = (a, b) => Math.hypot( cities[a].x - cities[b].x, cities[a].y - cities[b].y ); 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); } }33:[{"id":"b593c268adb15f7f32ace40d424848b5b232a655d4693362608357f6ea26a499e43c449e5c942db03b2e206b07c90681fcd127a76ca6be4231e8ed19a81c0114","href":"https://static.observableusercontent.com/files/b593c268adb15f7f32ace40d424848b5b232a655d4693362608357f6ea26a499e43c449e5c942db03b2e206b07c90681fcd127a76ca6be4231e8ed19a81c0114","name":"2000-points.png","type":"image/png","lastModified":1598200282190.114,"size":76832},{"id":"091d9f89bc1e8e6a57a01301e5590c58a8d59ebaec592c3dcc67ee7910ac9b266ac6167ac7a5c616ebf813222bdef1cbb9a632de1be1c5b652dfc0b176f1d599","href":"https://static.observableusercontent.com/files/091d9f89bc1e8e6a57a01301e5590c58a8d59ebaec592c3dcc67ee7910ac9b266ac6167ac7a5c616ebf813222bdef1cbb9a632de1be1c5b652dfc0b176f1d599","name":"alma-mater-rostro-gray.png","type":"image/png","lastModified":1596709451231.284,"size":22155}] 2e:{"title":"TSP Art","cells":[{"id":0,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":1080,"value":"md`\nAs input we will use the image below. This image is a gray scale picture of the head of the *Alma Mater* statue in front of the [University of Havana](https://en.wikipedia.org/wiki/University_of_Havana).\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":212,"value":"viewof image = {\n //Original image from file\n let original = await FileAttachment(\"alma-mater-rostro-gray.png\").image();\n\n // Scaling the image preserving the size ratio\n const height = 300;\n let scaled = Object.assign(original, {\n height: height,\n width: (original.width * height) / original.height\n });\n\n // Obtaining pixel data\n let data = imgdata(scaled);\n\n // Converting to gray scale\n let gray = rgba2gray(data);\n\n // Obtaining a canvas with the image\n let ctx = new DrawingContext(gray); // ,1); This one at the end is really important!!!\n ctx.image = gray;\n return ctx.canvasShowing(gray);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1093,"value":"md`\nThe first step is to sample points from the image in such a way that points are more concretrated in darker regions.\nWe use a form of [*rejection sampling*](https://en.wikipedia.org/wiki/Rejection_sampling). It works as follows: we take a random pixel from the image, we keep if its intensity is below a random number between 0 and 200, otherwise we reject it. To produce one sample we repeat that process until the point is accepted or we keep it after ${attemptsForOneSample} attempts. In the end we sample ${numberOfSamples} points from the input image.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":266,"value":"viewof samples = {\n const points = [];\n let ctx = new DrawingContext(image);\n\n for (let point of drawSamples(image, numberOfSamples, attemptsForOneSample)) {\n points.push(point);\n ctx.renderPoints(points);\n yield ctx.canvas;\n }\n\n yield ctx.canvasShowing(points);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1099,"value":"numberOfSamples = 500","pinned":false,"hidden":false,"mode":"ojs"},{"id":1103,"value":"attemptsForOneSample = 100","pinned":false,"hidden":false,"mode":"ojs"},{"id":1107,"value":"md`\nThe sampled points need to be reordered to obtain a better looking distribution. We use a weigthed variant of [*Lloyd's algorithm*](https://en.wikipedia.org/wiki/Lloyd's_algorithm). Given the initial set of points, we compute the [*Voronoi's diagram*](). Then we move each point to a weigthed centroid of its Voronoi region. To compute the centroid each point in the region is weighted according to its intensity in the image. Darker points get higher weights making points move around darker regions. The result is shown below.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":923,"value":"viewof points = {\n await visibility();\n if (samples === undefined) return; //Not ready yet\n\n let ctx = new DrawingContext(image);\n let result = [];\n for (let coordinates of reorderPoints(samples, image, reorderIterations)) {\n result = coordinates;\n ctx.renderPoints(coordinates);\n yield ctx.canvas;\n }\n yield ctx.canvasShowing(result);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1128,"value":"reorderIterations = 10","pinned":false,"hidden":false,"mode":"ojs"},{"id":1113,"value":"md`\nThe implementation of these two first steps are based on [Mike Bostock's notebook](@mbostock/voronoi-stippling) which is in turn inspired by [the work of Adrian Secord on Voronoi Stippling](https://www.cs.ubc.ca/labs/imager/tr/2002/secord2002b/secord.2002b.pdf).\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1117,"value":"md`\nThe final step is *just* to solve the Traveling Salesman Problem using the resulting points as cities. The implemententation of this notebook uses a [Hill-climbing heuristic](https://en.wikipedia.org/wiki/Hill_climbing). The process starts with a random solution and finds new candidates using [2-opt swaps](https://en.wikipedia.org/wiki/2-opt). This strategey is good enough to find a local optimum where the drawing line does not cross itself. The result is shown below.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":595,"value":"{\n await visibility();\n if (points === undefined) return; // Not ready yet\n\n const ctx = new DrawingContext(image);\n for (let solution of solveTSP(points)) {\n ctx.clear();\n ctx.begin();\n ctx.moveTo(points[solution[solution.length - 1]]);\n for (let index of solution) {\n ctx.lineTo(points[index]);\n }\n ctx.stroke();\n yield ctx.canvas;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1121,"value":"md`\nAs explained by [Arjan Westerdiep in his website](https://drububu.com/illustration/tsp/index.html) the results can be visually enhanced by drawing thicker segments or larger circles in the darker areas.\nIncreasing the number of points also produce better looking results but makes the notebook slower.\nCheck the precomputed example below using 2000 samples.\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1124,"value":"await FileAttachment(\"2000-points.png\").image()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1180,"value":"md`You can also take a look at a video I produced for the [KTH Continuous Integration Art Hackathon ](https://castor-software-days-2019.github.io/ci_art_hackathon)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1183,"value":"html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":571,"value":"md`## Supporting code`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1147,"value":"md`This section documents the code supporting the notebook.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":575,"value":"md`\n[D3 module](https://observablehq.com/@d3)\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":249,"value":"d3 = require('d3', 'd3-random', 'd3-delaunay')","pinned":false,"hidden":false,"mode":"ojs"},{"id":167,"value":"\nfunction imgdata(image) {\n //(image instanceof HTMLImageElement) {\n const ctx = DOM.context2d(image.width, image.height, 1);\n ctx.drawImage(image, 0, 0, image.width, image.height);\n return ctx.getImageData(0, 0, image.width, image.height);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":757,"value":"md`\nObtains an instance of \\`ImageData\\` holding the information about pixels and dimensions from an HTML image element.\n\n**Parameters:**\n- \\`image\\`: An instance of \\`HTMLImageImageElement\\`.\n\n**Returns:**\n An instance of \\`ImageData\\` matching the information from \\`image\\`.\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":175,"value":"function rgba2gray(rgba) {\n let gray = new ImageData(rgba.data, rgba.width);\n for (let i = 0; i < gray.data.length; i += 4) {\n gray.data[i] = gray.data[i + 1] = gray.data[i + 2] =\n 0.2126 * gray.data[i] +\n 0.7152 * gray.data[i + 1] +\n 0.0722 * gray.data[i + 2];\n }\n return gray;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":770,"value":"md`\nConverts an \\`ImageData\\` representing a RGBA image to the corresponding gray scale image.\n\n**Parameters:**\n- \\`rgba\\` An instance of \\`ImageData\\`.\n\n**Returns:**\n- An instance of \\`ImageData\\` with gray scaled pixels, i.e. all color channels have the same value.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":499,"value":"function levelat(image, x, y) {\n return image.data[4 * (y * image.width + x)];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":808,"value":"md`\nObtains the intensity value of the input image at the pixel in row \\`x\\`, column \\`y\\`.\n\n**Parameters:**\n- \\`x\\`: The row index.\n- \\`y\\`: The column index.\n\n**Returns:**\nAn integer between 0 and 255 representing the intensity value.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":845,"value":"class DrawingContext {\n constructor(size) {\n this.width = size.width;\n this.height = size.height;\n this.ctx = DOM.context2d(this.width, this.height, 1);\n this.ctx.lineWidth = 1;\n }\n\n begin() {\n this.ctx.beginPath();\n }\n\n clear() {\n this.ctx.clearRect(0, 0, this.width, this.height);\n }\n\n moveTo(pt) {\n this.ctx.moveTo(pt.x, pt.y);\n }\n\n lineTo(pt) {\n this.ctx.lineTo(pt.x, pt.y);\n }\n\n dot(pt, r = 2) {\n this.ctx.moveTo(pt.x + r, pt.y);\n this.ctx.arc(pt.x, pt.y, r, 0, 2 * Math.PI);\n }\n\n renderPoints(points) {\n this.clear();\n this.begin();\n for (let pt of points) {\n this.dot(pt);\n }\n this.fill();\n }\n\n fill() {\n this.ctx.fill();\n }\n\n stroke() {\n this.ctx.stroke();\n }\n\n get canvas() {\n return this.ctx.canvas;\n }\n\n canvasShowing(data) {\n let canvas = this.ctx.canvas;\n if (data !== undefined) {\n canvas.value = data;\n }\n return canvas;\n }\n\n set image(img) {\n this.ctx.putImageData(img, 0, 0);\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1133,"value":"md`A wrapper for \\`CanvasRenderingContext2D\\` to reduce boilerplate code.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":247,"value":"function drawSamples(image, count = 500, attempts = 100) {\n const rndpoint = () => {\n return {\n x: Math.floor(Math.random() * image.width),\n y: Math.floor(Math.random() * image.height)\n };\n };\n\n return {\n [Symbol.iterator]: function*() {\n for (let i = 0; i < count; i++) {\n let point = rndpoint();\n for (\n let att = 0;\n att < attempts &&\n 200 * Math.random() < levelat(image, point.x, point.y);\n att++\n ) {\n point = rndpoint();\n }\n yield point;\n }\n }\n };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1138,"value":"md`\nSamples a set of points from a gray scale image, favoring pixels from darker regions.\n\n**Parameters:**\n- \\`image\\`: The image to sample points from.\n- \\`count\\`: Number of samples. Default to 500.\n- \\`attempts\\`: Number of attempts to produce one sample.\n\n**Returns:**\nAn array of points. Each point is an \\`{x, y}\\` object.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":916,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":1141,"value":"md`\nReorders a given array of points selected from one image using a weighted Lloyd's algorithms.\n\n**Parameters:**\n- \\`samples\\`: The initial array of points.\n- \\`image\\`: The image used to sample the points and to compute their weights.\n- \\`iterations\\`: The number of iterations in the reordering.\n\n**Returns:**\nAn array of points. Each point is an \\`{x, y}\\` object.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":568,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":1145,"value":"md`\nFinds a local optimum solution of the TSP problem given a set of cities. It starts with a random solution and finds next candidates using 2-opt swaps.\n\n**Parameters:**\n- \\`cities\\`: An array of \\`{x, y}\\` objects.\n\n**Returns:**\nThe solution encoded as an array of integers. Each integer is the position of the city in the array given as input.\n`","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}