40:null 41:["$","title",null,{"children":"Baby's First Voronoi: with d3-delaunay | Max Graze | Observable"}] 47:T4c9,centeredForest = { const svg = d3.select(DOM.svg(width, height)).style("fill", "white"); // um what is this part? const renderCell = d => { return d == null ? null : "M" + d.join("L") + "Z"; }; var circle = svg .selectAll("g") .data(trees) .join("g"); // we need to use JSON parse and stringify because there is some copy on modify shenanigans // that happens in JS that I don't even want to go into right now // but rather than use voronoi directly, we'll use our algorithm to create // evenly spaced trees in the forest! // console.log(lloydTrees) const voronoi = d3.Delaunay.from(lloydTrees, d => d.x, d => d.y).voronoi([ 0.5, 0.5, width - 0.5, height - 0.5 ]); var cell = circle .append("path") .data(lloydTrees.map((d, i) => voronoi.renderCell(i))) .style("stroke", "#006a4e") .style("stroke-width", "10") .attr("d", d => d) .attr("id", function(d, i) { return "cell-" + i; }) .attr("fill", "#b8d5cd"); const emoji = "🌲"; svg .selectAll(".emoji") .data(lloydTrees) .join("text") .attr("x", d => d.x) .attr("y", d => d.y) .classed("emoji", true) .text(emoji); return svg.node(); }48:T5a8,lloydAlgo = (points, NumIterations = 20) => { // 0️⃣ have N points // create the voronoi structure const voronoi = d3.Delaunay.from(points, d => d.x, d => d.y).voronoi([ 0.5, 0.5, width - 0.5, height - 0.5 ]); // here's our previous set of points - lets get read to update them // d3.Delaunay represents them as a flat array of coordinates [x0, y0, x1, y1, x2, y2…] // mutable debug = v.delaunay.points; for (let i = 0; i < NumIterations; ++i) { for (let j = 0; j < points.length; ++j) { // 1️⃣ computeeach cell of each voronoi polygon const cell = voronoi.cellPolygon(j); // 2️⃣ compute centroid of each voronoi polygon const [x_centroid, y_centroid] = d3.polygonCentroid(cell); /* 3️⃣ move each point towards centroid of its polygon Here .03 is a dampending ratio Since each point has two entries in the array (an x and a y) we need to multiply j by 2 (j * 2) +1 sets the y */ voronoi.delaunay.points[j * 2] += (x_centroid - voronoi.delaunay.points[j * 2]) * 0.03; voronoi.delaunay.points[j * 2 + 1] += (y_centroid - voronoi.delaunay.points[j * 2 + 1]) * 0.03; } //update to make x & y changes voronoi.update() } // 4️⃣ go back to step 1️⃣ return Array.from(points, (_, j) => ({ x: voronoi.delaunay.points[2 * j], y: voronoi.delaunay.points[2 * j + 1] })); }49:[] 45:{"id":"7c4e3d5ed73a7cf5","slug":"babys-first-voronoi-with-d3-delaunay","title":"Baby's First Voronoi: with d3-delaunay","thumbnail":"08ace1809c08299ecb23c4687f742d1f925c579f4c79edb569e3adab796b4087","access_level":"public","create_time":"$D2021-05-09T03:29:28.741Z","update_time":"$D2021-05-27T15:33:20.855Z","view_time":null,"first_public_time":"$D2021-05-11T20:36:10.600Z","has_unpublished_edits":null,"fork":{"id":"feaf689f3cc6d305","slug":"babys-first-voronoi","title":"Baby's First Voronoi","owner":{"id":"cfa704f351f0d39f","login":"mayagans","name":"Maya Gans"}},"stars":1,"starred":false,"owner":{"type":"team","id":"998e3f48dc296646","login":"datagrazing","name":"Max Graze","avatar_url":"https://avatars-next.observableusercontent.com/f69d8a810962426c04ba3ee76a79f7dfb2fc875b2c2d768f60d2084049a4dcdc","tier":"starter_2024","bio":"","following":false},"version":578,"publish_version":578,"role":null,"authored":false,"authors":[{"type":"individual","id":"4c2305a37ae74c4b","login":"datagrazing","name":"Max Graze","avatar_url":"https://avatars-next.observableusercontent.com/f69d8a810962426c04ba3ee76a79f7dfb2fc875b2c2d768f60d2084049a4dcdc","tier":null,"bio":"","following":false}],"members":[{"type":"individual","id":"4c2305a37ae74c4b","login":"datagrazing","name":"Max Graze","avatar_url":"https://avatars-next.observableusercontent.com/f69d8a810962426c04ba3ee76a79f7dfb2fc875b2c2d768f60d2084049a4dcdc","tier":null,"role":"editor"}],"comments":[{"id":"0d66557b5722b112","reply_to_id":null,"content":"*van der Zwan\n\nLike the bird, but with a Z instead of an S :)","create_time":"$D2021-05-27T12:07:27.933Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"d36034ddfb454bdd","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":null}}],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Baby's First Voronoi: with d3-delaunay","cells":[{"id":0,"value":"md`# Baby's First Voronoi: with d3-delaunay`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":50,"value":"md` Voronoi itself is a fairly easy-to-grok concept.\nGiven \\`N\\` points… create a polygon for each point where the polygon is the whole region for which that point is the closest.\n\nThe goal of this notebook is to walkthrough this process and show how you can use voronoi to space out points like a grid, all while updating the previous notebook by using \\`d3-delauny\\`, which optimizes the algorithm. \n\nTo do: \n\n* Update to use flat arrays everywhere so that code is optimized and doesn't use \\`{x, y}\\` objects.\n\nThanks to Maya and Matt for starting this notebook, and Fil and Job van der Zwan for helping me understand and update this notebook to use \\`d3-delauny\\`\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":213,"value":"viewof N = Range([5, 100], {value: 25, label: \"N\", step:1})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":171,"value":"// create x and y positions for N trees\ntrees = {\n const radius = 1\n return d3.range(N).map(function() {\n return {\n x: Math.round(Math.random() * (width - radius * 2) + radius),\n y: Math.round(Math.random() * (height - radius * 2) + radius)\n }\n })\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":203,"value":"forest = {\n const svg = d3.select(DOM.svg(width, height))\n .style(\"fill\",\"white\")\n\n const emoji = \"🌲\";\n \n svg.selectAll(\".emoji\")\n .data(trees)\n .join(\"text\")\n .attr(\"x\", d => d.x)\n .attr(\"y\", d => d.y)\n .classed(\"emoji\", true)\n .text(emoji);\n \n \n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":164,"value":"md `now look at EACH BLADE OF GRASS between the trees and dertermine which tree is closest to each blade of grass….\nafter this is done… you’ll have a “blob” of grass that is all the grass labeled with “tree a”. this is now your voronoi polygon for the point A.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":27,"value":"chart = {\n const svg = d3.select(DOM.svg(width, height))\n .style(\"fill\",\"white\")\n \n const delaunay = d3.Delaunay.from(trees, d => d.x, d => d.y )\n const voronoi = delaunay.voronoi([0.5, 0.5, width - 0.5, height - 0.5])\n // um what is this part?\n const renderCell = (d) => {\n \treturn d == null ? null : \"M\" + d.join(\"L\") + \"Z\";\n }\n \n var circle = svg.selectAll(\"g\")\n .data(trees)\n .enter().append(\"g\")\n \n var cell = circle.append(\"path\")\n .data(trees.map((d,i) => voronoi.renderCell(i)) )\n \t.style(\"stroke\", \"#006a4e\")\n .style(\"stroke-width\", \"10\")\n .attr(\"d\", d => d)\n .attr(\"id\", function(d, i) { return \"cell-\" + i; })\n .attr(\"fill\", \"#b8d5cd\")\n \n \n const emoji = \"🌲\";\n \n \n svg.selectAll(\".emoji\")\n .data(trees)\n .join(\"text\")\n .attr(\"x\", d => d.x)\n .attr(\"y\", d => d.y)\n .classed(\"emoji\", true)\n .text(emoji);\n \n \n return svg.node();\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":257,"value":"md `**But what's interesting is our trees are NOT at the centroid of each polygon! We need Lloyd's Alogorithim to do that!**\n\n**NOTE Lloyds algorithm is NOT a d3.js function we can simply call like voronoi, rather it's a _specific_ way of *implementing* voronoi:**\n\n0️⃣ have N points
\n1️⃣ compute voronoi polygons
\n2️⃣ compute centroid of voronoi polygon
\n3️⃣ move each point towards centroid of its polygon
\n4️⃣ go back to step 1️⃣ and repeat for \\`Num Iterations\\`\n\nRather than show the algorithm at work which would start as our voronoi above does and iterate until each tree is MOVED enough so that each tree gets the same area of grassy field, I'm going to show the end result of the algorithm: `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":246,"value":"md `## Using Lloyd's algorithim will take the number of trees and MOVE them so each tree has the same grassy field:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":314,"value":"viewof NumIters = Range([0, 200], {value: 0, label: \"Num Iterations\", step:1})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":249,"value":"$47","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":224,"value":"md `## Our Algorithm Functions!`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":344,"value":"md `### Voronoi`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":452,"value":"lloydTrees = lloydAlgo(JSON.parse(JSON.stringify(trees)), NumIters)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":346,"value":"md `### Lloyd's Algorithm\n\nGiven the number of trees and a number of iterations, try to move the x,y of the trees so the forest is evenly spaced`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":545,"value":"mutable debug = {}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":276,"value":"$48","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":232,"value":"md `## Appendix`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"height = 400","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"//d3 = require(\"https://d3js.org/d3.v5.min.js\")\nd3 = require(\"d3@6\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":208,"value":"import {Range} from \"@observablehq/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W49","stdlib":"1"}} 46:"$45:body"