|
Re: help with nesting
by dragonchild (Archbishop) on Oct 01, 2003 at 14:00 UTC
|
Try looking up a few algorithms or talking to a Math professor. This is a solved problem with some very neat solutions.
Of course, you could always brute-force it, trying all combinations and picking the one that takes the least area. I might take a stab at this later ...
------
We are the carpenters and bricklayers of the Information Age. The idea is a little like C++ templates, except not quite so brain-meltingly complicated. -- TheDamian, Exegesis 6 Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.
| [reply] |
|
|
Hint for brute force optimization: arrange the pieces with the largest extents in either direction first. Also, for geek karma, try to do it using the regex engine, Abigail style. :)
Makeshifts last the longest.
| [reply] |
Re: help with nesting
by bart (Canon) on Oct 01, 2003 at 16:14 UTC
|
| [reply] |
|
|
It would be if the problem was worded as so:
I have a piece of 8.5 x 11 paper and a set of rectangles to cut. Tell me either one:
- How many rectangles can I fit on the paper?
- What is the fewest number of cuts for the largest number of rectangles?
The problem, as stated, is different. "Given a set of rectangles, what is the smallest piece of paper that will encompass all the rectangles with the smallest amount of waste?" The reason this isn't a Knapsack is because the overall paper-size isn't constricted. (At least, the OP didn't restrict it in the statement.)
------
We are the carpenters and bricklayers of the Information Age. The idea is a little like C++ templates, except not quite so brain-meltingly complicated. -- TheDamian, Exegesis 6 Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.
| [reply] |
Re: help with nesting
by Abigail-II (Bishop) on Oct 01, 2003 at 14:46 UTC
|
This smells very much like an NP-complete problem. I'd be
very surprised if the problem isn't known in the literature.
I am although a bit confused by the 'least amount of wasted
space' requirement. If you have 4 4x6 and 6 2x9 rectangles,
it's going to take 252 area. If your big rectangle has area
N, and the smaller rectangles fit, you will be wasting
N - 252 space. No matter how you fit them.
Abigail | [reply] |
|
|
The question is how close can (N - 252) -> 0? This problem isn't NP-complete. I'll post a solution after lunch.
------
We are the carpenters and bricklayers of the Information Age. The idea is a little like C++ templates, except not quite so brain-meltingly complicated. -- TheDamian, Exegesis 6 Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.
| [reply] |
|
|
According to NIST, the Cutting Stock Problem is NP-Complete.
The are several agressive optimisations that can be applied, but the basic status of the problem remains...unless you know different:)
Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." -Richard Buckminster Fuller
If I understand your problem, I can solve it! Of course, the same can be said for you.
| [reply] |
|
|
Re: help with nesting
by dragonchild (Archbishop) on Oct 01, 2003 at 16:51 UTC
|
The following is a quick stab at the problem. It doesn't claim to create the best possible mapping. In fact, it only takes two stabs at the problem - once in the horizontal and once in the vertical. But, it does provide quite a good starting point. It also works very quickly.
------
We are the carpenters and bricklayers of the Information Age. The idea is a little like C++ templates, except not quite so brain-meltingly complicated. -- TheDamian, Exegesis 6 Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.
| [reply]
[d/l]
[select] |
|
|
Thanks, and I apologize if I was not specific about the problem. Lets say I have a piece of paper 8.5x11 and a set of rectangles {(x,y,n),(x1,y1,n1),(x2,y2,n2)} x=base, y=height, n=number of these. I am trying to fit as many of these rectangles onto the paper as I can.
I guess that I also need to add in a "profit" aspect, because I would like to have the least amount of cuts possible. Thanks again and any help is greatly appreciated.
| [reply] |
|
|
That problem statement is a variation of the Knapsack problem. Your initial constraint is the 8.5x11 size and you have an additional constraint of aligning the sides as much as possible. The code I posted does accidentally align the sides of the rectangles, but provides no constraints on the size.
I might play around with it a bit to provide the paper-size constraint, but you'd be better off following the googlinks that others have provided.
Update: You can try the following algorithm to see if it helps:
- Get your paper size
- Get your list of rectangles. Collapse it to (x,y,n) if you don't already have it that way.
- Eliminate all rectangles that cannot fit on the paper. E.g., 1x12 won't fit on 8.5x11, but will fit on 8.5x14
- Reduce the number of rectangles of a given size to the most that can fit on your paper. For example, two 6x11 rectangles cannot fit on the same 8.5x11 piece of paper
- Expand the list of rectangles so that (x,y,n) => (x,y) x n
- Order the remaining rectangles by area, smallest first, then by X, smallest first
- Start tiling in the X direction, filling the Y direction and see what comes out
- Re-order the rectangles by area, then Y (smallest first in both values)
- Repeat, but in the Y direction filling the X direction.
- Repeat the two tilings, swapping each particular rectangle's orientation. (($x, $y) = ($y, $x);) This will result in N! tilings, where N is the total number of rectangles (of all sizes) you're working with
- This problem is O(n!), which is pretty crappy. It's also (at least) NP-hard, so you can't really prove this algorithm will provide the best solution. It might provide a good base for a human to take and improve upon, but that's the best it could possibly do.
------
We are the carpenters and bricklayers of the Information Age. The idea is a little like C++ templates, except not quite so brain-meltingly complicated. -- TheDamian, Exegesis 6 Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.
| [reply]
[d/l] |