←back to thread

The Skyline algorithm for packing 2D rectangles

(jvernay.fr)
218 points lapnect | 2 comments | 18 Nov 24 15:19 UTC | HN request time: 0.473s | source
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 #
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 #
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 #
1. 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 #
2. db48x ◴[19 Nov 24 00:05 UTC] No.42178684[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.