2d:null 2e:["$","title",null,{"children":"Voronoi and Voronoise | John C | Observable"}] 33:T656,p5(s => { class FeaturePoint{ constructor(x, y, r){ this.x = x; this.y = y; this.r = r; // radious for dragging } display(){ s.push(); s.strokeWeight(3); s.stroke('red'); s.point(this.x, this.y); s.pop(); } } let randomness = displacement; let rowNo = 20, colNo = 20; let delaunay, voronoi; let points = []; let theCanvas; s.setup = function () { theCanvas = s.createCanvas(400, 400); s.background(255); createPoints(points, rowNo, colNo); createVoronoi(points); } s.draw = function(){ points.forEach(fp => fp.display()); for (let i = 0, n = delaunay.points.length / 2; i < n; ++i) { const cell = voronoi.cellPolygon(i); if (cell && cell.length) { for(let k = 1; k < cell.length; k++) { s.line(cell[k][0], cell[k][1], cell[k-1][0], cell[k-1][1]); } } } s.noLoop(); } let createPoints = function (target, r, c) { let cellW = s.width / c; let cellH = s.height / r; for (let i = 0; i < r; i ++){ for (let j = 0; j < c; j ++) { let x = (j) * cellW + cellW / 2 + (Math.random() - 0.5) * randomness * cellW; let y = (i) * cellH + cellH / 2 + (Math.random() - 0.5) * randomness * cellH; target.push(new FeaturePoint(x,y,10)); } } } let createVoronoi = function(featurePoints){ let flatArray = []; featurePoints.forEach(fp => { flatArray.push(fp.x); flatArray.push(fp.y); }); delaunay = new Delaunay(flatArray); voronoi = delaunay.voronoi([0,0, s.width, s.height]); } })34:T2158,class Apollonius { /** * return the square of the distance between two sites (unweighted) * * @param {Site} a * @param {Site} b * @returns the square of the distance */ static distSq(a, b) { return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); } /** * return the distance between two sites (unweighted) * * @param {Site} a * @param {Site} b * @returns */ static dist(a, b) { return Math.sqrt(Apollonius.distSq(a, b)); } /** * return distance between two points * * @param {number} x1 * @param {number} y1 * @param {number} x2 * @param {number} y2 * @returns */ static distP(x1, y1, x2, y2) { return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); } /** * site compare function * * @param {Site} a * @param {Site} b * @returns */ static compareSite(a, b) { if (a.getWeight() > b.getWeight()) { return 1; } else if (a.getWeight() === b.getWeight()) { return 0; } else { return -1; } } /** * sort sites so sites[0].w < sites[1].w < ... < sites[n-1].w * * @param {Array} sites */ static sortSites(sites) { sites = sites.sort(Apollonius.compareSite); } /** * constructor * * @param {number} width * @param {number} height * @param {Array} data data should be a flat array [x0,y0,w0,x1,y1,w1,...] */ constructor(width, height, data) { if (arguments.length === 0) { width = 100; height = 100; } else if (arguments.length === 1) { data = width; width = 100; height = 100; } this.width = width; this.height = height; this.widthInt = Math.floor(width); this.heightInt = Math.floor(height); if (data && data.length) this.setSites(data); this.scanGap = 1; this.bisectors = []; } /** * set the sites used for the graph * sites will be moved all together to ensure x, y coordinate are all positive * width and height will be adjusted if there are sites fall outside * * @param {Array} data input sites, should be a flat array [x0,y0,w0,x1,y1,w1,...] * @param {*} pure if true, sites will not be moved and width and height will not be adjusted * @returns */ setSites(data, pure) { if (!Array.isArray(data)) throw new Error("data should be an array"); if (data[0] instanceof Site) { this.sites = data; return; } if (data.length % 3 != 0) throw new Error("invalid data"); if (pure) { this.sites = []; for (let i = 0; i < data.length / 3; i++) { this.sites[i] = new Site(data[i * 3], data[i * 3 + 1], data[i * 3 + 2]); } this.n = this.sites.length; return } let minX = Number.POSITIVE_INFINITY, minY = Number.POSITIVE_INFINITY, maxX = Number.NEGATIVE_INFINITY, maxY = Number.NEGATIVE_INFINITY; this.sites = []; for (let i = 0; i < data.length / 3; i++) { if (data[i * 3] > maxX) { maxX = data[i * 3]; } if (data[i * 3] < minX) { minX = data[i * 3]; } if (data[i * 3 + 1] > maxY) { maxY = data[i * 3]; } if (data[i * 3 + 1] < minY) { minY = data[i * 3]; } this.sites[i] = new Site(data[i * 3], data[i * 3 + 1], data[i * 3 + 2]); } let xrange = maxX - minX, yrange = maxY - minY; if (minX < 0) { this.sites.forEach(site => { site.x += -minX }); } if (minY < 0) { this.sites.forEach(site => { site.y += -minY }); } if (xrange > this.width) { this.width = xrange; this.widthInt = Math.floor(width); } if (yrange > this.height) { this.height = yrange; this.heightInt = Math.floor(this.height); } this.n = this.sites.length; } /** * set the curve quality (i.e number of bisectors calculated) * * @param {number} scanGap a positive integer, default to 1, the larger the less bisectors get calculated */ setScanGap(scanGap) { if (scanGap < 0) throw new Error("scanGap should be positive"); this.scanGap = scanGap; } /** * build the graph * */ build() { let sites = this.sites; let allBi = []; Apollonius.sortSites(sites); let n = this.n; //double x2r = 0, y2r = 0; for (let i = 1; i < this.n; i++) { for (let j = i + 1; j < this.n + 1; j++) { let locSec = []; // double distIJ = power(power(sites[i-1].x - sites[j-1].x, 2) + power(sites[i-1].y // - sites[j-1].y,2), 0.5);// let distIJ = Apollonius.dist(sites[i - 1], sites[j - 1]); let weightDiffJI = sites[j - 1].w - sites[i - 1].w; if (distIJ > weightDiffJI) { let halfDistIJ = distIJ / 2; let midXIJ = (sites[i - 1].x + sites[j - 1].x) / 2; let midYIJ = (sites[i - 1].y + sites[j - 1].y) / 2; let deltaY = midYIJ - sites[i - 1].y; let ph = deltaY / halfDistIJ; let th = Math.atan(ph / Math.sqrt(1 - ph * ph)); if (sites[i - 1].x < sites[j - 1].x) { th = Math.PI - Math.atan(ph / Math.sqrt(1 - ph * ph)); } let minYInt = -this.heightInt; let maxYInt = this.heightInt; for (let yjInt = minYInt; yjInt <= maxYInt; yjInt += this.scanGap) { let b1y = 4 * (halfDistIJ * weightDiffJI) * (halfDistIJ * weightDiffJI) + 4 * (weightDiffJI * yjInt) * (weightDiffJI * yjInt) - weightDiffJI * weightDiffJI * weightDiffJI * weightDiffJI; let b2y = (16 * halfDistIJ * halfDistIJ - 4 * weightDiffJI * weightDiffJI); let b3y = b1y / b2y; if (b3y >= 0) { let x0 = Math.sqrt(b3y); let x10, y10; x10 = midXIJ + Math.cos(-th) * x0 - Math.sin(-th) * yjInt; y10 = midYIJ + Math.sin(-th) * x0 + Math.cos(-th) * yjInt; if (x10 > 0 && x10 < this.width && y10 > 0 && y10 < this.height) { let d5 = Apollonius.distP(x10, y10, sites[i - 1].x, sites[i - 1].y) - sites[i - 1].w; let valid = true; for (let k = 1; k < n + 1; k++) { if (k != i && k != j) { let d6 = Apollonius.distP(x10, y10, sites[k - 1].x, sites[k - 1].y) - sites[k - 1].w; if (d5 > d6) { valid = false; break; } } } if (valid) { locSec.push([x10, y10]); } } } } } if (locSec.length > 0) allBi.push(locSec); } } this.bisectors = allBi; } /** * return site centers as a flat array * * @return */ siteCenters() { let res = []; for (let i = 0; i < this.sites.length; i++) { res[i * 2] = this.sites[i].x; res[i * 2 + 1] = this.sites[i].y; } return res; } /** * return sites as a flat array [x0,y0,w0,x1,y1,w1,...] * * @return */ flattenSites() { let res = []; for (let i = 0; i < this.sites.length; i++) { res[i * 3] = this.sites[i].x; res[i * 3 + 1] = this.sites[i].y; res[i * 3 + 2] = this.sites[i].w; } return res; } }35:[{"id":"fbbedbad7831cad71b159343e11dac92e9fe810d46813a227820fb568071c9979240b158f60955fea8ea8cc53520100382552c351ee81aefe9602c9b639f8ed5","href":"https://static.observableusercontent.com/files/fbbedbad7831cad71b159343e11dac92e9fe810d46813a227820fb568071c9979240b158f60955fea8ea8cc53520100382552c351ee81aefe9602c9b639f8ed5","name":"image.png","type":"image/png","lastModified":1699367368795.545,"size":74969}] 31:{"id":"bac4a9145b71c5b0","slug":"voronoi","title":"Voronoi and Voronoise","thumbnail":"9e8f9e553fb90d0adcf29ce78a0fba515b9b3c08f6578bd6db804b3a2168f609","access_level":"public","create_time":"$D2023-11-06T11:29:33.204Z","update_time":"$D2023-12-04T10:27:06.684Z","view_time":null,"first_public_time":"$D2023-11-06T11:29:33.204Z","has_unpublished_edits":null,"fork":false,"stars":3,"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"},"version":129,"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}],"members":[{"type":"individual","id":"e8e99acdbe3aebfb","login":"real-john-cheung","name":"John C","avatar_url":"https://avatars-next.observableusercontent.com/1d9ef6121a0bbd1a75fab479f9891fe1d78cc65f76c394585ae1a7dad0d3abf6","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"aac27ce630a2ebd4","slug":"posts","title":"Posts","owner":{"id":"b2e9840be7b1b607","login":"real-john-cheung","name":"John C"}},"type":"notebook","body":{"title":"Voronoi and Voronoise","cells":[{"id":0,"value":"# Voronoi and Voronoise\n\nI recently read a blog by Inigo Quilez (quite a old one, link [here](https://iquilezles.org/articles/voronoise)) about merging Voronoi and noise in procedural graphic generation, which is quite interesting. As the blog indicated, this merge doesn't have any practical application yet as it's slower than perlin noise or cell noise. But what computational artists do is often playing with useless stuff so here we go.\n\n## Voronoi graph \n\nPreviously I made a post on Delaunay triangulation, Voronoi, and Gabriel graph. In that post we approach Voronoi graph as a mirrored image from a Delaunay triangulation. But we can think about it in another context. \n\nImagine we many feature points, laying out in a very rigid manner in the space. If we make a Voronoi graph from it, it will looks like a rigid grid.\n\n

\n\nBut what if we add some random displacement for the feature points?","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":64,"value":"viewof displacement = Inputs.range([0, 1], {value: 0, step: 0.01, label: \"Displacement\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":69,"value":"So, another way to approach Voronoi graph is to think about it as a randomly jittered grid. This give a more natural looking tessellation as nothing in nature appear in the form of a perfect grid. Thinking about Voronoi in this way also allow us to put grid noise into Voronoi graph\n```\nunder construction\n```","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":72,"value":"## Weighted Voronoi graph\n\nApollonius Graph (Additive Weighted Voronoi Graph) is another kind of Voronoi graph. In Apollonius graph, each point is weighted. It can be seen as the Voronoi graph of disk.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":102,"value":"p5(s => {\n s.setup = function () {\n s.createCanvas(600,600);\n s.background(255);\n s.stroke(0);\n s.noFill();\n let data = [];\n for (let i = 0; i < 9; i++) {\n for (let j = 0; j < 9; j++) {\n let x = 60 + i * 60 + s.random(-20,20);\n let y = 60 + j * 60 + s.random(-20,20);\n let w = s.random(5,30);\n s.circle(x,y,w*2);\n data.push(x,y,w);\n }\n }\n\n let g = new Apollonius(s.width, s.height);\n g.setSites(data, true);\n g.setScanGap(5);\n g.build();\n s.stroke(255,0,0);\n for (let i = 0; i < g.bisectors.length; i++) {\n const sec = g.bisectors[i];\n for (let j = 1; j < sec.length; j++) {\n s.line(sec[j][0], sec[j][1],sec[j-1][0],sec[j-1][1]);\n \n }\n }\n }\n});","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"

","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":12,"value":"import {p5, p5c} from \"@real-john-cheung/p5js\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"Delaunay = d3.Delaunay","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":75,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":80,"value":"class Site {\n\n\n /**\n * create a new site\n * @param {number} x \n * @param {number} y \n * @param {number} w \n */\n constructor(x, y, w) {\n this.x = x;\n this.y = y;\n this.w = w;\n }\n\n /**\n * \n * @returns weight of the site\n */\n getWeight() {\n return this.w;\n }\n\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 32:"$31:body"