31:T9f9,chart = { const chart = d3 .create('svg') .attr('width', width) .attr('height', height); const color = d3 .scaleOrdinal() .domain(["a", "b", "c"]) .range(['green', 'orange', 'red']); const cells = circles.map((d, i) => [d, voronoi.cellPolygon(i)]); // 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 diameter = Math.sqrt(-area); // given the number of circles and the polygon shape // return a vector of XYs to put inside our element object below for plotting // (make a grid and get the centroids maybe?) // (maybe we can use deulaney for this?) // const XYs = getXYs(num, polygon) // initially placed on the grid at the bottom // const elements = circles.map((d, i) => ({ // x: center[0], //XY.x[i] // y: center[1], //XY.y[i] // r: d.count, // food: d.food // })); const elements = circles.map((d, i) => ({ x: coor[i][0], //XY.x[i] y: coor[i][1], //XY.y[i] r: d.count, food: d.food })); 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)) // chart.append("g") // .style("font", "10px sans-serif") // .selectAll("text") // .data(cells) // .join("text") // .each(function([[x, y], cell]) { // console.log(cell) // const [cx, cy] = d3.polygonCentroid(cell); // const angle = (Math.round(Math.atan2(cy - y, cx - x) / Math.PI * 2) + 4) % 4; // d3.select(this).call(angle === 0 ? orient.right // : angle === 3 ? orient.top // : angle === 1 ? orient.bottom // : orient.left); // }) // //.attr("transform", ([d]) => `translate(${d})`) // .attr("display", ([, cell]) => -d3.polygonArea(cell) > 2000 ? null : "none") // .text((d, i) => i); return chart.node() }32:T97b,md`### Possible strategies Thanks Sylvian, for the help: 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. ** And what if we want these "circles" to possibly be pack circles? ** 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.`33:T6e9,/* // RIGHT NOW THIS IS TOTALLY COPIED FROM THE SCRIPT FUNCTION // WE DEF NEED TO ADAPT THIS A BIT AND UNPACK IT // IDEALLY WE WANT TO SUPPLY N AND POLYGON // AND RETURN N [X,Y] getXY = (points) => { // what IS points here? 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) { // what is data?! 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); } } // do we even need all of this part? probably not? // 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; } // can we have this return a vector of [x, y] of length circles? voronoi.update(); } } */34:T5b2,packed = { let svgElement, svg; [svgElement, svg] = getSVG(); const color = d3 .scaleOrdinal() .domain(["a", "b", "c"]) .range(['green', 'orange', 'red']); const cells = circles.map((d, i) => [d, voronoi.cellPolygon(i)]); // 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 diameter = Math.sqrt(-area); const elements = circles.map((d, i) => ({ x: coor[i][0], //XY.x[i] y: coor[i][1], //XY.y[i] r: d.count, food: d.food })); svg .append('path') .data([polygon]) .attr('stroke', 'black') .attr('fill', 'none') .attr('d', d => d3.line()(d)); const root = pack(data); const node = svg.selectAll("g") .data(d3.group(root.descendants(), d => d.height)) .join("g") .selectAll("g") .data(d => d[1]) .join("g") .attr("transform", d => `translate(${d.x + 1},${d.y + 1})`); node.append("circle") .attr("r", d => d.r) .attr("fill", d => color(d.height)); const leaf = node.filter(d => !d.children); leaf.select("circle") .attr("id", d => (d.leafUid = DOM.uid("leaf")).id); return svgElement }35:[] 2f:{"title":"Circles in a Polygon","cells":[{"id":0,"value":"md`# Circles in a Polygon\nTO DO:\n- put force inside \n- put packed circle\n\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"},{"id":113,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"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"},{"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 =len /samples;\n \n for (var i=0;i<=len;i+=step){\n var p = path.getPointAtLength(i);\n points.push([p.x - 1, p.y]);\n }\n\n return points\n}","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":381,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":378,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":389,"value":"//get our polygon from path \npolygon = polygonSampledFromPath(maxspath, 1000)","pinned":true,"hidden":false,"mode":"ojs"},{"id":601,"value":"md`There's probably a better way to do it, but here I am trying to guess what points are in the polygon, and put those numbers to create random numbers that we will use to see if those generaed coordinates are in the polygon or not. If they are, we keep them, if they aren't we keep searching.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":587,"value":"polygonExt = d3.extent(polygon)","pinned":true,"hidden":false,"mode":"ojs"},{"id":596,"value":"polygonExtX = {\n return polygonExt.map(i => i[0])\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":591,"value":"polygonExtY = {\n return polygonExt.map(i => i[1])\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":516,"value":"//make an array of random points \nfunction getRandomPoints() {\n let pts = [getRandomArbitrary(polygonExtX[0] ,polygonExtX[1]), getRandomArbitrary(polygonExtY[0] ,polygonExtY[1])]\n return pts;\n}\n","pinned":true,"hidden":false,"mode":"ojs"},{"id":657,"value":"# Resources\n[Packed in rectrangle](https://jsfiddle.net/LeGfW/3/)","pinned":false,"hidden":false,"mode":"md"},{"id":662,"value":"getSVG = () => {\n const svgElement = DOM.svg(width, height);\n\n const svg = d3\n .select(svgElement)\n .append(\"g\")\n .attr(\"transform\", `translate(${margin},${margin})`);\n return [svgElement, svg];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":665,"value":"margin = 50","pinned":true,"hidden":false,"mode":"ojs"},{"id":666,"value":"$34","pinned":true,"hidden":false,"mode":"ojs"},{"id":614,"value":"orient = ({\n top: text => text.attr(\"text-anchor\", \"middle\").attr(\"y\", -6),\n right: text => text.attr(\"text-anchor\", \"start\").attr(\"dy\", \"0.35em\").attr(\"x\", 6),\n bottom: text => text.attr(\"text-anchor\", \"middle\").attr(\"dy\", \"0.71em\").attr(\"y\", 6),\n left: text => text.attr(\"text-anchor\", \"end\").attr(\"dy\", \"0.35em\").attr(\"x\", -6)\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":565,"value":"coor = {\n let coor = []\n for (let i = 0; i < circles.length; i++) {\n let n = false;\n while(!n) {\n let randomCoor = getRandomPoints()\n if (d3.polygonContains(polygon, randomCoor)) {\n coor.push(randomCoor);\n n = true;\n }\n }\n } \n return coor\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":436,"value":"function getRandomArbitrary(min, max) {\n return Math.random() * (max - min) + min;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":421,"value":"voronoi = {\n const [xMin, xMax] = d3.extent(pointsOnPolygon.map(d => d[0]));\n const [yMin, yMax] = d3.extent(pointsOnPolygon.map(d => d[1]));\n \n // 1 px padding to prevent points on bounds from appearing inside polygon\n const padding = 5\n const bounds = [xMin - padding, yMin - padding, xMax + padding, yMax + padding];\n\n return d3.Delaunay\n .from(pointsOnPolygon)\n .voronoi(bounds);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":652,"value":"data = ({\n \"name\": \"Top\",\n \"children\": [\n {\n \"name\": \"Example A\",\n \"children\": [\n {\n \"name\": \"Example D\",\n \"value\": 6\n }\n ]\n },\n {\n \"name\": \"Example B\",\n \"children\": [\n {\n \"name\": \"Example E\",\n \"value\": 3\n },\n {\n \"name\": \"Example F\",\n \"value\": 1\n },\n {\n \"name\": \"Example G\",\n \"value\": 2\n }]\n },\n {\n \"name\": \"Example C\",\n \"children\": [\n {\n \"name\": \"Example H\",\n \"value\": 2\n },\n {\n \"name\": \"Example I\",\n \"value\": 4\n }\n ]\n }\n ]\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":649,"value":"// color = d3.scaleOrdinal().range([\"#10549E\", \"#1F74D1\", \"#5598E2\"]);\ncolor = d3.scaleOrdinal().range([\"#E26F99\", \"#E89BB7\", \"#F2C5D6\"]);","pinned":false,"hidden":false,"mode":"ojs"},{"id":646,"value":"pack = data => d3.pack()\n .size([width/4, height/4])\n .padding(3)\n (d3.hierarchy(data)\n .sum(d => d.value)\n .sort((a, b) => b.value - a.value))","pinned":false,"hidden":false,"mode":"ojs"},{"id":424,"value":"allCellPolygons = Array.from(voronoi.cellPolygons())","pinned":false,"hidden":false,"mode":"ojs"},{"id":426,"value":"isInsidePolygon = (node) => d3.polygonContains(pointsOnPolygon, node) ? true : false","pinned":false,"hidden":false,"mode":"ojs"},{"id":428,"value":"// adds 'inside' boolean property to each node\ncheckNodesInside = (cellPolygon) => cellPolygon.map((node) => {\n node.inside = isInsidePolygon(node);\n return node\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":419,"value":"pointsOnPolygon = getPointsAlongPolyline(polygon, 200)","pinned":false,"hidden":false,"mode":"ojs"},{"id":415,"value":"// From https://observablehq.com/@veltman/centerline-labeling\nfunction getPointsAlongPolyline(polyline, count) {\n // Calculate distance between each point of polyline\n const distances = polyline.map((p, i) => {\n return distanceBetween(p, polyline[i + 1] || polyline[0]);\n });\n\n const totalLength = d3.sum(distances);\n const stepsize = totalLength / count;\n let traversed = 0;\n let next = stepsize / 2;\n\n const done = polyline.reduce((arr, currentPoint, i) => {\n const distanceBetweenCurrentPoints = distances[i];\n while (next < traversed + distanceBetweenCurrentPoints) {\n let nextPoint = polyline[i + 1] || polyline[0];\n\n\n let percent = (next - traversed) / distanceBetweenCurrentPoints;\n \n arr.push([\n currentPoint[0] + (nextPoint[0] - currentPoint[0]) * percent,\n currentPoint[1] + (nextPoint[1] - currentPoint[1]) * percent\n ]);\n \n next += stepsize;\n }\n traversed += distanceBetweenCurrentPoints;\n return arr;\n }, []);\n return done;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":413,"value":"function distanceBetween(a, b) {\n const dx = a[0] - b[0],\n dy = a[1] - b[1];\n return Math.sqrt(dx * dx + dy * dy);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":116,"value":"height = 200","pinned":false,"hidden":false,"mode":"ojs"},{"id":119,"value":"d3 = require(\"d3@6\", \"d3-delaunay@5\")","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W35","stdlib":"1","titling":"auto"}