The Skyline algorithm for packing 2D rectangles
1–10 of 60 posts
Re: The Skyline algorithm for packing 2D rectangles
#2This looks useful for auto-placing parts inside a PCB.
Re: The Skyline algorithm for packing 2D rectangles
#3An 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.
Re: The Skyline algorithm for packing 2D rectangles
#4This looks useful for auto-placing parts inside a PCB.
[dead]
Re: The Skyline algorithm for packing 2D rectangles
#5This looks useful for auto-placing parts inside a PCB.
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.
Re: The Skyline algorithm for packing 2D rectangles
#6Nice, I didn’t know stb had a rect packer: https://github.com/nothings/stb/blob/master/stb_rect_pack.h
Re: The Skyline algorithm for packing 2D rectangles
#7If 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
Re: The Skyline algorithm for packing 2D rectangles
#8Great writeup. Sucks when this gets asked in a coding interview to be solved in 15min :)
Re: The Skyline algorithm for packing 2D rectangles
#9Very 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).
Re: The Skyline algorithm for packing 2D rectangles
#10This looks useful for auto-placing parts inside a PCB.
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.