31:T5d7,relax = function* (lumData, density, nbIterations) { const { values, width, height } = lumData; const nb = Math.floor(width * height * density); const coords = new Float64Array(nb * 2); for (let index = 0; index < nb * 2; ) { let nb = 0; let x, y; do { [x, y] = [randInt(width), randInt(height)]; } while (values[y * width + x] < Math.random() && nb++ < 30); coords[index++] = x; coords[index++] = y; } const delaunay = new Delaunay(coords); const voronoi = delaunay.voronoi([0, 0, width, height]); const c = new Float64Array(nb * 3); for (let k = 0; k < nbIterations; ++k) { // Compute the weighted centroid for each Voronoi cell. c.fill(0); let index = 0; for (const [w, x, y] of iterateArray2D(values, width)) { const [i, j] = [x + 0.5, y + 0.5]; index = delaunay.find(i, j, index); const ic = index * 3; c[ic] += w; c[ic + 1] += w * i; c[ic + 2] += w * j; } // Relax the diagram by moving points to the weighted centroid. // Wiggle the points a little bit so they don’t get stuck. const w = Math.pow(k + 1, -0.8) * 10; const relax = (c0, c1) => c0 + (c1 - c0) * 1.8 + (Math.random() - 0.5) * w; let i = 0; for (const [s, cx, cy] of arrGen(c, 3)) { if (s) { coords[i] = relax(coords[i], cx / s); coords[i + 1] = relax(coords[i + 1], cy / s); } i += 2; } yield delaunay; voronoi.update(); } yield delaunay; }32:T458,viewof points = { const { width, height } = lumData; const context = DOM.context2d(width, height); const view = context.canvas; yield view; let frame, last; const renderPoints = (delaunay, radius) => { context.fillStyle = "#fff"; context.fillRect(0, 0, width, height); context.beginPath(); delaunay.renderPoints(context, radius); context.fillStyle = "#000"; context.fill(); }; const iter = relax(lumData, dotsDensity, nbIterations); (function step() { const { value, done } = iter.next(); if (!done) { renderPoints((last = value), viewof dotsRadius.value); frame = requestAnimationFrame(step); } else { view.value = last.points; view.dispatchEvent(new CustomEvent("input")); } })(); const onInput = (e) => { e.stopPropagation(); // necessary to avoid triggering cell clients (why ?) renderPoints(last, viewof dotsRadius.value); }; viewof dotsRadius.addEventListener("input", onInput); invalidation.then(() => { cancelAnimationFrame(frame); viewof dotsRadius.removeEventListener("input", onInput); }); }33:T9fe,{ const { width, height } = lumData; const H = 500; const v = viewer([H * (width / height), H], true); const params = () => ({ "stroke-width": viewof strokeWidth.value, margin: 0, viewBox: `0 0 ${width} ${height}` }); const traceLine = (points, [min, max]) => { const p = Plot(); let i = 0; let [x1, y1] = points[i++]; p.move(x1, y1); while (i < points.length) { const [x2, y2] = points[i++]; const [dx, dy] = [x2 - x1, y2 - y1]; const length = Math.hypot(dx, dy); if (length > min && length < max) p.draw(dx, dy); else p.move(dx, dy); [x1, y1] = [x2, y2]; } return p; }; const traceLines = (lines, length) => Plot().insert(...lines.map((line) => traceLine(line, length))); yield v; const rec = function* (points, [xmin, xmax], [ymin, ymax], acc) { if (points.length < 2) return; else if (points.length < dotThreshold) { let last; let iters = 20; for (const sorted of order_by_distance(points)) { yield acc.concat([(last = sorted)]); if (--iters == 0) break; // security } acc.push(last); } else { const [dx, dy] = [xmax - xmin, ymax - ymin]; if (dx > dy) { const xs = xmin + dx / 2; const [h1, h2] = split(points, ([x, y]) => x < xs); yield* rec(h1, [xmin, xs], [ymin, ymax], acc); yield* rec(h2, [xs, xmax], [ymin, ymax], acc); } else { const ys = ymin + dy / 2; const [h1, h2] = split(points, ([x, y]) => y < ys); yield* rec(h1, [xmin, xmax], [ymin, ys], acc); yield* rec(h2, [xmin, xmax], [ys, ymax], acc); } } }; const pts = arrGen(points, 2) .filter(([x, y]) => x >= 0 && y >= 0 && x < width && y < height) .toArray(); const iter = rec(pts, [0, width], [0, height], []); let frame, last; (function step() { const { value, done } = iter.next(); if (!done) { v.view(traceLines((last = value), viewof segmentLength.value), params()); frame = requestAnimationFrame(step); } })(); const onInput = (e) => { e.stopPropagation(); // important to avoid triggering cell clients v.view(traceLines(last, viewof segmentLength.value), params()); }; viewof strokeWidth.addEventListener("input", onInput); viewof segmentLength.addEventListener("input", onInput); invalidation.then(() => { cancelAnimationFrame(frame); viewof strokeWidth.removeEventListener("input", onInput); viewof segmentLength.removeEventListener("input", onInput); }); }34:[{"id":"813eeb6380eecc26fb4cd5d423df09e9d75c8d830eeae2d537de73954d48b42326328018cbb6542948f50693024223fe4d283c26ba45b63f05aa2a9ed74a67e3","href":"https://static.observableusercontent.com/files/813eeb6380eecc26fb4cd5d423df09e9d75c8d830eeae2d537de73954d48b42326328018cbb6542948f50693024223fe4d283c26ba45b63f05aa2a9ed74a67e3","name":"mad.jpg","type":"image/jpeg","lastModified":1781305016741.314,"size":59389}] 2f:{"title":"Bitmap to lines using distribution relaxation and TSP","cells":[{"id":0,"value":"# Bitmap to lines using distribution relaxation and TSP","pinned":false,"hidden":false,"mode":"md"},{"id":480,"value":"When feeding a pen plotter with your vector obsessions, you sometimes have the weird idea to render bitmap images. Plotter are obviously not made for this, but eh. Some desktop applications (e.g. [DrawingBot](https://drawingbotv3.com), [linedraw](https://github.com/LingDong-/linedraw), [plottter](https://github.com/pywkt/plottter)) are very, very good at this, but I was wondering if a simple version could be implemented as a new tool in [my plotter toolbox](https://observablehq.com/@ehouais/pivot-format-for-plotter-experiments).","pinned":false,"hidden":false,"mode":"md"},{"id":498,"value":"Of course you can use [smart hatching](https://observablehq.com/@ehouais/bitmap-image-to-plotter-svg), but hatching is not fun ([it is](https://observablehq.com/@ehouais/bitmap-to-lines-using-marching-squares-and-hatching), actually), and the slightest imperfection in a tightly hatched zone triggers my undiagnosed ASD mind.","pinned":false,"hidden":false,"mode":"md"},{"id":488,"value":"Others have already been wandering on these paths, and [@jonhelfman](https://observablehq.com/@jonhelfman) has showed me the way with his notebook: [Hamiltonian from Stipple](https://observablehq.com/@jonhelfman/hamiltonian-from-stipple). And, as it is often the case, [@mbostock](https://observablehq.com/@mbostock) and [@fil](https://observablehq.com/@fil) are the purveyors of the underlying algorithm implementations.","pinned":false,"hidden":false,"mode":"md"},{"id":4,"value":"### 1) Image selection","pinned":false,"hidden":false,"mode":"md"},{"id":6,"value":"viewof imageRaw = imageInput({\n crossOrigin: \"anonymous\",\n initialUrl: await FileAttachment(\"mad.jpg\").url(),\n accept: \".png,.jpg,.jpeg,.gif,.webp\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":15,"value":"imageRaw","pinned":false,"hidden":false,"mode":"ojs"},{"id":18,"value":"### 2) Extraction of image luminance data","pinned":false,"hidden":false,"mode":"md"},{"id":502,"value":"Nothing fancy here, but control over luminosity and contrast is crucial to get decent results. Images with transparency are composed with a white background.","pinned":false,"hidden":false,"mode":"md"},{"id":384,"value":"viewof luminosity = Inputs.range([0, 5], {\n step: 0.1,\n label: \"Luminosity\",\n value: 2\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":836,"value":"viewof contrast = Inputs.range([0, 5], {\n step: 0.1,\n label: \"Contrast\",\n value: 2\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":849,"value":"viewof quantization = Inputs.select(\n new Map([\n [\"none\", null],\n [\"16 levels\", 16],\n [\"8 levels\", 8],\n [\"4 levels\", 4],\n [\"3 levels\", 3],\n [\"2 levels\", 2]\n ]),\n { value: 0, label: \"Quantization\" }\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":20,"value":"viewof lumData = {\n const { width, height } = imageRaw;\n const ease1 = Ease.easePolyOut.exponent(luminosity);\n const ease2 = Ease.easePoly.exponent(contrast);\n const quantize = quantization ? quantizer([0, 1], quantization) : (v) => v;\n const lum = (rgba) => 1 - quantize(ease2(ease1(rgba2lum(rgba) / 256)));\n const { data } = getImageData(imageRaw);\n const values = new Float64Array(arrGen(data, 4).map(lum));\n const pixelData = function* (lumData) {\n for (const val of lumData) {\n const v = Math.floor((1 - val) * 256);\n yield* [v, v, v, 255];\n }\n };\n const context = imageContext(width, height, pixelData(values));\n context.canvas.value = { width, height, values };\n return context.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":49,"value":"### 3) Stippling using weighted relaxation","pinned":false,"hidden":false,"mode":"md"},{"id":504,"value":"This is where the fun begins. Dots are first scattered on the image surface with preference to darker areas ([rejection sampling](https://en.wikipedia.org/wiki/Rejection_sampling)) then moved around to further concentrate in those areas (weighted variant of [Lloyd’s relaxation algorithm](https://en.wikipedia.org/wiki/Lloyd's_algorithm)). ","pinned":false,"hidden":false,"mode":"md"},{"id":538,"value":"I took the code from [this notebook](https://observablehq.com/@mbostock/voronoi-stippling), choosing to convert the worker messaging into a generator. The result is pretty satisfying, but not yet best suited to the plotter needs, since plotting dots can be very long, due to the up and down movements of the pen.","pinned":false,"hidden":false,"mode":"md"},{"id":53,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":410,"value":"viewof dotsDensity = Inputs.range([0.02, 0.5], {\n step: 0.01,\n label: \"Dots density\",\n value: 0.1\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":816,"value":"viewof nbIterations = Inputs.range([1, 100], {\n step: 1,\n label: \"Nb. of iterations\",\n value: 80\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1010,"value":"viewof dotsRadius = Inputs.range([0.5, 2], {\n step: 0.05,\n label: \"Dots radius\",\n value: 1\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":659,"value":"Nb of dots: ${Math.floor(lumData.width * lumData.height * dotsDensity)}","pinned":false,"hidden":false,"mode":"md"},{"id":74,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":110,"value":"### 4) Hamiltonian path","pinned":false,"hidden":false,"mode":"md"},{"id":548,"value":"The idea is: since the dots are well positionned to match the dark areas of the image, and since we don't want to just plot dots, why not join the dots somehow ? The density of dots should convert to a density of segments, and still match the dark areas of the image. To please the plotter, a [Hamiltonian path](https://en.wikipedia.org/wiki/Hamiltonian_path) seems the best starting point to join the dots: it's a path that will go through each dot once and only once, thus the plotter would never have to 'up/move/down'. Furthermore, finding [the shortest non-crossing hamiltonian path](https://en.wikipedia.org/wiki/Travelling_salesman_problem) would be a plus.","pinned":false,"hidden":false,"mode":"md"},{"id":553,"value":"I'm using the approximation method (this is a NP-complete problem) implemented in [@fil](https://observablehq.com/@fil)'s [\"Sort stuff by similarity\"](https://observablehq.com/@fil/sort-stuff-by-similarity) notebook.","pinned":false,"hidden":false,"mode":"md"},{"id":112,"value":"import { order_by_distance } with { opts as opts } from \"@fil/sort-stuff-by-similarity\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":135,"value":"opts = ({ crossover: true, points: true })","pinned":false,"hidden":false,"mode":"ojs"},{"id":556,"value":"Since this is heavy computation, the image surface is recursively split in rectangular zones having less than a threshold number of dots in it, and a unique path is computed inside each of these zones.","pinned":false,"hidden":false,"mode":"md"},{"id":566,"value":"viewof dotThreshold = Inputs.range([100, 2000], {\n step: 10,\n label: \"Max nb dots per zone\",\n value: 400\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":575,"value":"To avoid long isolated segments, we can also specify a length threshold: segments longer than this value will simply not be drawn.","pinned":false,"hidden":false,"mode":"md"},{"id":1091,"value":"viewof segmentLength = interval([0, 30], {\n step: 0.1,\n value: [0, 30],\n label: \"Segment length\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1019,"value":"viewof strokeWidth = Inputs.range([0.1, 2], {\n step: 0.1,\n label: \"Stroke width\",\n value: 1\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":144,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":8,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":10,"value":"import { imageInput } from \"@mbostock/file-input\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":51,"value":"Delaunay = require(\"d3-delaunay\").then(({ Delaunay }) => Delaunay)","pinned":false,"hidden":false,"mode":"ojs"},{"id":677,"value":"Ease = require(\"d3-ease\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":350,"value":"arrGen = function* (items, nb) {\n let arr = [];\n for (const item of items) {\n arr.push(item);\n if (arr.length == nb) {\n yield arr;\n arr = [];\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":361,"value":"getImageData = (image) => {\n const { width, height } = image;\n const context = DOM.context2d(width, height, 1);\n context.drawImage(image, 0, 0);\n return context.getImageData(0, 0, width, height);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":378,"value":"imageContext = (width, height, pixelData) => {\n const context = DOM.context2d(width, height, 1);\n const data = new Uint8ClampedArray(pixelData);\n context.putImageData(new ImageData(data, width, height), 0, 0);\n return context;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":80,"value":"rgba2lum = ([r, g, b, a]) =>\n (a / 256) * (0.2126 * r + 0.7152 * g + 0.072) + (256 - a)","pinned":false,"hidden":false,"mode":"ojs"},{"id":146,"value":"import { Plot, viewer } from \"@ehouais/pivot-format-for-plotter-experiments\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":624,"value":"iterateArray2D = function* (arr, width) {\n let [x, y] = [0, 0];\n for (const item of arr) {\n yield [item, x++, y];\n if (x == width) (x = 0), y++;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":644,"value":"randInt = (max) => Math.floor(Math.random() * max)","pinned":false,"hidden":false,"mode":"ojs"},{"id":858,"value":"quantizer = ([min, max], nb) =>\n (val) => {\n const nv = (val - min) / (max - min);\n return (Math.floor(nv * nb) / (nb - 1)) * (max - min) + min;\n }","pinned":false,"hidden":false,"mode":"ojs"},{"id":1086,"value":"import { interval } from \"@mootari/range-slider\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":1125,"value":"split = (items, condition) =>\n items.reduce(\n ([ta, fa], coords) => {\n (condition(coords) ? ta : fa).push(coords);\n return [ta, fa];\n },\n [[], []]\n )","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}