jGridder : how to fit elements in a sized grid

Today I want to share about jGridder : https://github.com/eloone/jgridder.

jGridder is a javascript UI component that I developed to fit a number of elements in a sized html grid.
It solves this problem :

Given a height and width and a number of items, how do I place those items as squares in a grid that fits those dimensions?

To see what I mean, peek at the demo : http://eloone.net/jgridder/demo/.

In this post I will share my approach to design the script and tackle the problem, it’s not a tutorial about the code itself. But hopefully it will enlighten and help you regarding similar problems you might have in UI. The focus will be on the method.

Motivation

I wanted to use a grid made of squares to track the progress of someone viewing a slideshow. This was part of an experimental UI concept to help users track the information they viewed. So consider that each square represents a piece of information (a photo, a tweet, a post etc.), and the goal is to represent each piece of information in a sized grid, so that you can control the graphics of your UI. The size of information is unpredictable, it’s a continuous stream that always grows. So the number of items in your grid is variable.

Approach

I approached the problem by realizing that any rectangle could be filled with small squares, even if the squares don’t cover the whole grid, like so :

If the grid dimensions are fixed, the problem boils down to calculating the dimensions of a square. So calculating the grid resumes to calculating boxDim  in the figure below. Once you find that, you can draw your grid. Before I go further, here is the reference I use in this post to make everything clearer :

> First approach : surfaces

So how to find boxDim? First approach is to reason in terms of surface. The surface of the grid is settings.width*settings.height = (cols*boxDim)*(rows*boxDim), so you immediately deduce boxDim = Math.sqrt(settings.width*settings.height/(cols*rows));

However, if you reason in terms of surface only, you don’t solve the problem because it’s possible that the squares don’t cover the grid horizontally, you might get this :

As you can see, even though the squares dimensions comply with the surface of the grid, it doesn’t mean the squares will fit inside the grid. You might get an overflow problem. Aha !

So you need to approach the problem differently. Let’s re-specify.

> Second approach : recursion

What we need, is squares covering the grid horizontally, that’s what is important to us to get a well formed grid. If the squares cover the grid horizontally, it means we need to adjust the height subsequently. That is the subtlety of the method I used, it’s all about adjusting the height to make the squares fit in the grid.

So first, to make the squares cover the grid horizontally, we set a number of columns for the grid (we’ll see later how to calculate that). For that number of columns, we check if the height overflows, and if it does we increase the number of columns to make the height drop, and so on until the height fits.

So if with 3 columns of squares, the height overflows, we increase the columns to 4, it will reduce the height. If it’s still not enough to make the height fit, we repeat the same thing, until the height is smaller than the settings height.

With this method you are assured that horizontally the squares will always fit your grid, which really renders well. As you might have detected by now, this is a recursion problem. So as you will look through my code, you will see that indeed, I used a recursive function to calculate the dimensions of the squares. Here it is :

I find the recursion method really elegant, because it’s easily understandable, you see what is going on, and I avoided the while loop because it’s often a source of bugs. I found interesting to share this recursion method, because it’s not often that I see it in use, yet it works, and it’s kinda pretty !

> Third approach : prediction

If you have followed until now, you have noticed that the call to the recursive function is calculate(2, _this_.nb_items); So why do we start with 2 ? Well, at minimum we want to have 2 columns, because we want a grid. So we start with 2 columns and increase the number of columns until the height perfectly fits. This means the number of times we would recurse would be the number of columns in total. If N is the number of items, the complexity of the recursion would be O(N^1/2), you’ll see why in a few minutes.

Such complexity is good already, but we can do way better. What if we know from the start the number of columns we need to make the height fit ? Indeed we can predict the optimum number of columns we need to create a fitting grid. Follow this quick reasoning :

So if we calculate the optimum number of columns from the start, we can start calculating our grid with this number, and at maximum it will recurse one more time to get the height right. Indeed, in the worse case, the calculated number of columns will generate a number of rows that makes the height slightly too big, the recursion is there to fix that and adjust the height accordingly. As you can see, if we predict the number of columns, we can get an O(1) complexity, which is ideal.

Illustration

So to illustrate the recursion method I just described, here is what it would look like at the first iteration :

At first iteration, the algorithm calculates a first evaluation of the number of columns there should be to make the height fit. Then it checks if with that number of columns, the height fits the grid or not, normally it does already. If not, it will trigger the second iteration where it will increase the number of columns by 1, and checks the height again, etc. until the height is finally adjusted.

So if at first iteration, the number of columns was 4, on second iteration it’s 5 :

Note that I also introduced a “border” parameter. The border parameter exists to calculate precisely the size of the squares in “real” conditions where the grid is gonna render in html/css. Indeed, don’t forget a border is going to be applied, so we need to take it into account in our calculations.

Code

I’m not going to be heavy on the code, but here are some useful comments related to it.

It is very important to pre-calculate the grid and therefore to separate calculations from any DOM operations to not cause browser reflow. I know it might be tempting to first create your html element and then compare the calculated dimensions against the real dimensions returned by the DOM and iterate like that. However since there is recursion, – even if minimised here – by doing so you will tire your browser by causing it to always redraw your grid until it is well formed. For this reason, it is really better to do all the calculations before hand, it’s faster and it’s a good practice.

Also a note about how the grid renders. The normal way for the grid to render would be like this :

However since I needed to use it as a tracker (see example in next section), I needed it to be flipped. Let me tell you that it was some mind gymnastics to find a clean way of doing so without messing with the navigation. I went through all kinds of different stages, including reversing an array to keep the navigation consistent. Let me spare you the exhausting workout. Actually the solution lies in the magic of css. Yes, just that ! As you will see in the code, to get the flipped grid, you just need to apply float:right on the row container. See https://github.com/eloone/jgridder/blob/master/css/grid.css for the minimal css you need to get it working.

What to do with this?

So basically this just draws a grid. What to do with that? Well, initially I built the script as part of another script to make slideshows, so I had an idea already of how to use it. But I isolated it afterwards because it could be used for other things and and it’s an interesting UI case study. Here is an example of how you could use it :
http://machinesaredigging.com/2013/04/18/my-first-time-in-america-ah/#slideshow-72157633096294423.

Basically the script returns an object of this form :

{
  node : '[object]', //the jquery node for the grid container => $('.grid')
  items : [ //array of all the boxes in the grid
   ...
    {
      node : '[object]', //jquery node for a box in the grid, => $('.box')
      index : '[int]' //index of the box in the grid
    },
    {
      node : '[object]', //jquery node for a box in the grid,
      index : '[int]' //index of the box in the grid
    }
    ...
  ]
}

You can use this to do all kinds of tricks. This structure might not be final, but for now it does the job. See the github page for more details. Voilà !

That’s all folks !

So that’s it. I had a blast designing this script. This article was not meant to be a tutorial on how to code, but it was rather to focus on the most interesting part, how to design. Once you understand the method, you can reapply it to your own problem and in your own language, fantastic right ? If however you need some guidance about the code itself, you can read the script, I heavily commented it. I’m not a big fan of the scripts that fly around out there without any insight on how they function. I hope I can bring you guys a little more than a mere javascript file. Let’s give the code some spirit !

The beautiful graphics here were produced by using photoshop combined with keynote + my adorable wacom tablet “Wacom Bamboo Pen & Touch CTH-470K” that I’m still learning to use. If you know an app I could use to produce the same kind of graphics easily, please post in the comments, I’m interested !

If you want to effectively use jGridder, you can head over its github page and follow the readme: https://github.com/eloone/jgridder. Enjoy !