Emballage de cercles de différentes tailles en rectangle – d3.js

Voici un aller à la mise en œuvre de votre algorithme.

Je l'ai réglé un peu, mais je pense que c'est fondamentalement la même chose.

Cercles délimitant

J'ai utilisé une astuce pour rendre le calcul plus régulier.

À la place des segments définissant la zone de délimitation, j'ai utilisé des cercles avec des rayons "infinis", qui peuvent être considérés comme une bonne approximation des lignes:

L'image montre à quoi ressemblent les 4 cercles délimitant lorsque le rayon diminue. Ils sont calculés pour passer dans les coins de la boîte de délimitation et converger vers les côtés réels lorsque le rayon se développe.

Les cercles «coin» (comme l'appelle l'algorithme) sont tous calculés comme des tangentes à une paire de cercles, éliminant ainsi le cercle spécial + segment ou segments + segments.

Cela simplifie également considérablement la condition de démarrage.
L'algorithme commence simplement avec les quatre cercles de délimitation et ajoute un cercle à la fois, en utilisant le paramètre lambda heuristic greedy pour choisir le meilleur emplacement.

Meilleure stratégie d'ajustement

L'algorithme original ne produit pas le plus petit rectangle pour tenir tous les cercles
(Il essaie simplement d'adapter un tas de cercles dans un rectangle donné).

J'ai ajouté une recherche dichotomique simple en dessus pour deviner la surface minimale (qui donne le plus petit rectangle délimitant pour un rapport d'aspect donné).

Le code

Voici un violon

 var Packer = function (circles, ratio) { this.circles = circles; this.ratio = ratio || 1; this.list = this.solve(); } Packer.prototype = { // try to fit all circles into a rectangle of a given surface compute: function (surface) { // check if a circle is inside our rectangle function in_rect (radius, center) { if (center.x - radius < - w/2) return false; if (center.x + radius > w/2) return false; if (center.y - radius < - h/2) return false; if (center.y + radius > h/2) return false; return true; } // approximate a segment with an "infinite" radius circle function bounding_circle (x0, y0, x1, y1) { var xm = Math.abs ((x1-x0)*w); var ym = Math.abs ((y1-y0)*h); var m = xm > ym ? xm : ym; var theta = Math.asin(m/4/bounding_r); var r = bounding_r * Math.cos (theta); return new Circle (bounding_r, new Point (r*(y0-y1)/2+(x0+x1)*w/4, r*(x1-x0)/2+(y0+y1)*h/4)); } // return the corner placements for two circles function corner (radius, c1, c2) { var u = c1.c.vect(c2.c); // c1 to c2 vector var A = u.norm(); if (A == 0) return [] // same centers u = u.mult(1/A); // c1 to c2 unary vector // compute c1 and c2 intersection coordinates in (u,v) base var B = c1.r+radius; var C = c2.r+radius; if (A > (B + C)) return []; // too far apart var x = (A + (B*BC*C)/A)/2; var y = Math.sqrt (B*B - x*x); var base = c1.c.add (u.mult(x)); var res = []; var p1 = new Point (base.x -uy * y, base.y + ux * y); var p2 = new Point (base.x +uy * y, base.y - ux * y); if (in_rect(radius, p1)) res.push(new Circle (radius, p1)); if (in_rect(radius, p2)) res.push(new Circle (radius, p2)); return res; } ///////////////////////////////////////////////////////////////// // deduce starting dimensions from surface var bounding_r = Math.sqrt(surface) * 100; // "infinite" radius var w = this.w = Math.sqrt (surface * this.ratio); var h = this.h = this.w/this.ratio; // place our bounding circles var placed=[ bounding_circle ( 1, 1, 1, -1), bounding_circle ( 1, -1, -1, -1), bounding_circle (-1, -1, -1, 1), bounding_circle (-1, 1, 1, 1)]; // Initialize our rectangles list var unplaced = this.circles.slice(0); // clones the array while (unplaced.length > 0) { // compute all possible placements of the unplaced circles var lambda = {}; var circle = {}; for (var i = 0 ; i != unplaced.length ; i++) { var lambda_min = 1e10; lambda[i] = -1e10; // match current circle against all possible pairs of placed circles for (var j = 0 ; j < placed.length ; j++) for (var k = j+1 ; k < placed.length ; k++) { // find corner placement var corners = corner (unplaced[i], placed[j], placed[k]); // check each placement for (var c = 0 ; c != corners.length ; c++) { // check for overlap and compute min distance var d_min = 1e10; for (var l = 0 ; l != placed.length ; l++) { // skip the two circles used for the placement if (l==j || l==k) continue; // compute distance from current circle var d = placed[l].distance (corners[c]); if (d < 0) break; // circles overlap if (d < d_min) d_min = d; } if (l == placed.length) // no overlap { if (d_min < lambda_min) { lambda_min = d_min; lambda[i] = 1- d_min/unplaced[i]; circle[i] = corners[c]; } } } } } // select the circle with maximal gain var lambda_max = -1e10; var i_max = -1; for (var i = 0 ; i != unplaced.length ; i++) { if (lambda[i] > lambda_max) { lambda_max = lambda[i]; i_max = i; } } // failure if no circle fits if (i_max == -1) break; // place the selected circle unplaced.splice(i_max,1); placed.push (circle[i_max]); } // return all placed circles except the four bounding circles this.tmp_bounds = placed.splice (0, 4); return placed; }, // find the smallest rectangle to fit all circles solve: function () { // compute total surface of the circles var surface = 0; for (var i = 0 ; i != this.circles.length ; i++) { surface += Math.PI * Math.pow(this.circles[i],2); } // set a suitable precision var limit = surface/1000; var step = surface/2; var res = []; while (step > limit) { var placement = this.compute.call (this, surface); console.log ("placed",placement.length,"out of",this.circles.length,"for surface", surface); if (placement.length != this.circles.length) { surface += step; } else { res = placement; this.bounds = this.tmp_bounds; surface -= step; } step /= 2; } return res; } }; 

Performance

Le code n'est pas optimisé, pour favoriser la lisibilité (ou j'espère :)).

