The Skyline algorithm for packing 2D rectangles

This looks useful for auto-placing parts inside a PCB.

There are all sorts of application for this. E.g. optimally cutting carpets from rolls of carpet. It is a variant on the 2D knapsack problem, one of the classic operational research problems: https://en.wikipedia.org/wiki/Knapsack_problem

The knapsack problem gets much harder as you increase the dimensions.

Placing parts on a PCB is harder if you have to care about where the components go relative to each other (e.g. because they have to be electrically connected, a certain distance from ink marking or drill holes, due to thermal or interference issues etc) rather than just optimizing space used.

Packing has so many applications for different things. Such as optimal packing of a truck or shipping container. Or how to optimally pack graphics into a GPU texture.

I had this guy as a prof. https://en.wikipedia.org/wiki/David_A._Klarner I have never encountered someone so excited about dividing up rectangles, as it is related to combinatorics. Also with such a seething hatred for floating point numbers.

3d printing build plate optimalisation, passenger transport, real estate plot division. Let's make this list longer?

Hell, I needed something like this when working on my Halloween costumes this year!

Packing things into a GPU texture is probably the #1 most common use. If you played a game today then your computer probably spent some time packing rectangles into rectangles.

A long time ago, some websites used to pack their images and use css to display a piece of the larger image. It reduced the number of round trips by not having to fetch a bunch of small files.

This "sprite sheet" style hack is still used sometimes.

I guess it's not really that necessary now that most sites load 25MB of JavaScript and a 250MB video that plays onload.

HTTP/2's multiplexing is probably the main reason we don't need sprite sheets anymore. I guess icon fonts are the modern sprite sheet to some degree.

Your web browser may have also spent some time packing rectangles into rectangles. I recall reading this article a while back about how Firefox does/did it.

https://mozillagfx.wordpress.com/2021/02/04/improving-textur...

That’s great; I’d forgotten about it.

Plus there are a fair few programs that render text by rendering the font into a texture atlas once and then using the GPU to copy from the atlas. Your terminal emulator may be doing this, for example.

The truck packing thing is one thing he was proud of. Last time I saw him he was trying to work it out for 3d. But for that particular use case many companies found that optimal packing is not necessarily the best use of time (as some value speed over total shipping volume). Sometimes just stacking it up and leaving some slack was faster. Wonder if the same sort of issues show up in GPU texture packing? I would suppose that could only pop up in some edge cases and only if you are building the textures at runtime.