←back to thread

The Skyline algorithm for packing 2D rectangles

(jvernay.fr)
218 points lapnect | 10 comments | 18 Nov 24 15:19 UTC | HN request time: 0.62s | source | bottom
Show context
proee ◴[18 Nov 24 16:57 UTC] No.42174294[source]▶
This looks useful for auto-placing parts inside a PCB.
replies(3): >>42175009 #>>42175082 #>>42175440 #
1. sumtechguy ◴[18 Nov 24 18:36 UTC] No.42175440[source]▶
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.

replies(3): >>42177042 #>>42177196 #>>42177491 #
2. pineaux ◴[18 Nov 24 21:07 UTC] No.42177042[source]▶
3d printing build plate optimalisation, passenger transport, real estate plot division. Let's make this list longer?
replies(1): >>42177595 #
3. pavel_lishin ◴[18 Nov 24 21:22 UTC] No.42177196[source]▶
Hell, I needed something like this when working on my Halloween costumes this year!
4. db48x ◴[18 Nov 24 21:51 UTC] No.42177491[source]▶
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.
replies(2): >>42178568 #>>42183041 #
5. amenghra ◴[18 Nov 24 22:01 UTC] No.42177595[source]▶
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.
replies(1): >>42177651 #
6. qingcharles ◴[18 Nov 24 22:08 UTC] No.42177651{3}[source]▶
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.

replies(1): >>42177858 #
7. amenghra ◴[18 Nov 24 22:37 UTC] No.42177858{4}[source]▶
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.
8. joshtynjala ◴[18 Nov 24 23:51 UTC] No.42178568[source]▶
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...

replies(1): >>42178684 #
9. db48x ◴[19 Nov 24 00:05 UTC] No.42178684{3}[source]▶
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.

10. sumtechguy ◴[19 Nov 24 13:13 UTC] No.42183041[source]▶
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.