Search code examples
javascripthtmlalgorithmbin-packing

Bin Packing Algorithm for Fitting HTML elements on the Screen

I recently built a web extension that can scrape HTML elements from a page and open a new tab with those elements. I came across a problem that I've been working on for hours but I'm not coming up with a good solution. Basically I want to fit these elements on the screen by arranging them somehow, while also being able to scale them. I plan to implement this algorithm in Javascript so I can use it with my web extension.

Goals:

  • Scale rectangles as uniformly as possible (ex. not scaling one down by 0.5 and another up by 5)
  • Utilize as much space as possible

Constraints:

  • Maintain aspect ratio of each rectangle
  • No rotating rectangles
  • No overlapping rectangles

Here's an example of what my extension outputted in a new tab (was trying to make a cheat sheet):

https://imgur.com/yNzIp2w

I've done a decent amount of searching into bin packing algorithms (although that's pretty new for me) and similar topics but haven't found any that include the ability to scale the rectangles.

Any help here would be much appreciated!

Solution
    • Sum the areas of all the rectangles.
    • If sum is more than, say 80%, of the available space - Scale all rectangles down so that the sum will be less than 80% of available space
    • Use a standard bin packing algorithm to pack the scaled rectangles
    • IF they still do not fit, select the largest 10% of the rectangles and scale them down some more. Repeat until all fit.

    You can experiment with the 80% and 10% to get some values that work well with your bin packing algorithm.