in reply to help with nesting

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

Replies are listed 'Best First'.
Re: Re: help with nesting
by dragonchild (Archbishop) on Oct 01, 2003 at 15:24 UTC
    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.

      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.

        This is very similar to analyzing alpha-beta trees using Treemaps. That problem isn't NP-complete. It's just annoying. :-)

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