Horizontal ordered bin packing of svg elements

Question

Trying to figure out the best way of bin packing/ distributing a bunch of known width svg images in a horizontal row, where they can be stacked on top of each other if the width of the container is too tight.

Height of container should optimally be self-adjusted, and the gravity should be the vertical center point. Created a few images to illustrate the desired solution.

Are there any JS library out there that solves this problem, d3 perhaps? It feels like a bin packing problem, but perhaps with some added complexity for order and gravity. Not interested in canvas solutions.

If container is wide enough

Too tight, stack some elements

Even tighter, stack all

Answer 1

What you try to achieve is a masonry layout. This is typically used when you don't know the height and number of elements. A real masonry layout will work even with variable width elements.

Here is a JSFIDDLE example (resize to see how the elements packs themselves).

A lot of codes will require some js AND still won't be real masonry, as each column will have the same width (here, or here). Though you can actually achieve this result in pure css (no js) by using a multi-column layout, alongside with media queries. However, as this is only suitable when all elements have the same width, and it seems it's not your case, I would advise you to pick one from the list below:

• https://isotope.metafizzy.co/layout-modes/masonry.html

  1. Supports a lot of features:

     1. Fit-width
     2. Horizontal/vertical ordering
     3. Gutter
     4. Fully-responsive
  2. Has a vertical (default) masonry mode and also horizontal mode
• https://masonry.desandro.com/v3/
• https://vestride.github.io/Shuffle/

• https://codepen.io/jh3y/pen/mPgyqw this one is pure css, but is trickier to use

  Here is the first one in action:

I might have forgotten some, if so, please propose in comment section, and if it is indeed a real masonry (support for variable width), in accordance to what the OP ask for, I will add it to the list.

Answer 2

For a pure D3-based SVG solution, my proposal here is using a force simulation with collision detection. The collision detection in the D3 force simulation (d3.forceCollide) is a circular one, that is, it uses the elements' radii as arguments. So, since you have square/rectangular elements, I'm using this rectangular collision detection I found.

The idea is setting the x and y positions using the simulation based on your data and the available width, with the collision based on the elements' size. Then, in the resize event, you run the simulation again with the new width.

Have in mind that, contrary to most D3 force directed charts you'll find, we don't want to show the entire simulation developing, but only the final positions. So, you'll set the simulation and stop it immediately:

const simulation = d3.forceSimulation(data)
  //etc...
  .stop();

Then, you do:

simulation.tick(n);

Or, in the resize handler, re-heating it:

simulation.alpha(1).tick(n);

Where n is the number of iterations you want. The more the better, but also the more the slower...

Here is a very crude example, move the blue handle on the right-hand side to squeeze the rectangles:

const svg = d3.select("svg");
let width = parseInt(svg.style("width"));
const data = d3.range(15).map(d => ({
  id: d,
  size: 5 + (~~(Math.random() * 30))
}));
const collisionForce = rectCollide()
  .size(function(d) {
    return [d.size * 1.2, d.size * 1.2]
  })
const simulation = d3.forceSimulation(data)
  .force("x", d3.forceX(d => (width / data.length) * d.id).strength(0.8))
  .force("y", d3.forceY(d => 100 - d.size / 2).strength(0.1))
  .force("collision", collisionForce.strength(1))
  .stop();

simulation.tick(100);

const rect = svg.selectAll("rect")
  .data(data, d => "id" + d.id);

rect.enter()
  .append("rect")
  .style("fill", d => d3.schemePaired[d.id % 12])
  .attr("x", d => d.x)
  .attr("y", d => d.y)
  .attr("width", d => d.size)
  .attr("height", d => d.size);

const drag = d3.drag()
  .on("drag", function() {
    const width = Math.max(d3.mouse(this.parentNode)[0], 70);
    simulation.nodes(data)
      .force("x", d3.forceX(d => (width / data.length) * d.id).strength(0.8))
      .stop();
    simulation.alpha(1).tick(100);
    const rect = svg.selectAll("rect")
      .data(data, d => "id" + d.id);
    rect.attr("x", d => d.x)
      .attr("y", d => d.y);

    d3.select("#outer").style("width", width + "px");
  });

d3.select("#inner").call(drag);

function rectCollide() {
  var nodes, sizes, masses
  var size = constant([0, 0])
  var strength = 1
  var iterations = 1

  function force() {
    var node, size, mass, xi, yi
    var i = -1
    while (++i < iterations) {
      iterate()
    }

    function iterate() {
      var j = -1
      var tree = d3.quadtree(nodes, xCenter, yCenter).visitAfter(prepare)

      while (++j < nodes.length) {
        node = nodes[j]
        size = sizes[j]
        mass = masses[j]
        xi = xCenter(node)
        yi = yCenter(node)

        tree.visit(apply)
      }
    }

    function apply(quad, x0, y0, x1, y1) {
      var data = quad.data
      var xSize = (size[0] + quad.size[0]) / 2
      var ySize = (size[1] + quad.size[1]) / 2
      if (data) {
        if (data.index <= node.index) {
          return
        }

        var x = xi - xCenter(data)
        var y = yi - yCenter(data)
        var xd = Math.abs(x) - xSize
        var yd = Math.abs(y) - ySize

        if (xd < 0 && yd < 0) {
          var l = Math.sqrt(x * x + y * y)
          var m = masses[data.index] / (mass + masses[data.index])

          if (Math.abs(xd) < Math.abs(yd)) {
            node.vx -= (x *= xd / l * strength) * m
            data.vx += x * (1 - m)
          } else {
            node.vy -= (y *= yd / l * strength) * m
            data.vy += y * (1 - m)
          }
        }
      }

      return x0 > xi + xSize || y0 > yi + ySize ||
        x1 < xi - xSize || y1 < yi - ySize
    }

    function prepare(quad) {
      if (quad.data) {
        quad.size = sizes[quad.data.index]
      } else {
        quad.size = [0, 0]
        var i = -1
        while (++i < 4) {
          if (quad[i] && quad[i].size) {
            quad.size[0] = Math.max(quad.size[0], quad[i].size[0])
            quad.size[1] = Math.max(quad.size[1], quad[i].size[1])
          }
        }
      }
    }
  }

  function xCenter(d) {
    return d.x + d.vx + sizes[d.index][0] / 2
  }

  function yCenter(d) {
    return d.y + d.vy + sizes[d.index][1] / 2
  }

  force.initialize = function(_) {
    sizes = (nodes = _).map(size)
    masses = sizes.map(function(d) {
      return d[0] * d[1]
    })
  }

  force.size = function(_) {
    return (arguments.length ?
      (size = typeof _ === 'function' ? _ : constant(_), force) :
      size)
  }

  force.strength = function(_) {
    return (arguments.length ? (strength = +_, force) : strength)
  }

  force.iterations = function(_) {
    return (arguments.length ? (iterations = +_, force) : iterations)
  }

  return force
};

function constant(_) {
  return function() {
    return _
  }
};

svg {
  width: 100%;
  height: 100%;
}

#outer {
  position: relative;
  width: 95%;
  height: 200px;
}

#inner {
  position: absolute;
  width: 10px;
  top: 0;
  bottom: 0;
  right: -10px;
  background: blue;
  opacity: .5;
  cursor: pointer;
}

<script src="https://d3js.org/d3.v5.min.js"></script>
<div id="outer">
  <svg></svg>
  <div id="inner"></div>
</div>

As I said, this is a very crude code, just as an example. You can tweak the strengths and improve other parts, for fitting your needs.