[HN Gopher] The Skyline algorithm for packing 2D rectangles
___________________________________________________________________
The Skyline algorithm for packing 2D rectangles
Author : lapnect
Score : 107 points
Date : 2024-11-18 15:19 UTC (7 hours ago)
(HTM) web link (jvernay.fr)
(TXT) w3m dump (jvernay.fr)
| proee wrote:
| This looks useful for auto-placing parts inside a PCB.
| hermitcrab wrote:
| 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.
| sumtechguy wrote:
| 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.
| pineaux wrote:
| 3d printing build plate optimalisation, passenger transport,
| real estate plot division. Let's make this list longer?
| amenghra wrote:
| 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.
| qingcharles wrote:
| 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.
| amenghra wrote:
| 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.
| pavel_lishin wrote:
| Hell, I needed something like this when working on my
| Halloween costumes this year!
| db48x wrote:
| 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.
| romesmoke wrote:
| An interesting variation is Dynamic Storage Allocation, in which
| the rectangles can slide only alongside one axis.
|
| AKA "static memory allocation", since the heights of the
| rectangles can be interpreted as buffer sizes, and their widths
| as lifetimes.
|
| Most of my PhD's effort has been devoted to beating the SOTA in
| this. Problem's importance nowadays is owed to deep learning's
| memory wall.
| auvi wrote:
| nice! you have your thesis or any related paper available
| online?
| alex_suzuki wrote:
| Nice, I didn't know stb had a rect packer:
| https://github.com/nothings/stb/blob/master/stb_rect_pack.h
| thanatos519 wrote:
| If you're printing randomly sized rectangles and want to cut them
| apart with a guillotine paper cutter, then the algorithm can be
| much simpler: https://github.com/trathborne/guillot
| clippy99 wrote:
| Great writeup. Sucks when this gets asked in a coding interview
| to be solved in 15min :)
| jkaptur wrote:
| Very fun. I wonder if a heap could improve the performance of the
| "loop through the skyline in order to find the best candidate
| location" step. (I think it would improve the asymptotic time, if
| I'm understanding the algorithm correctly, but obviously the real
| performance is more complex).
| chatmasta wrote:
| With some clever bit twiddling hacks, you might be able to
| avoid the loop entirely.
| mjevans wrote:
| This blog post references
| https://github.com/juj/RectangleBinPack/blob/master/Rectangl... (
| and implicitly https://github.com/juj/RectangleBinPack/ ) as it's
| primary source.
|
| The README even mentions the guillotine algorithm / method that
| someone else posted (not the same link, but the same method).
| taeric wrote:
| Fun write up, kudos!
|
| At a glance, this feels like a good case for an exact cover
| algorithm. Would be neat to see how that compares, here.
| antirez wrote:
| I wonder how well Montecarlo works with a problem like this (for
| the online version), where you try all the potential places and
| run simulations adding new random boxes similar to the one added
| so far in order to see which option allows for better outcome.
| For sure it's slow, yet it should work well, which is interesting
| per-se since it would show once more how you can come up with
| slow but good solutions just simulating stuff. But likely, this
| is how this heuristics, like Skyline, were found: analyzing the
| properties of the brute-forced best picks.
| theOGognf wrote:
| They do this in subsets of aerodynamics for optimizing the
| tradeoff between simulation speed and fidelity in cases where
| there will be a lot of runs with the same geometry but
| different parameters
| nsxwolf wrote:
| Can't wait to ask this one as a Leetcode warmup.
| Const-me wrote:
| Yeah, that algorithm is pretty good.
|
| BTW, when I needed it, I have ported C algorithm from fontstash
| library to C++: https://github.com/Const-
| me/nanovg/blob/master/src/FontStash...
| solomonb wrote:
| One of my first big personal programming projects was
| implementing this and a bunch of variations in python many years
| ago: https://github.com/solomon-b/greedypacker
|
| Its still my most starred repo. :shrug:
| TacticalCoder wrote:
| Is this an algorithm in the family of "2D bin packing"?
|
| As for packing sprites for games... I remember the fun on very
| constrained devices where many of the sprites where actually more
| round than square. So it was about packing both rectangles (for
| tiles and "rectangle" sprites) and packing circles too. The size
| of the spritesheet had to be kept small but in memory things were
| okay'ish (as in: a "round" sprite could be extracted from the
| spritesheet in its own rectangle).
|
| Thankfully thing is: this can be done with a much more powerful
| machine than the device the sprite sheet shall eventually be on.
___________________________________________________________________
(page generated 2024-11-18 23:00 UTC)