Algorithm of "newspaper" layout of the web page

This post is specifically written in a personal blog, so as not to clog the general.

There was a problem at work: there are a number of articles, perhaps with pictures, and just pictures, and this bunch of good stuff should be automatically wrapped onto a web page in a newspaper format - that is, in several columns, one article in one column, another - in three, but less in height. And all the pictures fit into the columns to look exactly like the spread of the newspaper.
For some reason I do not want to believe that I am the first who faced this task. This does not negate the fact that I already have some idea of ​​the algorithm;) Nevertheless, I would like to hear those who have already encountered such a task. Or just those to whom the task seemed interesting. Yes, anyone, really, really =)

Let's get started
')
0) Baseline
Suppose we have a certain set of articles \ pictures. Each article can also (but not required) to be images. There is the width of the newspaper page, say 1000px. And there is the number of columns into which this page should be divided.

General idea:
The page is divided into "squares" (a certain analogue of parrots from the famous cartoon). Those. if we have five columns, then the column width is 200px, and the height of the box, respectively, is also 200 px. As a result, we get a rectangle of 5 squares in width and infinity in height. Then there is a miscalculation of all the different options for the size of the content - for example, the same article can be made as a 1x4 square, and 2x2, and 4x1 - that is, the area is the same. But you should look at two subtle points:
a) If there are pictures in the article, then they need to be resized / sprinkled, making its width a multiple of the column width, and only then consider the total area;
b) It is necessary to count the area occupied by the text, MANDATORY starting from the width of the characters of the font - otherwise we risk “rounding out” with all sorts of word breaks.
As a result, after all the calculations, we have a set of elements with variations in their size, which need to be optimally entered into a rectangle with a fixed width - this is no longer a problem. Although the simplest search of options =) Then the result (by the way, maybe not one optimal location, then you can give some randomly) we cache and give the user a static header, in which the articles are in marvels with hard-coded dimensions pixels. When a new article arrives, the pictures - and r-times, and two, and three - to the original! - repeat the procedure.

In summary, a brief algorithm:
1. Calculation of options for the areas of articles, images in them and "stand-alone" images;
2. The choice of the optimal (second \ s) option (s \ s) location.

It looks not particularly difficult, but I want (including for myself) to speak the main points.

1) Separate images
These are the ones that are not in the article, but just pictures. With them, in my opinion, the easiest way is that we either resize them or sprinkle them to the width we need, the height remains proportional.
There is, by the way, another little idea (for the future) - since you want a complete resemblance to a newspaper, you can write headlines in pictures (using dd, for example). But I was distracted, this is all sometime later, and even that is not a fact =)

2) Fonts
It seems that one cannot do without the widths of the characters of the font - otherwise it will not be possible to calculate the volume of the article. Consequently, we need the functionality of working with fonts - for example, some kind of server tool launched by PHP exec, or a parser of .ttf files, it doesn't matter. These are implementation details, but all the character widths of the fonts should be in the database (it is clearly faster to kick it than the parser).

3) Images in articles
Occupy a certain area. So far, I am of the opinion that they should be driven into a corner, and then inserted into the text and counted the total area in “squares”. Again, the image can be stretched to a different number of squares, so that options are also possible here.
Also do not forget that there can be many images. In this case, while I find it difficult ... I must think more. Ideas are accepted.

4) Search for the best location option
I do not see anything difficult - going through all the options for the location of all the options for the elements, and, in fact, voila.

So, returning to - why did I write this.
I'd like to hear any tips, hints and other such things. In return, I promise, when everything is ready (and it will be, that's for sure), lay out a link for the public.
If suddenly there is someone who is faced with a similar task - this person will be worth my weight in gold;)
Anyway ... Agree, this is not a trivial task? ;) And the brain is always interesting to stretch. Personally, I, at least, am happy with this project - if I think, then I exist =)
Anyway, thanks to everyone who mastered this text. I tried to write as clearly as possible, but if I did not succeed, I will answer any question on the merits in the comments.