Le temps de calcul augmente assez nettement.
Vous pouvez placer en toute sécurité environ 20 cercles, mais tout ce qui précède 100 fera tourner votre navigateur.

Pour une raison quelconque, il est beaucoup plus rapide sur FireFox que sur IE11.

Efficacité de l'emballage

L'algorithme fonctionne assez mal sur des cercles de taille identique (il ne peut pas trouver le célèbre motif en nid d'abeille pour 20 cercles sur un carré), mais plutôt sur une large distribution de rayons aléatoires.

Esthétique

Le résultat est assez négligeable pour les cercles de taille identique.
Il n'y a pas de tentative de regroupement des cercles ensemble, donc si deux possibilités sont jugées équivalentes par l'algorithme, on choisit simplement au hasard.

Je soupçonne que le paramètre lambda pourrait être raffiné un peu pour permettre un choix plus esthétique en cas de valeurs égales.

Évolutions possibles

Avec le "rayon des rayons infinis", il devient possible de définir un polygone délimitant arbitrairement.

Si vous fournissez une fonction pour vérifier si un cercle s'insère dans ledit polygone, il n'y a aucune raison pour que l'algorithme ne produise pas de résultat.

La question de savoir si ce résultat serait efficace est une autre question :).

Une approche complètement différente …

Comme je l'ai mentionné dans un commentaire, une disposition de la force de grappe d3 pourrait être adaptée à une méthode heuristique pour ajuster les cercles dans la boîte, en changeant progressivement la balance jusqu'à ce que vous ayez un ajustement serré.

Les résultats jusqu'à présent ne sont pas parfaits, donc je présente quelques versions:

Option 1, serre dans la boîte à l'espace occupé par les cercles avant d' ajuster le chevauchement du cercle. Le résultat est très serré, mais avec un léger chevauchement entre les cercles qui s'accrochent entre les murs de la boîte et les uns des autres, incapables de bouger sans conflit:
http://fiddle.jshell.net/LeGfW/2/

Option 2, serre dans la boîte après avoir séparé les cercles surmontés. Cela évite le chevauchement, mais l'emballage n'est pas optimal puisque nous ne poussons jamais les cercles l'un dans l'autre pour les forcer à étaler pour remplir la dimension longue du rectangle:
http://fiddle.jshell.net/LeGfW/3/

