←back to thread

The Skyline algorithm for packing 2D rectangles

(jvernay.fr)
218 points lapnect | 1 comments | 18 Nov 24 15:19 UTC | HN request time: 0.202s | 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. 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.