javascript - framework - Embalaje de círculos de diferentes tamaños en un rectángulo-d3.js

jquery d3

Question

d3.js círculos de diferentes tamaños en un contenedor rectangular , sin empacar en un contenedor circular con d3.js empaquetado con, bajo d3.layout.pack .

aquí está el diseño que quiero lograr:

Encontré este artículo sobre este tema, pero no soy matemático para entender el artículo a fondo y convertirlo en código ...

Cualquiera puede sugerir dónde debería comenzar a convertir esto en el complemento de diseño d3.js, o si ha visualizado burbujas similares a este diseño, sugiera cualquier dirección que haya tomado para resolverlo.

Gracias.

Answer 1

Aquí hay un avance en la implementación de su algoritmo.

Lo puse un poco, pero creo que básicamente es lo mismo.

Círculos delimitadores

Usé un truco para hacer que el cálculo sea más regular.

En lugar de segmentos que definen el cuadro delimitador, utilicé círculos con radios "infinitos", que pueden considerarse una buena aproximación de líneas:

La imagen muestra cómo se ven los 4 círculos delimitadores cuando se reduce el radio. Se calculan para pasar a través de las esquinas del cuadro delimitador y convergen hacia los lados reales cuando el radio crece.

Los círculos de "esquina" (como los llama el algoritmo) se calculan como tangentes a un par de círculos, eliminando así el círculo especial + segmento o segmento + segmento de casos.

Esto también simplifica enormemente la condición de inicio.
El algoritmo simplemente comienza con los cuatro círculos delimitadores y agrega un círculo a la vez, usando el parámetro heurístico lambda codicioso para elegir la "mejor" ubicación.

La mejor estrategia de ajuste

El algoritmo original no produce el rectángulo más pequeño para contener todos los círculos
(simplemente intenta encajar un grupo de círculos en un rectángulo dado).

He añadido una búsqueda dicotómica simple en la parte superior para adivinar la superficie mínima (que produce el rectángulo delimitador más pequeño para una relación de aspecto determinada).

El código

Aquí hay un violín

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*B-C*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 -u.y * y, base.y + u.x * y);
            var p2 = new Point (base.x +u.y * y, base.y - u.x * 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; 
    }
};

Actuación

El código no está optimizado para favorecer la legibilidad (o eso espero :)).

El tiempo de cálculo aumenta de forma bastante pronunciada.
Puede colocar de forma segura unos 20 círculos, pero cualquier valor superior a 100 hará que el navegador rastree.

Por alguna razón, es mucho más rápido en Firefox que en IE11.

Eficiencia de embalaje

El algoritmo funciona bastante mal en círculos de tamaño idéntico (no puede encontrar el patrón de nido de abeja famoso para 20 círculos en un cuadrado), pero bastante bien en una amplia distribución de radios aleatorios.

Estética

El resultado es bastante desgarbado para círculos de tamaño idéntico.
No hay ningún intento de juntar los círculos, de modo que si el algoritmo considera dos posibilidades equivalentes, una se elige al azar.

Sospecho que el parámetro lambda podría refinarse un poco para permitir una elección más estética en caso de valores iguales.

Posibles evoluciones

Con el truco de "radios infinitos", es posible definir un polígono delimitador arbitrario.

Si proporciona una función para verificar si un círculo encaja en dicho polígono, no hay ninguna razón para que el algoritmo no produzca un resultado.

Si este resultado sería eficiente es otra pregunta :).

Answer 2

Bueno, esto está lejos de ser un embalaje óptimo, pero es algo que otros pueden intentar superar.

Actualizado, pero aún no es genial

https://jsfiddle.net/LF9Yp/6/

Código clave, como es:

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
       d.x = d.y = 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
            d.y = radiusPlus;
            rp2 = (rScale(lastRow[j-1].size) + padding);
            d.x = 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];
           d.x = left.x + rScale(left.size) + padding + radiusPlus;
           var prevRow = points[i - 1];       
           j = prevRow.length;
           while ((j--) && (prevRow[j].x > d.x));
           j = Math.max(j,0);
           if (j + 1 < prevRow.length) {
               console.log("fit between", prevRow[j], prevRow[j+1]);
               d.y = prevRow[j].y 
               + (Math.sqrt(Math.pow((radiusPlus + 
                           rScale(prevRow[j].size) +padding), 2) 
                           - Math.pow( (d.x - prevRow[j].x),2)
                       )||0);
              j++;
              d.y = Math.max(d.y, prevRow[j].y 
               + (Math.sqrt(Math.pow((radiusPlus + 
                           rScale(prevRow[j].size) +padding), 2) 
                           - Math.pow( (d.x - prevRow[j].x),2)
                       )||0)  );
           }
           else { //tuck tight against wall
               console.log("fit between", prevRow[j], "wall");
            d.x = width - radiusPlus;
            rp2 = (rScale(prevRow[j].size) + padding);
            d.y = prevRow[j].y + (Math.sqrt(
                Math.pow( (radiusPlus + rp2), 2)
                - Math.pow( (d.x - prevRow[j].x),2) )||0);
            if (i > 1)
                d.y = Math.max(d.y, points[i-2].height + radiusPlus);
           }
        }

        lastRow.push(d); 
        lastRow.width = d.x + radiusPlus;
        lastRow.height = Math.max(lastRow.height, 
                                  d.y + radiusPlus);
        lastRow.base = Math.min(lastRow.base,
                                d.y - 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
                d.x = prevRow[j].x;
                d.y = testY;
            }
        }
        if (!d.x) {//start row at left
          d.x = radiusPlus;
          d.y = prevRow.height + radiusPlus;
        }
        var newRow = [d];
        newRow.width = d.x + radiusPlus;
        newRow.height = Math.max(d.y + radiusPlus, prevRow.height);
        newRow.base = d.y - radiusPlus;
        points.push(newRow); 
    } 
            if (!d.y) console.log("error",d);
    if (d.y + radiusPlus > height) {
      //change rScale by the ratio this exceeds the height
      var scaleFactor = height/(d.y + radiusPlus);
      rScale.range([0, rScale.range()[1]*scaleFactor]);

      //recalculate all positions
      points.forEach(function(row, j){
            row.forEach(function(d, i) {
               d.x = (d.x - i*2*padding)*scaleFactor + i*2*padding;
               d.y = (d.y - i*2*padding)*scaleFactor + i*2*padding;
            });
            row.width *= scaleFactor;
      });

    }

}