L'option 3, le moyen heureux, recule encore après le réglage pour le chevauchement, mais le facteur de compression est basé sur la moyenne de la pièce dans les dimensions de largeur et de hauteur, au lieu de la pièce minimale, de sorte qu'il continue à serrer jusqu'à ce que la largeur et la hauteur soient remplies:
http://fiddle.jshell.net/LeGfW/5/

Le code clé consiste en la méthode updateBubbles appelée par la coche de force et la méthode de collide appelée dans la première ligne de updateBubbles . Il s'agit de la version "option 3":

 // Create a function for this tick round, // with a new quadtree to detect collisions // between a given data element and all // others in the layout, or the walls of the box. //keep track of max and min positions from the quadtree var bubbleExtent; function collide(alpha) { var quadtree = d3.geom.quadtree(data); var maxRadius = Math.sqrt(dataMax); var scaledPadding = padding/scaleFactor; var boxWidth = width/scaleFactor; var boxHeight = height/scaleFactor; //re-set max/min values to min=+infinity, max=-infinity: bubbleExtent = [[Infinity, Infinity],[-Infinity, -Infinity]]; return function(d) { //check if it is pushing out of box: var r = Math.sqrt(d.size) + scaledPadding, nx1 = dx - r, nx2 = dx + r, ny1 = dy - r, ny2 = dy + r; if (nx1 < 0) { dx = r; } if (nx2 > boxWidth) { dx = boxWidth - r; } if (ny1 < 0) { dy = r; } if (ny2 > boxHeight) { dy = boxHeight - r; } //check for collisions r = r + maxRadius, //radius to center of any possible conflicting nodes nx1 = dx - r, nx2 = dx + r, ny1 = dy - r, ny2 = dy + r; quadtree.visit(function(quad, x1, y1, x2, y2) { if (quad.point && (quad.point !== d)) { var x = dx - quad.point.x, y = dy - quad.point.y, l = Math.sqrt(x * x + y * y), r = Math.sqrt(d.size) + Math.sqrt(quad.point.size) + scaledPadding; if (l < r) { l = (l - r) / l * alpha; dx -= x *= l; dy -= y *= l; quad.point.x += x; quad.point.y += y; } } return x1 > nx2 || x2 < nx1 || y1 > ny2 || y2 < ny1; }); //update max and min r = r-maxRadius; //return to radius for just this node bubbleExtent[0][0] = Math.min(bubbleExtent[0][0], dx - r); bubbleExtent[0][1] = Math.min(bubbleExtent[0][1], dy - r); bubbleExtent[1][0] = Math.max(bubbleExtent[1][0], dx + r); bubbleExtent[1][1] = Math.max(bubbleExtent[1][1], dy + r); }; } function updateBubbles() { bubbles .each( collide(0.5) ); //check for collisions //update the scale to squeeze in the box //to match the current extent of the bubbles var bubbleWidth = bubbleExtent[1][0] - bubbleExtent[0][0]; var bubbleHeight = bubbleExtent[1][1] - bubbleExtent[0][1]; scaleFactor = (height/bubbleHeight + width/bubbleWidth)/2; //average /* console.log("Box dimensions:", [height, width]); console.log("Bubble dimensions:", [bubbleHeight, bubbleWidth]); console.log("ScaledBubble:", [scaleFactor*bubbleHeight, scaleFactor*bubbleWidth]); //*/ rScale .range([0, Math.sqrt(dataMax)*scaleFactor]); //shift the bubble cluster to the top left of the box bubbles .each( function(d){ dx -= bubbleExtent[0][0]; dy -= bubbleExtent[0][1]; }); //update positions and size according to current scale: bubbles .attr("r", function(d){return rScale(d.size);} ) .attr("cx", function(d){return scaleFactor*dx;}) .attr("cy", function(d){return scaleFactor*dy;}) } 

Eh bien, ce n'est pas un emballage optimal, mais c'est quelque chose que d'autres peuvent essayer de battre.

Mis à jour, mais toujours pas génial

http://fiddle.jshell.net/LF9Yp/6/

