Simple Square Packing Algorithm
In a recent project the design asked for a component which shows a small number of values in squares. It was important to represent the relation between the values, so they should be mapped to the area and not the size of the squares.
My initial read of the design was: largest value in the center, then increasingly smaller values packed around it. I knew that there would be fewer than about 7 distinct values. And the domain wouldn’t be too wide (all values between zero and one, roughly). Furthermore, these charts are rendered once each can be reviewed for correctness before the whole website is published. There was no need to have a fancy algorithm which would work for arbitrary input.
Given these constraints, my approach was to write a simple algorithm to pack these squares: place the largest value in the center, and pack the rest (in decreasing value) such that each new square shares at least one edge with an existing square.
Use D3 Force Layout?
I was briefly considering using D3 force layout. But it seemed overkill, because of the static nature of the underlying data: the number of values doesn’t change and the values themselves don’t change. There was no need to make the behavior dynamic at runtime. Once the squares are placed their position and size won’t change. D3 force layout uses an iterative approach and is more expensive than a simple algorithm which iterates over the data once.
The Algorithm
Placing the first square is simple: straight in the middle of the canvas. The algorithm for all remaining squares is the same:
- Find the vertex that is closest to the centroid of the figure.
- The second vertex needs to be along one of the edges which is going out of this first vertex. Pick one direction, it doesn’t matter. Given that we pack the values in decreasing order, we have a guarantee that the edge of the new square will be shorter than the existing edge.
- The third vertex is on the edge which goes into the other direction. Here we have the first complications: First the case where the two edges are parallel, and second when we know that the resulting square would overlap its neighbor. But these problem are easy to solve with a bit of math.
- The fourth vertex is given by the other three.
The most difficult part is the first step. For that we need a list of all existing vertices — the outline of the whole figure. I could compute the outline at the beginning of each step. That would be most robust, but I opted for a solution which is a bit simpler: keep a list of vertices which make up the outline and manually update it at the end of each step.
The complexity of the algorithm is O(n). And given that the number of input values is expected to be in the single-digit range, it is very cheap.
The Edge Cases
That algorithm is pretty much guaranteed to work for up to five values. Unfortunately there are edge cases where it stops working properly, the symptoms are that it places squares on top of each other. There are two causes:
- Once the algorithm picks the first vertex, it’s committed to placing the square at that location. But there are cases where there isn’t enough space around. The algorithm doesn’t backtrack and pick the second closest vertex (or even one farther away from the centroid).
- There are cases where manually updating the outline doesn’t work correctly. Remember when I said that we have a guarantee that the edge of the new square will be shorter than the existing edge? Yeah, that’s not always true. The algorithm would be more robust if I calculated the outline at the beginning of each step from the list of squares that have already been placed on the canvas, but it would increase the code size.
The Code
The original source code is available in my simple-square-packing repository on GitHub. It is written in TypeScript. When compressed with the Google Closure Compiler, it’s only 3.1KB in size.
The repository contains some example code which uses the algorithm to calculate the placement and D3 to render the result (while rotating the whole group by 90 degrees, as required by the design). You can play with the example in the playground or on bl.ocks.org. In this playground you can supply your own list of values and the SVG shows the squares as well as some additional information which is useful: the extent of the whole figure, the exact outline, and the centroid of the whole figure.
Playground
Below are a few screenshots from the playground which I used to test whether the algorithm works correctly when given a particular list of values. The rendering also shows additional useful information about the chart: centroid (blue dot), outline (red line), and extent (green line).
In the next screenshot you see 11 distinct values being shown in the chart. Adding one more value will cause two squares to overlap. See for yourself!
Next up is an example of what happens when the algorithm first breaks down. Two squares are placed on top of each other.
Attempting to render many values (>30) exhibits interesting behaviour patterns. Each value you add or remove in this example causes seemingly unpredictable changes in the chart. Delete the last value and observe what happens! It also show that the code which updates the outline (the red line) is not robust enough to handle all edge-cases.
