2a:null 2b:["$","title",null,{"children":"Circles in a Polygon | Maya Gans | Observable"}] 30:Tc50,md`### Possible strategies First: how many circles, and which size? it depends on what we want, but we can compute the polygon area with https://github.com/d3/d3-polygon#polygonArea. - if we know the number of circles, and all the circles have the same size, just divide the area by the number of circles, and Math.sqrt to get an approximate of the radius, then divide by a factor (1.5?) to get some space around the circles - if we know the size of the circles, do the reverse computation to get the number of points. If the circles have different sizes, we require more thinking. Then, how to place the points? I think we have two ways to do it. Plan A, based on Voronoï stippling / Lloyd: - give the circles an initial location. I think it's not critical, it might be a grid, random, on a circle, or all at the same point (center of the viewport, centroid of the polygon)... - iterate until some stopping criteria (number of iterations, sum of all deplacements under a threshold): - a) compute the voronoi partition - b) iterate on all points - b1) if a point is outside of the polygon, move towards the polygon centroid (hoping it's inside the polygon, which is not ensured in theory) - b2) else, move it towards the center of its Voronoi cell (Lloyd algorithm) in b1) and b2), we might want to move by a constant distance in pixels, or by a percentage of the segment between the current point and its target (10%, for example) To check if a point is inside or outside of the polygon, we use https://github.com/d3/d3-polygon. We can ust call it every time we need it. I don't think it would be a problem for a small number of circles. If the number of circles become high, we might have to do memoïzation: if the function polygonContains has already been called for a given (x,y) point, we should return it from memory instead of doing the calculation again. To store the values in memory, we can use any data structure: - if we want to do as in Voronoï Stippling's notebook, we might store them in a canvas, with white meaning outside, and black meaning inside. - fill a Map object - fill an Array of Arrays... Anyway, I think we should first resolve the problem without memoïzation, then optimize. So: no need for canvas for the moment. Plan B, based on d3-force: - give the circles an initial location - create a d3-force simulation with some or all of the following "forces", with relative strengths to tweak (I gave up here because it was unstable->ugly animation - but it we are interested in the final result only, it could work): - d3.forceCollide to prohibit circles overlap - d3.forceManyBody with a negative strength factor to separate the points - d3.forceCenter to attract the circles towards the polygon centroid - a custom force function to move the points located outside the polygon. Maybe moving them toward the polygon centroid, or maybe just moving them randomly would let converge in the end --- Note: if the circles have different sizes, Plan B works out of the box, I think, while Plan A requires to weight the points in a way, as in Voronoï Stippling. Requires more thinking. `31:Tae5,chart = { const chart = d3 .create('svg') .attr('width', width) .attr('height', height); const color = d3 .scaleOrdinal() .domain(["a", "b", "c"]) .range(['green', 'orange', 'red']); // make a polygon from our path const polygon = polygonSampledFromPath(maxspath, 1000) // number of circles const num = circles.length; // get the area of the polgygon // and divide it into the number of circles we want // with some offset because ??? const area = (d3.polygonArea(polygon) / num) * 0.8; // get the center of the polygon // using this as a standin for our points just to plot something const center = d3.polygonCentroid(polygon); const elements = circles.map((d, i) => ({ // honestly these x,ys shouldn't matter // because it looks like we use getMask and getXYs // to actually generate the x and ys we want x: center[0], y: center[1], r: d.count, food: d.food })); // TRYING TO ADAPT SYLVIANS CODE: const mask = getMask({ width, height, polygon }); // Rather than creating the simulate(n) function // (since I didn't know what n was) // I just make the number of points we need statically right here // but this makes no sense to me... // I _think_ this is just setup to supply points as an argument to getXYs aka the script??? /* function simulate(n) { if (locked === true) { next = n; return; } next = null; locked = true; const points = new Float64Array(n * 2); for (let i = 0; i < n; ++i) { points[i * 2] = elements[i].x; points[i * 2 + 1] = elements[i].y; } worker.postMessage({ data: mask, width, height, points, center }); } */ const points = new Float64Array(num * 2); for (let i = 0; i < num; ++i) { points[i * 2] = elements[i].x; points[i * 2 + 1] = elements[i].y; } // now instead of calling a worker or anything fancy I made a function called getXY // that should be used instead of the fancy script thats a string with workers // but this is not working at all.... // My mental model would be that we use the mask, w,h, and center to update the points // that must be wrong?? getXYs(mask, width, height, points, center); chart .append('path') .data([polygon]) .attr('stroke', 'black') .attr('fill', 'none') .attr('d', d => d3.line()(d)); // show the elements in their initial position chart .selectAll('g.element') .data(elements, (d, i) => i) .enter() .append('g') .attr('class', 'element') .append('circle') .attr('cx', d => d.x) .attr('cy', d => d.y) .attr('r', d => d.r) .style('stroke', 'none') .attr('fill', d => color(d.food)) return chart.node() }32:T5e0,// this is my attempt at simplifying the script cell and failing getXYs = (data, width, height, points, center) => { const n = points.length const c = new Float64Array(n * 2); const s = new Float64Array(n); const [cx, cy] = center; const strength = 0.1 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 wp = data[Math.floor(y0) * width + Math.floor(x0)]; let x1, y1; if (wp && s[i]) { x1 = c[i * 2] / s[i]; y1 = c[i * 2 + 1] / s[i]; } else { x1 = x0 + (cx - x0) * strength y1 = y0 + (cy - y0) * strength; } 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; } } return points voronoi.update() }33:[] 2e:{"id":"59824137a8016bf1","slug":"circles-in-a-path","title":"Circles in a Polygon","thumbnail":"49e3b8e7b5c25c76853ac31b4ed41e895e2facb91573182f4e68e995d0ccb899","access_level":"public","create_time":"$D2021-05-06T18:52:51.910Z","update_time":"$D2021-05-12T09:33:42.717Z","view_time":null,"first_public_time":"$D2021-05-06T19:04:16.021Z","fork":{"id":"2b6aad7b680290cf","slug":"path-to-polygon","title":"From Path to Polygon and Back Again","owner":{"id":"cfa704f351f0d39f","login":"mayagans","name":"Maya Gans"}},"stars":0,"starred":false,"owner":{"type":"team","id":"cfa704f351f0d39f","login":"mayagans","name":"Maya Gans","avatar_url":"https://avatars-next.observableusercontent.com/106e9e9b89751753a8046f057b9b885e525e02d6deca7ef8b83b5b1f969a1f26","tier":"starter_2024"},"version":430,"publish_version":430,"role":null,"authored":false,"authors":[{"type":"individual","id":"8a52a621b0b172dc","login":"mayagans","name":"Maya Gans","avatar_url":"https://avatars-next.observableusercontent.com/106e9e9b89751753a8046f057b9b885e525e02d6deca7ef8b83b5b1f969a1f26","tier":null}],"members":[{"type":"individual","id":"4c2305a37ae74c4b","login":"datagrazing","name":"Max Graze","avatar_url":"https://avatars-next.observableusercontent.com/f69d8a810962426c04ba3ee76a79f7dfb2fc875b2c2d768f60d2084049a4dcdc","tier":null,"role":"editor"},{"type":"individual","id":"8a52a621b0b172dc","login":"mayagans","name":"Maya Gans","avatar_url":"https://avatars-next.observableusercontent.com/106e9e9b89751753a8046f057b9b885e525e02d6deca7ef8b83b5b1f969a1f26","tier":null,"role":"editor"},{"type":"individual","id":"bf1872cca880d345","login":"severo","name":"Sylvain Lesage","avatar_url":"https://avatars-next.observableusercontent.com/7713195c83e5bfd8090ffe70c871c23e743c711e9e712675c99a8960ca8c7944","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":2,"collection":{"id":"bfad2565a2b5a457","slug":"d3-paths-and-algos","title":"D3 Paths and Algos","owner":{"id":"cfa704f351f0d39f","login":"mayagans","name":"Maya Gans"}},"type":"notebook","body":{"title":"Circles in a Polygon","cells":[{"id":0,"value":"md`# Circles in a Polygon\n\nNow that our path is a polygon from Part 1, let's see if we can use this notebook to put some circles INSIDE our polygon. The notebook is fancy and pushes circles into the shape, let's simplify and have the circles just render inside the shape!\n\nSee also Voronoi Stippling and Lloyd's Algorithm.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2,"value":"maxspath = \"M221.3,136.1c-8.2,22.6-55.3,16.2-105.6-29.1C85,79.5,98.8,74.9,82,65.7C34.8,39.9-3.4,39.9,0.8,13.6C5.6-16.1,104.5,5.5,134,70.3c10,22,20.7,18.8,39.8,26C206,108.5,227.4,119.3,221.3,136.1z\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":92,"value":"polygonSampledFromPath = (path,samples) => {\n\n path = svg``\n var poly = document.createElementNS(\"http://www.w3.org/2000/svg\", \"polygon\");\n\n var points = [];\n var len = path.getTotalLength();\n var step = step=len/samples;\n \n for (var i=0;i<=len;i+=step){\n var p = path.getPointAtLength(i);\n points.push([p.x, p.y]);\n }\n\n return points\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":228,"value":"circles = [\n {count: 10, food: \"a\"}, \n {count:5, food: \"b\"}, \n {count:8, food: \"c\"},\n {count: 10, food: \"a\"}, \n {count:7, food: \"b\"}\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":381,"value":"md `### TODO: Trying to pull out the script that uses a worker and called it the function getXY. The first argument of this function is the result of getMask so I put that in this notebook too but I'm not sure what the hell I'm doing. I also tried to pull in the simulate code because the getXY function needs points but I'm not sure how these points are generated!!`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":425,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":113,"value":"$31","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":389,"value":"function getMask({ width, height, polygon }) {\n // build the black and white mask, used by the voronoi stippling algorithm\n const canvas = document.createElement(\"canvas\");\n const dpi = 1; // TODO: manage other cases, to reduce the computation complexity?\n canvas.width = width * dpi;\n canvas.height = height * dpi;\n canvas.style.width = width + \"px\";\n canvas.style.height = height + \"px\";\n const context = canvas.getContext(\"2d\");\n context.scale(dpi, dpi);\n context.beginPath();\n context.moveTo(...polygon[polygon.length - 1]);\n for (const p of polygon) {\n context.lineTo(...p);\n }\n context.fillStyle = 'black';\n context.fill();\n\n // prepare data\n const { data: rgba } = context.getImageData(\n 0,\n 0,\n canvas.width,\n canvas.height\n );\n const mask = new Float64Array(canvas.width * canvas.height);\n for (let i = 0, n = rgba.length / 4; i < n; ++i)\n mask[i] = Math.max(0, rgba[i * 4 + 3] / 254);\n mask.width = canvas.width;\n mask.height = canvas.height;\n\n return mask;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":378,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":116,"value":"height = 200","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":119,"value":"d3 = require(\"d3@6\", \"d3-delaunay@5\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W33","stdlib":"1","titling":"auto"}} 2f:"$2e:body"