Le code clé, tel qu'il est:

 var points = [[]]; //positioned circles, by row function assignNextPosition(d,index) { console.log("fitting circle ", index, d.size); var i, j, n; var radiusPlus = rScale(d.size) + padding; if (!points[0].length) { //this is first object dx = dy = radiusPlus; points[0].push(d); points[0].width = points[0].height = 2*radiusPlus; points[0].base = 0; return; } i = 0; n = points.length - 1; var tooTight, lastRow, left, rp2, hyp; while ((tooTight = (width - points[i].width < 2*radiusPlus) ||( points[i+1]? points[i+1].base - points[i].base < 2*radiusPlus : false) ) &&(i < n) ) i++; //skim through rows to see if any can fit this circle if (!tooTight) { console.log("fit on row ", i); //one of the rows had room lastRow = points[i]; j=lastRow.length; if (i == 0) { //top row, position tight to last circle and wall dy = radiusPlus; rp2 = (rScale(lastRow[j-1].size) + padding); dx = lastRow[j-1].x + Math.sqrt( Math.pow( (radiusPlus + rp2), 2) - Math.pow( (radiusPlus - rp2),2) ); } else { //position tight to three closest circles/wall //(left, top left and top right) //or (left, top left and right wall) var left = lastRow[j-1]; dx = left.x + rScale(left.size) + padding + radiusPlus; var prevRow = points[i - 1]; j = prevRow.length; while ((j--) && (prevRow[j].x > dx)); j = Math.max(j,0); if (j + 1 < prevRow.length) { console.log("fit between", prevRow[j], prevRow[j+1]); dy = prevRow[j].y + (Math.sqrt(Math.pow((radiusPlus + rScale(prevRow[j].size) +padding), 2) - Math.pow( (dx - prevRow[j].x),2) )||0); j++; dy = Math.max(dy, prevRow[j].y + (Math.sqrt(Math.pow((radiusPlus + rScale(prevRow[j].size) +padding), 2) - Math.pow( (dx - prevRow[j].x),2) )||0) ); } else { //tuck tight against wall console.log("fit between", prevRow[j], "wall"); dx = width - radiusPlus; rp2 = (rScale(prevRow[j].size) + padding); dy = prevRow[j].y + (Math.sqrt( Math.pow( (radiusPlus + rp2), 2) - Math.pow( (dx - prevRow[j].x),2) )||0); if (i > 1) dy = Math.max(dy, points[i-2].height + radiusPlus); } } lastRow.push(d); lastRow.width = dx + radiusPlus; lastRow.height = Math.max(lastRow.height, dy + radiusPlus); lastRow.base = Math.min(lastRow.base, dy - radiusPlus); } else { console.log("new row ", points.length) prevRow = points[points.length -1]; j=prevRow.length; while(j--) { var testY = prevRow[j].y + rScale(prevRow[j].size) + padding + radiusPlus; if (testY + radiusPlus < prevRow.height) { //tuck row in gap dx = prevRow[j].x; dy = testY; } } if (!dx) {//start row at left dx = radiusPlus; dy = prevRow.height + radiusPlus; } var newRow = [d]; newRow.width = dx + radiusPlus; newRow.height = Math.max(dy + radiusPlus, prevRow.height); newRow.base = dy - radiusPlus; points.push(newRow); } if (!dy) console.log("error",d); if (dy + radiusPlus > height) { //change rScale by the ratio this exceeds the height var scaleFactor = height/(dy + radiusPlus); rScale.range([0, rScale.range()[1]*scaleFactor]); //recalculate all positions points.forEach(function(row, j){ row.forEach(function(d, i) { dx = (dx - i*2*padding)*scaleFactor + i*2*padding; dy = (dy - i*2*padding)*scaleFactor + i*2*padding; }); row.width *= scaleFactor; }); } } 

Si votre principale préoccupation est de trouver un emballage serré de cercles de taille différente dans un rectangle, malheureusement, vous devrez mettre en œuvre une nouvelle mise en page d3. Je ne connais pas un plugin déjà écrit qui fera cela.

Cependant, si ce que vous cherchez est un ancien emballage dans un rectangle, vous pouvez utiliser l'algorithme d'emballage de cercle existant que d3 fournit dans d3.layout.pack . Lorsque vous spécifiez les limites de cette mise en page, vous spécifiez les dimensions d'un rectangle. D3 détermine alors un cercle que le rectangle délimitant circonscrira et utilisera ce cercle pour visualiser la racine des données hiérarchiques. Donc, ce que vous pouvez faire, c'est fournir un nœud racine "mannequin" que vous ne rendez pas réellement, et que les données réelles que vous souhaitez visualiser sont les enfants de ce noeud.

