Programmers Contest: Fit pictures on a page

[Dan Sommers]

On Wed, 29 Jun 2005 19:43:33 -0400,
Roy Smith <roy at panix.com> wrote:

> Not just plywood panels, but sheets of paper, bolts of cloth, sheet
> metal, plate glass, etc.  A slight complication is that some materials
> have a preferred orientation (i.e. plywood has a grain, textiles have
> warp vs.  weft, etc) and some don't (or it doesn't matter for the
> application).

> It gets even more interesting when you're restricted to making cuts
> that start at an edge, or go all the way through the sheet to the
> other side.

I ran into this problem when I worked at a small computer store back in
1979 or 1980.  One of our customers owned a plastics plant, and found
such a program, and wanted us to install it and maintain it (on an 8080
or a Z-80 running CP/M, no less).

The first release only did rectangles, and assumed flawless material, so
his first trial was to tell the program about a 4 x 8 foot sheet of
plastic, and ask for two 4 x 4 pieces.  The program refused, because a
saw blade has a non-zero width.  But he had mis-specified the problem,
because a 4 x 8 sheet of plastic was really a half-inch (or some small
amount) bigger in both directions.

Anyway, after a couple more years and a few more releases, the program
could handle arbitrary polygons, shapes with various types of curved
edges, arbitrary flaws in the material (mostly for knots in sheets of
plywood), and I'm sure a few more things I don't remember right now.  It
could also beat his "best guy."

Regards,
Dan

-- 
Dan Sommers
<http://www.tombstonezero.net/dan/>