Xref: utzoo sci.math.symbolic:1758 comp.misc:10268
Path: utzoo!attcan!uunet!cs.utexas.edu!sun-barr!newstop!texsun!digi.lonestar.org!crichmon
From: crichmon@digi.lonestar.org (Charles Richmond)
Newsgroups: sci.math.symbolic,comp.misc
Subject: Desperately Seeking Geometric Solution by Computer
Keywords: area, geometry, algorithm
Message-ID: <1048@digi.lonestar.org>
Date: 1 Oct 90 23:42:06 GMT
Followup-To: poster
Organization: DSC Communications, Plano Tx.
Lines: 71

Given a large number of rectangular pieces of sheet metal (all of
the same size), it is desired to cut out smaller rectangular pieces
of given number and dimensions.  The goals are to minimize the
number of large pieces used for cutting, and to have the largest
pieces of scrap left over with usable dimensions (i.e. width very
nearly equal to height, such as 5 x 6 instead of 30 x 1).

For example:  If the larger rectangular sheets are 20 x 30 units
and it is desired to cut five pieces of 7 x 8 and three pieces
of 10 x 12, the the following MIGHT be a solution:

  <--------- 20 ---------->          <--------- 20 ---------->

  -------------------------         ------------------------- 
  |           |           |    ^    |        |        |      |
  |           |           |    |    |  7 x 8 |  7 x 8 |      |
  |  10 x 12  |  10 x 12  |    |    |        |        |      |
  |           |           |    |    |        |        |      |
  |           |           |    |    |________|________|      |
  |___________|___________|    |    |        |         scrap |
  |           |        |  |    |    |  7 x 8 |               |
  |           |  7 x 8 |  |    30   |        |               |
  |  10 x 12  |        |  |    |    |        |     scrap     |
  |           |        |  |    |    |________|               |
  |           |________|  |    |    |                        |
  |___________|        |  |    |    |                        |
  |           |  7 x 8 |  |    |    |          scrap         |
  |           |        |  |    |    |                        |
  |  scrap    |        |  |    |    |  scrap                 |
  |           |________|  |    v    |                        |
  -------------------------         -------------------------- 


Another constraint is that the smaller pieces must be placed
to allow for "clear cuts," i.e. all cuts must pass completely
across the larger sheet of metal.  Thus a configuration like
the following would NOT be allowed:


            ----------------------------------
            |         |                      |
            |         |                      |
            |         |                      |
            |         |----------------------|
            |         |            |         |
            |         |            |         |
            |         |            |         |
            |         |            |         |
            |         |            |         |
            |----------------------|         |
            |                      |         |
            |                      |         |
            |                      |         |
            ----------------------------------


For a computer solution, it seems to be a problem for backtracking
techniques.  A solution that is "close" to the optimal placement
for the pieces will be sufficient.

If you do not know how to approach this problem (hey, we don't either),
maybe you can give some references to books or journal articles that
will be of help.

If this is not the right group to post this article, please tell me
where I can post it to find some information.

Thanks in advance for any help you can render!


       Charles Richmond           crichmon@digi.lonestar.org