Horizontal ordered bin packing of svg elements
Asked Answered
N

2

18

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

Nailbrush answered 31/8, 2016 at 0:48 Comment(4)
how about treemap: bl.ocks.org/mbostock/4063582?Lubricate
Did you ever find a solution for this? I am looking for one now.Gaeta
One solution to your problem: Using svg elements with a wiewBox attribute and no width or height and the columns layout.Ethnogeny
@Gaeta the closest I came was using flexbox like this: 8p528.csb.app (resize the window). Source codesandbox.io/s/nifty-grass-8p528?fontsize=14Nailbrush
C
9

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.

Chelseachelsey answered 7/11, 2019 at 4:34 Comment(5)
As already discussed in the comments, you can use HTML-wrapped SVG images with flexbox Nope, this is wrong. Please see this question. It won't work with svg of different heights. So some would advise to use grid, but grid wouldn't work with svg of different widths. About your svg/D3 examples, there are really great, but I think they are more adapted for animations, not really for a layout problem, it's a bit overkill ^^Iceland
@Iceland flexbox does indeed work with different heights, see 8p528.csb.app . But the result is not as nice as the JS solution proposed hereNailbrush
Well, no, literally, the line heights are all the same, i.e. you can't vertically pack multiple svgs in a row even they are small enough to fit.Iceland
@Iceland misread your comment, that is correct! The flexbox way is more like a 80% solutionNailbrush
@Gerardo Furtado thanks for the answer. With a little tweaking I think it's possible to achieve what I was looking for... when I asked the question 3 years ago!Nailbrush
I
9

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:

Horizontal masonry (the one you're looking for Vertical masonry

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.

Iceland answered 5/11, 2019 at 19:32 Comment(1)
Why -1 ? It is the most relevant answer, corresponding exactly to what the OP want. The masonry layout is the right (and best) way to go for it !Iceland
C
9

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.

Chelseachelsey answered 7/11, 2019 at 4:34 Comment(5)
As already discussed in the comments, you can use HTML-wrapped SVG images with flexbox Nope, this is wrong. Please see this question. It won't work with svg of different heights. So some would advise to use grid, but grid wouldn't work with svg of different widths. About your svg/D3 examples, there are really great, but I think they are more adapted for animations, not really for a layout problem, it's a bit overkill ^^Iceland
@Iceland flexbox does indeed work with different heights, see 8p528.csb.app . But the result is not as nice as the JS solution proposed hereNailbrush
Well, no, literally, the line heights are all the same, i.e. you can't vertically pack multiple svgs in a row even they are small enough to fit.Iceland
@Iceland misread your comment, that is correct! The flexbox way is more like a 80% solutionNailbrush
@Gerardo Furtado thanks for the answer. With a little tweaking I think it's possible to achieve what I was looking for... when I asked the question 3 years ago!Nailbrush

© 2022 - 2024 — McMap. All rights reserved.