2020, 20 Oct

Figuring out Layouts Using Systems of Linear Equations

A few days ago, while writing the previous post, I needed a PhotoGallery component to display clickable previews of a set of photos. I wanted it to be zero-API, which means I pass an array of images, and it figures out a pretty layout for previews by looking at the dimensions of the images.

E.g., if the first three images in an input array are of landscape orientation, previews should be placed like this:

---------------------------  -----------------
|                         |  |  Right image  |
|                         |  |       1       |
|        Left image       |  -----------------
|                         |  -----------------
|                         |  |  Right image  |
|                         |  |       2       |
---------------------------  -----------------

Look at examples of different layouts in the previous post. You will need a tablet/desktop-sized screen.

The problem I faced was that I needed to figure out the dimensions of thumbnails based on the dimensions of original photos in each kind of layout, so that they look nice and balanced. E.g., considering the layout above, row & column gaps should be equal; both images in the right column should have equal dimensions; the sum of the heights of these two images plus a gap should be equal to the left image height; and so on.

As a first step, I expressed these requirements as equations:

liw + GAP + riw = CW
rih * 2 + GAP = lih

Where lower-case identifiers are variables:

liw — Left Image Width
lih — Left Image Height
riw — Right Image Width
rih — Right Image Height

And upper-cased identifiers are constants:

CW — Content Width. The width of the whole content column. Constant in my case, but the system can be expressed in relative values.
GAP — Gap between the columns and rows. Predefined as well.

The equations above are nothing but a system of linear equations, which can be solved using mathematical tools. However, the issue with the system in its current state is that it has four variables and only two equations.

Now, let's digress from the layout for a moment and look into the math theory.

A system of n linear equations and m variables, when n < m, can't have a single solution. It can only be reduced to a smaller number of equations. That's it. But when n == m, there are options: such a system can have one solution, an infinite number of solutions, or no solutions at all. The former system is called consistent, and the latter is inconsistent.

Getting back to my case, having four variables and two equations means that it's not possible to find a unique solution, because there isn't one. I need two more equations to be able to solve it. Luckily, there are precisely two more.

Since I deal with images with known dimensions, I can express the latter through aspect ratio.

liw / lih = LIAR
riw / rih = RIAR

Where:

LIAR — Left Image Aspect Ratio.
RIAR — Right Image Aspect Ratio.

Both are known.

Perfect. Now there are four variables and four equations, which means there is a chance that the system is solvable.

liw + GAP + riw = CW
rih * 2 + GAP = lih
liw / lih = LIAR
riw / rih = RIAR

One of the ways to solve this problem is to use the Gaussian elimination algorithm. You can think of it as a function of a system of linear equations that returns values of variables.

Gaussian elimination (system of linear equations) => values of variables

Speaking in math terms, it takes a system of linear equations in the shape of an augmented matrix, which is a combination of a matrix of coefficients and a matrix of constants. And outputs the matrix of variables—a solution, if there is one.

Gaussian elimination (augmented matrix) => variables matrix

To build an augmented matrix, the provided system should be normalized.

1 * liw +   0     * lih + 1 * riw +   0     * rih = CW - GAP
0 * liw + (-1)    * lih + 0 * riw +   2     * rih = -GAP
1 * liw + (-LIAR) * lih + 0 * riw +   0     * rih = 0
0 * liw +   0     * lih + 1 * riw + (-RIAR) * rih = 0

It is the same initial system described above, but each equation contains all the variables of the system placed in the same position in each equation. If an initial equation has no variable, its coefficient equals zero.

Coefficients matrix and constants matrix can be built by extracting coefficients from the left sides and constants from the right sides of the normalized equations.

Coefficients matrix | Constants matrix
--------------------|-----------------
1   0     1   0     |  CW - GAP
0  -1     0   2     | -GAP
1  -LIAR  0   0     |  0
0   0     1  -RIAR  |  0

An augmented matrix is the result of a concatenation of these two matrices:

1   0     1   0     CW - GAP
0  -1     0   2    -GAP
1  -LIAR  0   0     0
0   0     1  -RIAR  0

The result of Gaussian elimination is a variables matrix filled with calculated values, if the system is consistent.

liw
lih
riw
rih

The order of the values is the same as the order of variables in the normalized version of the system.

Getting back from the math world to reality, there is usually no such thing as a matrix in general-purpose programming languages. But it can be built on top of primitive data types, like arrays. The augmented matrix can be represented as an array of arrays of numbers:

[
  [1,   0   , 1,   0   ,  CW - GAP],
  [0,  -1   , 0,   2   , -GAP     ],
  [1,  -LIAR, 0,   0   ,  0       ],
  [0,   0   , 1,  -RIAR,  0       ],
]

Considering there is a function that implements Gaussian elimination, such an array can be passed to it, and the result would be an array of numbers, which are the values of the variables of the system.

Gaussian elimination

I'm not going to dive into the algorithm details here. There are dozens of links on Google on the subject. But if you'd like to use it in your code without introducing new dependencies, there is a dedicated section on RosettaCode, which has algorithm implementations in a variety of languages.