←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.201s | 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 #
1. hermitcrab ◴[18 Nov 24 18:07 UTC] No.42175082[source]▶
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.