2b:null 2c:["$","title",null,{"children":"Voronoi Stippling | Joe Taylor | Observable"}] 31:T651,{ const svg = d3.select(DOM.svg(width, height)); const worker = new Worker(script); let path; function polygonScaleOffset(polygon, offset, origin){ if (!origin){ origin = geometric.polygonCentroid(polygon); } let p = []; for (let i = 0, l = polygon.length; i < l; i++){ const v = polygon[i], d = geometric.lineLength([origin, v]), a = geometric.lineAngle([origin, v]); p[i] = geometric.pointTranslate(origin, a, d - offset); } return p; } function messaged({data: points}) { const delaunay = new d3.Delaunay(points); const voronoi = delaunay.voronoi([0, 0, width, height]); // if (path) {path.remove();} // path = svg.append("path") // .attr("fill", "none") // .attr("stroke", "#ccc") // .attr("stroke-width", 1) // .attr("d", voronoi.render()); const polygons = voronoi.cellPolygons(); let polygon = polygons.next(); while (!polygon.done) { let points = polygon.value var newPoints = geometric.polygonScale(points, 0.8); // var newPoints = polygonScaleOffset(points, 2); const flat = newPoints.reduce((acc, cur) => { return acc.concat(cur); }, []); path = svg.append("path") .attr("fill", "none") .attr("stroke", "#ccc") .attr("stroke-width", 1) .attr("d", `M${flat.join(',')}`); polygon = polygons.next(); } } invalidation.then(() => worker.terminate()); worker.addEventListener("message", messaged); worker.postMessage({data, width, height, n}); return svg.node(); }32:T733,script = { const blob = new Blob([` importScripts("${await require.resolve("d3-delaunay@^5.1.1")}"); onmessage = event => { const {data: {data, width, height, n}} = event; const points = new Float64Array(n * 2); const c = new Float64Array(n * 2); const s = new Float64Array(n); // Initialize the points using rejection sampling. for (let i = 0; i < n; ++i) { for (let j = 0; j < 30; ++j) { const x = points[i * 2] = Math.floor(Math.random() * width); const y = points[i * 2 + 1] = Math.floor(Math.random() * height); if (Math.random() < data[y * width + x]) break; } } const delaunay = new d3.Delaunay(points); const voronoi = delaunay.voronoi([0, 0, width, height]); for (let k = 0; k < 80; ++k) { // Compute the weighted centroid for each Voronoi cell. c.fill(0); s.fill(0); for (let y = 0, i = 0; y < height; ++y) { for (let x = 0; x < width; ++x) { const w = data[y * width + x]; i = delaunay.find(x + 0.5, y + 0.5, i); s[i] += w; c[i * 2] += w * (x + 0.5); c[i * 2 + 1] += w * (y + 0.5); } } // 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; for (let i = 0; i < n; ++i) { const x0 = points[i * 2], y0 = points[i * 2 + 1]; const x1 = s[i] ? c[i * 2] / s[i] : x0, y1 = s[i] ? c[i * 2 + 1] / s[i] : y0; points[i * 2] = x0 + (x1 - x0) * 1.8 + (Math.random() - 0.5) * w; points[i * 2 + 1] = y0 + (y1 - y0) * 1.8 + (Math.random() - 0.5) * w; } voronoi.update(); } postMessage(points); close(); }; `], {type: "text/javascript"}); const script = URL.createObjectURL(blob); invalidation.then(() => URL.revokeObjectURL(script)); return script; }33:[{"id":"3b772e005b307033597d065c49d1482c795418d1f4996011a73a90680a90cd686ab94a8abcf687a4fb96e4ff67d1a34b33141e83a6c5b50ced078ed22da08a13","href":"https://static.observableusercontent.com/files/3b772e005b307033597d065c49d1482c795418d1f4996011a73a90680a90cd686ab94a8abcf687a4fb96e4ff67d1a34b33141e83a6c5b50ced078ed22da08a13","name":"avatar.jpeg","type":"image/jpeg","lastModified":1673646557833.249,"size":20279},{"id":"a762f3f2c7e50a189ef921ac27ab26db932c33dc5ff9854f67ff3e2a2bc460994368d58ae6b771877256e98c65a41dd064875fc2f6cb7338b567c7942dcb7301","href":"https://static.observableusercontent.com/files/a762f3f2c7e50a189ef921ac27ab26db932c33dc5ff9854f67ff3e2a2bc460994368d58ae6b771877256e98c65a41dd064875fc2f6cb7338b567c7942dcb7301","name":"IMG_0870.jpg","type":"image/jpeg","lastModified":1673646670700.229,"size":1808726}] 2f:{"id":"8f42d1844fb04027","slug":null,"title":"Voronoi Stippling","thumbnail":"49e3b8e7b5c25c76853ac31b4ed41e895e2facb91573182f4e68e995d0ccb899","access_level":"public","create_time":"$D2023-01-13T21:49:17.833Z","update_time":"$D2023-01-13T21:51:38.400Z","view_time":null,"first_public_time":"$D2023-01-13T21:49:17.833Z","has_unpublished_edits":null,"fork":{"id":"3485825c256a1e6f","slug":"voronoi-stippling","title":"Voronoi Stippling","owner":{"id":"450c2de4bc1c9431","login":"iamjoetaylor","name":"Joe Taylor"}},"stars":0,"starred":false,"owner":{"type":"team","id":"450c2de4bc1c9431","login":"iamjoetaylor","name":"Joe Taylor","avatar_url":"https://avatars-next.observableusercontent.com/b337d9d2b96338d7fff5f21dfbf7bc4073ad88b9cf82cdeb6124b7cba8648d57","tier":"starter_2024"},"version":448,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"3dbc9e6ecc7db785","login":"iamjoetaylor","name":"Joe Taylor","avatar_url":"https://avatars-next.observableusercontent.com/b337d9d2b96338d7fff5f21dfbf7bc4073ad88b9cf82cdeb6124b7cba8648d57","tier":null}],"members":[{"type":"individual","id":"3dbc9e6ecc7db785","login":"iamjoetaylor","name":"Joe Taylor","avatar_url":"https://avatars-next.observableusercontent.com/b337d9d2b96338d7fff5f21dfbf7bc4073ad88b9cf82cdeb6124b7cba8648d57","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Voronoi Stippling","cells":[{"id":0,"value":"md`# Voronoi Stippling\n\nThis notebook applies a weighted variant of [Lloyd’s algorithm](/@mbostock/lloyds-algorithm) to implement stippling. Points are initially positioned randomly using rejection sampling, then at each iteration, the Voronoi cell centroids are weighted by the lightness of the contained pixels.\n\nThis technique is based on [*Weighted Voronoi Stippling*](https://www.cs.ubc.ca/labs/imager/tr/2002/secord2002b/secord.2002b.pdf) by [Adrian Secord](https://cs.nyu.edu/~ajsecord/stipples.html); see also posts by [Muhammad Firmansyah Kasim](https://mfkasim91.github.io/2016/12/06/stippling-pictures-with-lloyds-algorithm/), [Egor Larionov](https://elrnv.com/blog/weighted-lloyds-method-for-voronoi-tesselation/) and [Noah Veltman](https://bl.ocks.org/veltman/017a2093623e1bf3ae041dd3380578cb).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":404,"value":"file = FileAttachment(\"IMG_0870.jpg\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":417,"value":"viewof points = {\n const form = html``;\n form.i.oninput = () => form.o.value = `${(form.value = form.i.valueAsNumber)} points`;\n form.i.oninput();\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":435,"value":"viewof isInverted = {\n const form = html``;\n form.i.oninput = () => form.o.value = `Inverted: ${(form.value = form.i.checked)}`;\n form.i.oninput();\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":339,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3,"value":"data = file.image().then(image => {\n const height = Math.round(width * image.height / image.width);\n const context = DOM.context2d(width, height, 1);\n context.drawImage(image, 0, 0, image.width, image.height, 0, 0, width, height);\n const {data: rgba} = context.getImageData(0, 0, width, height);\n const data = new Float64Array(width * height);\n for (let i = 0, n = rgba.length / 4; i < n; ++i) {\n const value = Math.max(0, 1 - rgba[i * 4] / 254);\n data[i] = isInverted\n ? 1 - value\n : value;\n };\n data.width = width;\n data.height = height;\n return data;\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":40,"value":"n = Math.round(width * height / points)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"height = data.height","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":399,"value":"d3 = require(\"d3-delaunay@5\", \"d3-polygon@1\", \"d3@5\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":442,"value":"geometric = require('geometric');","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W33","stdlib":"1","titling":"auto"}} 30:"$2f:body"