Answer 3

Hay una manera mucho mejor de hacerlo: usar el algoritmo Best Fit de Mitchell.

Este es el patrón general:

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;
      };
    }

    });

  }

Ver por ejemplo con datos aleatorios.

Answer 4

Si su principal preocupación es encontrar un paquete ajustado de círculos de diferentes tamaños dentro de un rectángulo, desafortunadamente tendrá que implementar un nuevo diseño d3. No sé de un complemento que ya está escrito que hará esto.

Sin embargo, si lo que está buscando es un embalaje viejo en un rectángulo, entonces puede usar el algoritmo de empaque de círculo existente que proporciona d3 en d3.layout.pack . Cuando especifica los límites para este diseño, especifica las dimensiones de un rectángulo. d3 luego determina un círculo que circunscribirá el rectángulo delimitador, y usa ese círculo para visualizar la raíz de los datos jerárquicos. Entonces, lo que puede hacer es proporcionar un nodo raíz "ficticio" que en realidad no represente, y que los datos reales que desea visualizar sean hijos de ese nodo.

Codifique el ejemplo a continuación y también lo publico en bl.ocks.org para que pueda verlo en acción.

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 d.x; })
    .attr(''cy'', function(d) { return d.y; })
    .attr(''r'', function(d) { return d.r; })
    .attr(''fill'', ''white'')
    .attr(''stroke'', ''grey'');

Answer 5

Un enfoque completamente diferente ...

Como mencioné en un comentario, un diseño de d3 cluster-force podría adaptarse a un método heurístico para ajustar los círculos en la caja, cambiando progresivamente la escala hasta que tenga un ajuste ceñido.

Los resultados hasta ahora no son perfectos, entonces presento algunas versiones:

La opción 1, comprime la casilla en el espacio ocupado por los círculos antes de ajustar la superposición de círculos. El resultado es muy compacto, pero con una ligera superposición entre círculos que quedan atrapados entre las paredes de la caja y entre ellos, incapaces de moverse sin un conflicto:
https://jsfiddle.net/LeGfW/2/

Opción 2, aprieta en el cuadro después de separar los círculos superpuestos. Esto evita la superposición, pero el empaque no es óptimo ya que nunca empujamos los círculos el uno hacia el otro para forzarlos a extenderse para llenar la dimensión larga del rectángulo:
https://jsfiddle.net/LeGfW/3/

La opción 3, el medio feliz, vuelve a apretarse después de ajustar la superposición, pero el factor de compresión se basa en el promedio de la habitación en dimensiones de ancho y alto, en lugar de la habitación mínima, por lo que sigue apretando hasta llenar el ancho y la altura:
https://jsfiddle.net/LeGfW/5/

El código clave consiste en el método updateBubbles llamado por el tick de fuerza y ​​el método collide que se llama en la primera línea de updateBubbles . Esta es la versión de la "opción 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 = d.x - r,
        nx2 = d.x + r,
        ny1 = d.y - r,
        ny2 = d.y + r;

      if (nx1 < 0) {
           d.x = r;
      }
      if (nx2 > boxWidth) {
           d.x = boxWidth - r;
      }
      if (ny1 < 0) {
           d.y = r;
      }
      if (ny2 > boxHeight) {
           d.y = boxHeight - r;
      }


    //check for collisions
    r = r + maxRadius, 
        //radius to center of any possible conflicting nodes
        nx1 = d.x - r,
        nx2 = d.x + r,
        ny1 = d.y - r,
        ny2 = d.y + r;

    quadtree.visit(function(quad, x1, y1, x2, y2) {
      if (quad.point && (quad.point !== d)) {
        var x = d.x - quad.point.x,
            y = d.y - 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;
          d.x -= x *= l;
          d.y -= 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], 
                                  d.x - r);
    bubbleExtent[0][1] = Math.min(bubbleExtent[0][1], 
                                  d.y - r);
    bubbleExtent[1][0] = Math.max(bubbleExtent[1][0], 
                                  d.x + r);
    bubbleExtent[1][1] = Math.max(bubbleExtent[1][1], 
                                  d.y + 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){
            d.x -= bubbleExtent[0][0];
            d.y -= 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*d.x;})
        .attr("cy", function(d){return scaleFactor*d.y;})
}