Re:Erich's Packing Center
by tshaddox on Sunday December 12, 2021 @01:20PM
(#29532072)
I’ve encountered this lovely site several times over the years, but this is the first time I’ve noticed the animated section. These animations of circles are quite satisfying: https://erich-friedman.github.io/packing/ciranima/
Re:Erich's Packing Center
by borepop on Sunday December 12, 2021 @04:10PM
(#29533648)
My stepfather (a retired professor) is endlessly fascinated by these kinds of questions. If you ever ask him at dinner "so what are you working on?" the result is often a half-hour-long explanation of how many polygons could conceivably fit into some other polygon, if it's not about how many numbers could be derived from some other set of numbers. I've never been able to understand any of it, but it makes him happy.
Re:Erich's Packing Center
by ptero on Sunday December 12, 2021 @08:51AM
(#29529584)
This is a fascinating collection (especially in-depth plots of each type), thank you for posting (and many, many thanks to the author for building this)!
You'll notice that some of the packings have a threefold rotational symmetry, but only for certain numbers of triangles: 3, 6, 9, 15, 27, 36... A quick search in OEIS yields cryptic results, probably a red herring.
Re:Erich's Packing Center
by kwhitefoot on Sunday December 12, 2021 @04:48PM
(#29533984)
It's not exactly the same but cutting shapes out of pieces of material in ways that waste as little as possible is surely related. The paper industry is very interested in a specialised subset of this kind of thing. So are factories that make transformer cores. The cores are made by stacking many (sometimes hundreds) of thin sheets of steel cut from rolls. Good quality core steel is expensive so it is important to waste as little as possible by making the cuts in the proper places.
Re:Erich's Packing Center
by sidpatil on Sunday December 12, 2021 @05:08PM
(#29534154)
These are specifically known as cutting stock problems [1].
Example of a possible application: I used to work at a home improvement retailer, and one of my responsibilities was to cut plywood boards for customers, to the dimensions they specified. I'd often wonder if the cuts I was making were optimal. The constraints were that any cuts I made had to go all the way through the entire piece, and that the blade itself was 1/8" thick.
Re:Erich's Packing Center
by madcaptenor on Monday December 13, 2021 @10:21AM
(#29540332)
A similar problem shows up in quilting - fabric comes in rolls of about 44 inches wide (called "WOF" for "width of fabric" in some patterns). (Occasionally there are other pieces - for example you can buy "fat quarters" which are 18 by 22 inches, i. e. half a yard by half WOF.) You may need many small pieces, say rectangles or triangles a few inches on a side. And so it's natural to ask what the best way to cut them is - either with minimal waste, or with making the smallest number of cuts.
Re:Erich's Packing Center
by sidpatil on Sunday December 12, 2021 @04:58PM
(#29534067)
Which field(s) of engineering did you have in mind?
One obvious application would be to find the minimum dimensions for a box to contain a number of identically-shaped physical parts. This would be a three-dimensional packing problem.
Another application could be to find out how to run the maximum number of VMs on a finite quantity of physical machines. This would be a multidimensional packing problem, possibly irregular since the VMs could have different memory, CPU, disk storage, etc. requirements.
Re:Erich's Packing Center
by yumraj on Sunday December 12, 2021 @06:49PM
(#29534932)
Amazon, or any other vendor for that matter, trying to figure out the smallest single box to ship all the items in your order using optimal packing material.
It's seem abundantly clear from real world experience that even if they have an algorithmic method to determine this, it's only 1 input into the process. Hello, amzn shipping box that is 8x larger than the single content package.
Re:Erich's Packing Center
by eezurr on Sunday December 12, 2021 @01:30PM
(#29532172)
This is lovely and made me smile. Reminds me of the (incredibly fun) times I spent on attempting to solve problems that wont necessarily have an impact on the real world (e.g. Collatz conjecture)
You'll notice that some of the packings have a threefold rotational symmetry, but only for certain numbers of triangles: 3, 6, 9, 15, 27, 36... A quick search in OEIS yields cryptic results, probably a red herring.
Example of a possible application: I used to work at a home improvement retailer, and one of my responsibilities was to cut plywood boards for customers, to the dimensions they specified. I'd often wonder if the cuts I was making were optimal. The constraints were that any cuts I made had to go all the way through the entire piece, and that the blade itself was 1/8" thick.
[1] https://en.m.wikipedia.org/wiki/Cutting_stock_problem
One obvious application would be to find the minimum dimensions for a box to contain a number of identically-shaped physical parts. This would be a three-dimensional packing problem.
Another application could be to find out how to run the maximum number of VMs on a finite quantity of physical machines. This would be a multidimensional packing problem, possibly irregular since the VMs could have different memory, CPU, disk storage, etc. requirements.
I'm sure you're right.. Other potential inputs are:
- availability of boxes and the type of packing material near the packer
- availability of space in the shipping container, so that it packs. This is again an application of the above concept. :)
- the item being shipped, fragile vs not so fragile and so on
- weight of the item, and how it fits in the container, similar to above
and so on.
Or, it is equally possible that currently there is no algorithm. the person packing just makes a judgement call :)