Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Skyline algorithm for packing 2D rectangles

jvernay.fr

Post reply on HN
Print view View original

21–30 of 60 posts

Re: The Skyline algorithm for packing 2D rectangles

#21

Post by theOGognf »

antirez wrote: post #18

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 simula…

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

Re: The Skyline algorithm for packing 2D rectangles

#22

Post by amenghra »

pineaux wrote: post #15
sumtechguy wrote: post #10

Earlier quoted context omitted.

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?

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.

Re: The Skyline algorithm for packing 2D rectangles

#23

Post by qingcharles »

amenghra wrote: post #22
pineaux wrote: post #15

Earlier quoted context omitted.

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

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.

Re: The Skyline algorithm for packing 2D rectangles

#26

Post by amenghra »

qingcharles wrote: post #23
amenghra wrote: post #22

Earlier quoted context omitted.

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.

Re: The Skyline algorithm for packing 2D rectangles

#27

Post by TacticalCoder »

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.

Re: The Skyline algorithm for packing 2D rectangles

#28

Post by mikepurvis »

clippy99 wrote: post #8

Great writeup. Sucks when this gets asked in a coding interview to be solved in 15min :)

To be fair, in an interview context they’re probably looking for what you would implement in the mvp just to avoid getting blocked, and a brief acknowledgement that it’s an academic problem and once you have data to understand it better you’ll select and implement an appropriate algorithm after design review with colleagues.

Re: The Skyline algorithm for packing 2D rectangles

#30

Post by joshtynjala »

db48x wrote: post #20
sumtechguy wrote: post #10

Earlier quoted context omitted.

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.

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.

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...

Post reply on HN