2c:null 2d:["$","title",null,{"children":"Weighted Voronoi Stippling | John C | Observable"}] 32:T897,# Weighted Voronoi Stippling From [Daniel Shiffman](https://thecodingtrain.com) The paper referenced [here](https://www.cs.ubc.ca/labs/imager/tr/2002/secord2002b/secord.2002b.pdf) In this post we will start from Voronoi relaxation, if you want to know more about what is Voronoi diagram and how to compute it, check out [this post](../@real-john-cheung/delaunay). We will use the d3.Delaunay library for computing Voronoi diagram in this post, further information on that library is also available on the Delaunay post. ## Voronoi relaxation and Lloyd's algorithm Voronoi relaxation it the process to redraws Voronoi cell polygons after moving the seed of each cell in a Voronoi diagram to the centroid of that cell. Repeated iteration of this process causes the seeds to space out evenly and settle into a stable state. The algorithm for this is named after Stuart P. Lloyd. The algorithm repeats the following two steps until the Voronoi diagram is stable: 1. Compute the centroid of each Voronoi cell 2. Move the cell seed point to the computed centroid, and redraw the Voronoi diagram To implement Lloyd's algorithm, we will need a function to calculate the centroid of a polygon. There is a classic [paper](https://paulbourke.net/geometry/polygonmesh/) by Paul Bourke on calculating the area and centroid of a polygon, which contains two parts: 1. calculation of the area ![image](https://paulbourke.net/geometry/polygonmesh/polyarea6.gif) 2. calculation of the centroid ![image](https://paulbourke.net/geometry/polygonmesh/polyarea5.gif) With the d3.Delaunay library, we can retrieve each of the Voronoi cell in the following format: `[[x0, y0], [x1, y1], …, [x0, y0]]`, so, we can just loop over this array to get the sums we need for computing the centroid: ```js function getCentroid(polygon) { let area = 0, cx = 0, cy = 0; for (let i = 1; i < polygon.length; ++i) { let xi = polygon[i][0], yi = polygon[i][1], xj = polygon[i-1][0], yj = polygon[i-1][1]; area += xj*yi - xi*yj; cx += (xj + xi)*(xj*yi - xi * yj); cy += (yj + yi)*(xj*yi - xi * yj); } area /= 2; cx /= (6 * area); cy /= (6 * area); return [cx, cy]; } ```33:T6b4,p5(s => { let points = [], voronoi; s.setup = () => { s.createCanvas(400,400); s.background(255); for(let i = 0; i < 100; i ++) { points.push(s.random(400)); } s.frameRate(30); voronoi = (new d3.Delaunay(points)).voronoi([0,0,400,400]); } s.draw = () => { s.background(255); s.strokeWeight(1); let inedges = voronoi.delaunay.inedges, halfedges = voronoi.delaunay.halfedges, hull = voronoi.delaunay.hull; let circumcenters = voronoi.circumcenters, vectors = voronoi.vectors; for (let i = 0, n = halfedges.length; i < n; ++i) { const j = halfedges[i]; if (j < i) continue; const ti = Math.floor(i / 3) * 2; const tj = Math.floor(j / 3) * 2; const xi = circumcenters[ti]; const yi = circumcenters[ti + 1]; const xj = circumcenters[tj]; const yj = circumcenters[tj + 1]; s.line(xi, yi, xj, yj); } let h0, h1 = hull[hull.length - 1]; for (let i = 0; i < hull.length; ++i) { h0 = h1, h1 = hull[i]; const t = Math.floor(inedges[h1] / 3) * 2; const x = circumcenters[t]; const y = circumcenters[t + 1]; const v = h0 * 4; const p = voronoi._project(x, y, vectors[v + 2], vectors[v + 3]); if (p) s.line(x, y, p[0], p[1]); } s.strokeWeight(5); for(let i = 0; i < points.length; i += 2) { s.point(points[i], points[i+1]); } if (s.frameCount % 150 === 0){ //s.text(s.frameCount, 10, 10) points=[]; for(let i = 0; i < 100; i ++) { points.push(s.random(400)); } voronoi = (new d3.Delaunay(points)).voronoi([0,0,400,400]); } else { voronoi = relaxVoronoi(voronoi, 10); } } })34:T6ac,It does even out the points, but after a while the shape become blurry and deformed because the points keep moving away from each other. If you give it long enough time, the points will be evenly spread through out the space, leaving no shape behind. To fix it, we need to calculate the centroids with the underlaying image as the reference, i.e., using the weighted centroids. Imagining all the pixels in the cell have a weight, and the darker the pixels, the greater the weight. If we calculate the weighted average of all the pixels in a cell, we can get a weighted centroid. We can do that with a function like below: ```js function weightedCentroid(image, voronoi){ let weights = [], centroids=[], counts = []; let seedIndex = 0; for(let x = 0; x < image.width; x ++){ for(let y = 0; y < image.height; y ++){ let weight = 1 - getBrightness(image, x, y)/255; //With d3.Delaunay, we can use voronoi.delaunay.find() to find the closest Voronoi cell seed to an location seedIndex = voronoi.delaunay.find(x, y, seedIndex); if (!centroids[seedIndex]) centroids[seedIndex] = [0,0]; centroids[seedIndex][0] += x * weight; centroids[seedIndex][1] += y * weight; if (!weights[seedIndex]) weights[seedIndex] = 0; weights[seedIndex] += weight; if (!counts[seedIndex]) counts[seedIndex] = 0; counts[seedIndex] ++; } } for(let i = 0; i < centroids.length; i ++) { if (weights[i] && weights[i] > 0) { centroids[i][0] /= weights[i]; centroids[i][1] /= weights[i]; } else { centroids[i][0] = voronoi.delaunay.points[i*2]; centroids[i][1] = voronoi.delaunay.points[i*2 + 1]; } } return centroids; } ```35:T589,weightedVoronoiRelaxation = function(imagedata, voronoi, precentage = 100) { let width = voronoi.xmax - voronoi.xmin; let seed = voronoi.delaunay.points; let weights = new Array(seed.length/2).fill(0), centroids=new Array(seed.length).fill(0), counts = new Array(seed.length/2).fill(0); let seedIndex = 0; for(let x = voronoi.xmin; x < voronoi.xmax; x ++){ for(let y = voronoi.ymin; y < voronoi.ymax; y ++){ let ind = (x + y * width) * 4; let r = imagedata[ind + 0]; let g = imagedata[ind + 1]; let b = imagedata[ind + 2]; let bright = (r + g + b) / 3; let weight = 1 - bright / 255; //With d3.Delaunay, we can use voronoi.delaunay.find() to find the closest Voronoi cell seed to an location seedIndex = voronoi.delaunay.find(x, y, seedIndex); centroids[seedIndex*2] += x * weight; centroids[seedIndex*2 + 1] += y * weight; weights[seedIndex] += weight; counts[seedIndex] ++; } } for(let i = 0; i < centroids.length; i += 2) { if (weights[i/2] > 0) { centroids[i] /= weights[i/2]; centroids[i+1] /= weights[i/2]; } else { centroids[i] = seed[i]; centroids[i+1] = seed[i+1]; } } for (let i = 0; i < seed.length; i ++) { seed[i] += (centroids[i] - seed[i]) * (precentage/100); } return new d3.Delaunay(seed).voronoi([voronoi.xmin, voronoi.ymin, voronoi.xmax, voronoi.ymax]); }36:T418,p5(s => { let img; let points = [], pointsO; let voronoi; let imgData; s.preload = () =>{ img = s.loadImage(catimg); } s.setup = () => { s.createCanvas(400,400); //s.image(img, 0, 0); s.background(255,10); s.strokeWeight(2); for (let i = 0; i < 2000; i ++){ let x = Math.random() * s.width, y = Math.random() * s.height; let b = s.brightness(img.get(x,y)); if (s.random(90) > b) { points.push(x); points.push(y); } else { i --; } } img.loadPixels(); imgData = img.pixels.slice(); voronoi = (new d3.Delaunay(points)).voronoi([0,0,400,400]); pointsO = points.slice(); } s.draw = () => { s.background(255); for(let i = 0; i < points.length; i += 2) { s.point(points[i], points[i+1]); } if (s.frameCount % 300 === 0){ points= pointsO.slice(); voronoi = (new d3.Delaunay(points)).voronoi([0,0,400,400]); } else { voronoi = weightedVoronoiRelaxation(imgData, voronoi, 10); } } })37:T956,p5(s => { let img; let points = [], pointsO; let voronoi; let imgData; s.preload = () =>{ img = s.loadImage(catimg); } s.setup = () => { s.createCanvas(400,400); //s.image(img, 0, 0); s.background(255,10); s.strokeWeight(2); for (let i = 0; i < 2000; i ++){ let x = Math.random() * s.width, y = Math.random() * s.height; let b = s.brightness(img.get(x,y)); if (s.random(90) > b) { points.push(x); points.push(y); } else { i --; } } img.loadPixels(); imgData = img.pixels.slice(); voronoi = (new d3.Delaunay(points)).voronoi([0,0,400,400]); pointsO = points.slice(); } s.draw = () => { s.background(255); for(let i = 0; i < points.length; i += 2) { s.point(points[i], points[i+1]); } if (s.frameCount % 300 === 0){ points= pointsO.slice(); voronoi = (new d3.Delaunay(points)).voronoi([0,0,400,400]); } else { voronoi = s.bug(imgData, voronoi, 10); } //s.noLoop(); } s.bug = function(imagedata, voronoi, precentage = 100) { let seed = voronoi.delaunay.points; let weights = new Array(seed.length/2).fill(0), centroids=new Array(seed.length).fill(0), counts = new Array(seed.length/2).fill(0); let seedIndex = 0; for(let x = 0; x < 400; x ++){ for(let y = 0; y < 400; y ++){ let ind = (x + y * 400) * 4; let r = imagedata[ind + 0]; let g = imagedata[ind + 1]; let b = imagedata[ind + 2]; let bright = (r + g + b) / 3; let weight = 1 - bright / 255; //With d3.Delaunay, we can use voronoi.delaunay.find() to find the closest Voronoi cell seed to an location seedIndex = voronoi.delaunay.find(x, y, seedIndex); centroids[seedIndex * 2] += x * weight; centroids[seedIndex * 2 + 1] += y * weight; weights[seedIndex] += weight; counts[seedIndex] ++; } } for(let i = 0; i < centroids.length; i += 2) { if (weights[i/2] > 0) { centroids[i] /= weights[i / 2]; centroids[i+1] /= weights[i/2]; } else { centroids[i] = seed[i]; centroids[i+1] = seed[i+1]; } } for (let i = 0; i < seed.length; i ++) { seed[i] += (centroids[i] - seed[i]) * (precentage/100); } return voronoi.delaunay.voronoi([0,0,400,400]); } });38:[{"id":"04828fb87b1ec6a09c7727c634d3e596d8ff39e6b10f36fd294ceaec3a0b746a81afb6575e2d545f3061a465d64e3cc336799a596680fd2df52dbfc803d26064","href":"https://static.observableusercontent.com/files/04828fb87b1ec6a09c7727c634d3e596d8ff39e6b10f36fd294ceaec3a0b746a81afb6575e2d545f3061a465d64e3cc336799a596680fd2df52dbfc803d26064","name":"cat.jpg","type":"image/jpeg","lastModified":1709808116855.636,"size":20843}] 30:{"id":"734ee4accf3a7293","slug":"weighted-voronoi-stippling","title":"Weighted Voronoi Stippling","thumbnail":"13e30d4411e97eaeb46f364a832749801e1273e78f2cdfb92be3daf4ad0e6424","access_level":"public","create_time":"$D2024-03-05T16:03:26.096Z","update_time":"$D2024-03-07T16:27:49.722Z","view_time":null,"first_public_time":"$D2024-03-05T16:03:26.096Z","has_unpublished_edits":null,"fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"b2e9840be7b1b607","login":"real-john-cheung","name":"John C","avatar_url":"https://avatars-next.observableusercontent.com/1d9ef6121a0bbd1a75fab479f9891fe1d78cc65f76c394585ae1a7dad0d3abf6","tier":"starter_2024","bio":"I am lazy so for any info you wanna know about me, visit my website :p\n"},"version":178,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"e8e99acdbe3aebfb","login":"real-john-cheung","name":"John C","avatar_url":"https://avatars-next.observableusercontent.com/1d9ef6121a0bbd1a75fab479f9891fe1d78cc65f76c394585ae1a7dad0d3abf6","tier":null,"bio":"I am lazy so for any info you wanna know about me, visit my website :p\n"}],"members":[{"type":"individual","id":"e8e99acdbe3aebfb","login":"real-john-cheung","name":"John C","avatar_url":"https://avatars-next.observableusercontent.com/1d9ef6121a0bbd1a75fab479f9891fe1d78cc65f76c394585ae1a7dad0d3abf6","tier":null,"role":"editor"},{"type":"team","id":"b2e9840be7b1b607","login":"real-john-cheung","name":"John C","avatar_url":"https://avatars-next.observableusercontent.com/1d9ef6121a0bbd1a75fab479f9891fe1d78cc65f76c394585ae1a7dad0d3abf6","tier":"starter_2024","role":"viewer"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":{"id":"8a91769c6d3b75ab","slug":"algorithms","title":"Algorithms","owner":{"id":"b2e9840be7b1b607","login":"real-john-cheung","name":"John C"}},"type":"notebook","body":{"titling":"auto","title":"Weighted Voronoi Stippling","cells":[{"id":0,"value":"$32","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":21,"value":"function getCentroid(polygon) {\n let area = 0, cx = 0, cy = 0;\n for (let i = 1; i < polygon.length; ++i) {\n let xi = polygon[i][0], yi = polygon[i][1], xj = polygon[i-1][0], yj = polygon[i-1][1];\n area += xj*yi - xi*yj;\n cx += (xj + xi)*(xj*yi - xi * yj);\n cy += (yj + yi)*(xj*yi - xi * yj);\n }\n area /= 2;\n cx /= (6 * area);\n cy /= (6 * area);\n return [cx, cy];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":26,"value":"Now we have our centroid function, we can quickly code something up to \"relax\" the Voronoi diagram\n```js\nfunction relaxVoronoi(voronoi, precentage = 100) {\n const seed = voronoi.delaunay.points;\n const polygons = Array.from(voronoi.cellPolygons());\n let centroids = []\n for (const polygon of polygons) {\n const centroid = getCentroid(polygon);\n centroids.push(centroid[0]);\n centroids.push(centroid[1]);\n }\n for (let i = 0; i < seed.length; ++i) {\n seed[i] += (centroids[i] - seed[i]) * (precentage/100);\n }\n let delaunay = new d3.Delaunay(seed);\n return delaunay.voronoi([voronoi.xmin, voronoi.ymin, voronoi.xmax, voronoi.ymax]);\n}\n```","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":28,"value":"function relaxVoronoi(voronoi, precentage = 100) {\n const seed = voronoi.delaunay.points;\n const polygons = Array.from(voronoi.cellPolygons());\n let centroids = []\n for (const polygon of polygons) {\n const centroid = getCentroid(polygon);\n centroids.push(centroid[0]);\n centroids.push(centroid[1]);\n }\n for (let i = 0; i < seed.length; ++i) {\n seed[i] += (centroids[i] - seed[i]) * (precentage/100);\n }\n let delaunay = new d3.Delaunay(seed);\n return delaunay.voronoi([voronoi.xmin, voronoi.ymin, voronoi.xmax, voronoi.ymax]);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"value":"Let's put it into test with some random points","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":37,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":59,"value":"## Stippling\n\nStippling has been an important technique in fine art and craft, especially in print making, for a very long history. \n\n![image](https://upload.wikimedia.org/wikipedia/commons/thumb/4/45/Giulio_Campagnola_shepherd.jpg/300px-Giulio_Campagnola_shepherd.jpg)\n\n*A stippling print from the 16C*\n\nThe idea of using dot in different sizes and densities to create highlights and shadows are actually one of the key idea in computational graphics too. A very intuitive way to create a stippling style image with computer will be using random dots, something like below:\n```js\nlet image;\nfor (let i = 0; i < numberOfDots; i ++){\n let x = Math.random() * width, y = Math.random() * height;\n let b = getBrightness(image, x, y);\n if (b < threshold) drawPoint(x, y);\n else i --;\n}\n```","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":66,"value":"p5(s => {\n let img;\n s.preload = () =>{\n img = s.loadImage(catimg);\n }\n \n s.setup = () => {\n s.createCanvas(400,400);\n //s.image(img, 0, 0);\n s.background(255,100);\n s.strokeWeight(2);\n for (let i = 0; i < 2000; i ++){\n let x = Math.random() * s.width, y = Math.random() * s.height;\n let b = s.brightness(img.get(x,y));\n if (b < 90) s.point(x, y);\n else i--;\n }\n }\n});","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":85,"value":"It does outline the shape of the cat but doesn't look nice because the dots are not arranged in an organised way as the stippling prints are, especially, they are spear out kind of evenly in areas where brightness is lower than the threshold . We modified the function a bit to change the distribution:\n```js\nfor (let i = 0; i < numberOfDots; i ++){\n let x = Math.random() * width, y = Math.random() * height;\n let b = getBrightness(image, x, y);\n // this make points more likely to appear in the darker area\n if (Math.random() * threshold > b) drawPoint(x, y); \n eles i--;\n}\n```","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":88,"value":"p5(s => {\n let img;\n s.preload = () =>{\n img = s.loadImage(catimg);\n }\n \n s.setup = () => {\n s.createCanvas(400,400);\n //s.image(img, 0, 0);\n s.background(255,100);\n s.strokeWeight(2);\n for (let i = 0; i < 2000; i ++){\n let x = Math.random() * s.width, y = Math.random() * s.height;\n let b = s.brightness(img.get(x,y));\n if (s.random(90) > b) {\n s.point(x, y);\n } else {\n i --;\n }\n }\n }\n});","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":103,"value":"Now we got a bit more details in the stippling image, which is great. But, the points are still laying out in a random and chaotic way, which is not very appealing. We can apply the Voronoi relaxation to those points to relax them.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":105,"value":"p5(s => {\n let img;\n let points = [], pointsO;\n let voronoi;\n s.preload = () =>{\n img = s.loadImage(catimg);\n }\n \n s.setup = () => {\n s.createCanvas(400,400);\n //s.image(img, 0, 0);\n s.background(255,100);\n s.strokeWeight(2);\n for (let i = 0; i < 2000; i ++){\n let x = Math.random() * s.width, y = Math.random() * s.height;\n let b = s.brightness(img.get(x,y));\n if (s.random(90) > b) {\n points.push(x);\n points.push(y);\n } else {\n i --;\n }\n }\n voronoi = (new d3.Delaunay(points)).voronoi([0,0,400,400]);\n pointsO = points.slice();\n }\n\n s.draw = () => {\n s.background(255);\n for(let i = 0; i < points.length; i += 2) {\n s.point(points[i], points[i+1]);\n }\n \n if (s.frameCount % 300 === 0){\n points= pointsO.slice();\n voronoi = (new d3.Delaunay(points)).voronoi([0,0,400,400]);\n } else {\n voronoi = relaxVoronoi(voronoi, 10);\n }\n }\n});","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":114,"value":"$34","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":123,"value":"We can add replace the geometry centroids with the weighted centroids in Voronoi relaxation by adding this function into it.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":125,"value":"$35","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":157,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":153,"value":"Now we have the nice stippling style image! You can play with this algorithm, adding color, changing the size of the dot according to weights, use it on moving images, etc. A lot's of different things can be done with it.\n\nAlso , here is Some glitch effect from a bug, as the extract content. Doing generative art is like this: when you find a bug that looks cool, find a way to make it into a feature!","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":136,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":34,"value":"import {p5} from \"@real-john-cheung/p5js\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":69,"value":"catimg = FileAttachment(\"cat.jpg\").url()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W38","stdlib":"1"}} 31:"$30:body"