Exemple de code ci-dessous, et je l'ai également installé sur bl.ocks.org afin que vous puissiez le voir en action.

 var w = 640, h = 480; var data = { name : "root", children : [ { name: '1', size: 100 }, { name: '2', size: 85 }, { name: '3', size: 70 } , { name: '4', size: 55 }, { name: '5', size: 40 } , { name: '6', size: 25 }, { name: '7', size: 10 } , ] } var canvas = d3.select("#canvas") .append("svg:svg") .attr('width', w) .attr('height', h); var nodes = d3.layout.pack() .value(function(d) { return d.size; }) .size([w, h]) .nodes(data); // Get rid of root node nodes.shift(); canvas.selectAll('circles') .data(nodes) .enter().append('svg:circle') .attr('cx', function(d) { return dx; }) .attr('cy', function(d) { return dy; }) .attr('r', function(d) { return dr; }) .attr('fill', 'white') .attr('stroke', 'grey'); 

Il existe une meilleure façon de le faire – en utilisant l'algorithme Mitchell's Best Fit.

C'est le modèle général:

 function drawCircles() { var w = (parseInt(d3.select(".circles-div").style('width'), 10)) * 0.34, h = 350; d3.csv('dataset.csv', function(error, data) { var maxRadius = 8, // maximum radius of circle padding = 3, // padding between circles; also minimum radius margin = {top: maxRadius, right: maxRadius, bottom: maxRadius, left: maxRadius}, width = w - margin.left - margin.right, height = h - margin.top - margin.bottom; var color = d3.scale.linear() .domain([50,10]) .range(['#666','#efefef']) .interpolate(d3.interpolateHcl); var logscale = d3.scale.linear() .range([0,8]); logscale.domain([0,500]) var k = 1, // initial number of candidates to consider per circle m = 100, // initial number of circles to add per frame n = data.length, // remaining number of circles to add newCircle = bestCircleGenerator(maxRadius, padding); var svg = d3.select(".circles-div").append("svg") .attr("width", w) .attr("height", h) .append("g") .attr('class','bubbles') .attr("transform", "translate(" + margin.left + "," + margin.top + ")"); d3.timer(function() { for (var i = 0; i < m && --n >= 0; ++i) { var maxR = logscale(data[n]['Radius_value']) var circle = newCircle(k); svg.append("circle") .attr("cx", circle[0]) .attr("cy", circle[1]) .attr("r", 0) .style('fill', color(data[n]['Color_value'])) .transition() .attr("r", logscale(data[n]['Radius_value'])); if (k < 500) k *= 1.01, m *= .998; } return !n; }); function bestCircleGenerator(maxRadius, padding) { var quadtree = d3.geom.quadtree().extent([[0, 0], [width, height]])([]), searchRadius = maxRadius * 2, maxRadius2 = maxRadius * maxRadius; return function(k) { var bestX, bestY, bestDistance = 0; for (var i = 0; i < k || bestDistance < padding; ++i) { var x = Math.random() * width, y = Math.random() * height, rx1 = x - searchRadius, rx2 = x + searchRadius, ry1 = y - searchRadius, ry2 = y + searchRadius, minDistance = maxRadius; // minimum distance for this candidate quadtree.visit(function(quad, x1, y1, x2, y2) { if (p = quad.point) { var p, dx = x - p[0], dy = y - p[1], d2 = dx * dx + dy * dy, r2 = p[2] * p[2]; if (d2 < r2) return minDistance = 0, true; // within a circle var d = Math.sqrt(d2) - p[2]; if (d < minDistance) minDistance = d; } return !minDistance || x1 > rx2 || x2 < rx1 || y1 > ry2 || y2 < ry1; // or outside search radius }); if (minDistance > bestDistance) bestX = x, bestY = y, bestDistance = minDistance; } var best = [bestX, bestY, bestDistance - padding]; quadtree.add(best); return best; }; } }); } 

Voir par exemple avec des données aléatoires.