tiling

[Roedy Green]

Has anyone out there ever tackled problems like this:

1. cut out pieces of cloth to make a garment in such away you use the
minimum quantity from a bolt of cloth.

2. draw shapes to cut out using a minimum number of sheets of
construction paper.

3. cut pieces of wood/metal knowing an inventory of stock in such a
way you leave the least waste.

4. prepare stain glass patterns given the shapes of the pieces you
need and the shapes of the pieces of glass you have in your inventory.

How do you go about it?

I thought perhaps you could toss the pieces randomly on an infinite
plane then gravitate them closer together till they touch rotating
them till you got to get the best fit. Do this N times and pick the
pattern that gave the best fit.

How it is done?


--
Roedy Green Canadian Mind Products
http://mindprod.com

"America ships tons of sugar cookies to Denmark, and Denmark ships tons of sugar cookies to America. Wouldn’t it be more efficient just to swap recipes?"
~ Michael Pollan

 

[Joshua Cranmer]

Has anyone out there ever tackled problems like this:

1. cut out pieces of cloth to make a garment in such away you use the
minimum quantity from a bolt of cloth.

2. draw shapes to cut out using a minimum number of sheets of
construction paper.

3. cut pieces of wood/metal knowing an inventory of stock in such a
way you leave the least waste.

4. prepare stain glass patterns given the shapes of the pieces you
need and the shapes of the pieces of glass you have in your inventory.

How do you go about it?

This sounds very similar to bin packing:
<http://en.wikipedia.org/wiki/Bin_packing>, although it may need a bit
of transformation. The class of problems in general is known as 'packing
problems,' with the most famous subset being packing hyperspheres
(simple called `sphere packing'). Vanilla bin packing is known to be
NP-hard, so I suspect that the packing problems you care about are also
at least NP-hard.

I thought perhaps you could toss the pieces randomly on an infinite
plane then gravitate them closer together till they touch rotating
them till you got to get the best fit. Do this N times and pick the
pattern that gave the best fit.

How it is done?

This is an irregular packing method; I think Wikipedia calls it "random
close packing." For uniform spheres, a regular lattice will be more
efficient, at least in two and three dimensions; but I'm not sure about
others.

If you have a restriction as to the type of pieces you're trying to pack
together (e.g., they're all rectangles), the problem should be more
tractable.

 

[Larry K. Wollensham]

This is an irregular packing method; I think Wikipedia calls it "random
close packing." For uniform spheres, a regular lattice will be more
efficient, at least in two and three dimensions; but I'm not sure about
others.

Hexagonal in two dimensions; cubic close-packed (also called
face-centered cubic) in three. In higher dimensions, fairly efficient
packings are gotten by using so-called laminated lattices: start with
hexagonal packing, then stack these above each other so spheres in one
layer fit in declivities in the layer below and you get either cubic
close-packed or an equally efficient close relative, hexagonal
close-packed. Repeat in each higher dimension and you get among the most
efficient regular, or lattice, packings, particularly in the dimensions
4, 8, and 24 (where you get something called the Leech Lattice).

However, in most dimensions above 3, except for 24, the most efficient
packings known are irregular ones.

Wikipedia (http://en.wikipedia.org/wiki/Sphere_packing) has more.

 

[Martin Gregorie]

Has anyone out there ever tackled problems like this:

1. cut out pieces of cloth to make a garment in such away you use the
minimum quantity from a bolt of cloth.

2. draw shapes to cut out using a minimum number of sheets of
construction paper.

3. cut pieces of wood/metal knowing an inventory of stock in such a way
you leave the least waste.

4. prepare stain glass patterns given the shapes of the pieces you need
and the shapes of the pieces of glass you have in your inventory.

How do you go about it?

If this is intended to solve a real material cutting problem rather than
a thought process, be aware that its not a good idea to treat glass the
same way as other materials. nAt one time I was working with a colleague
who was writing a program to optimise cutting sheets of glass into panes
and remember him saying crack propagation was the major constraint he had
to work with. The problem was crack propagation from corners, so it was
necessary to continue every cut to the edge of the sheet, i.e. part
placement on the sheet != part placement for best packing.

 

[Larry K. Wollensham]

At one time I was working with a colleague who was writing a program to
optimise cutting sheets of glass into panes and remember him saying
crack propagation was the major constraint he had to work with. The
problem was crack propagation from corners, so it was necessary to
continue every cut to the edge of the sheet, i.e. part placement on the
sheet != part placement for best packing.

Ow.

If I'd been him, I'd have looked into whether doing the task with the
glass heated up to some higher temperature would work; many materials
get less brittle as they warm up. The tricky bit would be finding a
temperature that avoided both crack propagation problems and the glass
becoming too malleable such that it deformed during operation. (Such a
temperature might even turn out not to exist.)

 

[Martin Gregorie]

If I'd been him, I'd have looked into whether doing the task with the
glass heated up to some higher temperature would work; many materials
get less brittle as they warm up.

That wasn't possible. The cutting machines were manually operated and
designed to cut cold glass. The contract was to design a system that
would print out a set of cutting directions for the cutting machine
operator.

This was a long time ago, in the mid 70s, when computer-controlled
machinery was well out of reach of all but the most high-tech industries.

The tricky bit would be finding a
temperature that avoided both crack propagation problems and the glass
becoming too malleable such that it deformed during operation. (Such a
temperature might even turn out not to exist.)

Not to mention that heating it like that would ruin the temper of
toughened glass.

 

[Daniel Pitts]

That wasn't possible. The cutting machines were manually operated and
designed to cut cold glass. The contract was to design a system that
would print out a set of cutting directions for the cutting machine
operator.

This was a long time ago, in the mid 70s, when computer-controlled
machinery was well out of reach of all but the most high-tech industries.


Not to mention that heating it like that would ruin the temper of
toughened glass.

Unless you could do tempering as a post-cut step. I don't know if
that's feasible though

 

[Martin Gregorie]

Unless you could do tempering as a post-cut step. I don't know if
that's feasible though

Gets expensive, though. I don't know how much glass you'd sell if you
were trying to recover costs on the furnace and post-cut processing when
all your competitors were just cutting the stuff.

 

[Larry K. Wollensham]

Gets expensive, though. I don't know how much glass you'd sell if you
were trying to recover costs on the furnace and post-cut processing when
all your competitors were just cutting the stuff.

You'd be buying untempered presumably, while they were buying tempered.
So the cost of tempering would still be in there either way. And you'd
have less material wastage. But you might not get as big an economy of
scale in tempering as they did by getting tempered glass in bulk.

It's hard to say which side would have an edge without knowing a lot
more about the actual costs and economies of scale involved.

 

[Roedy Green]

Since each placement was done to subsequently produce 10000+ shirts or
pants, the cost of manual placement was dwarfed out. What mattered was
that placement resulted in the minimum length of used fabric; that the
placement process could take one or two hour from a skilled employee was
much less an issue.

It is primarily a pair of interesting algorithm problems. The
application I am most interested in seeing materialise is going to a
web store, or small storefront with cloth samples and video terminals,
pick out clothing designs and variations, measure yourself in minute
detail. (I have almost a phobia about buying clothes in a
conventional store, perhaps reliving childhood trauma acquiring
clothes the other kids said came from Jones Tent and Awning. Sweat
pours down my brow.) A computer then sizes the patterns for your
clothes, lays out the pieces efficiently, does the stitching for the
button holes, embroidery etc. then laser cuts the pieces. These are
given to seamstresses who put the garment together and ship it to you.
My partner is partial to the trim custom-tailored looks of the 1940s,
today too expensive. It might be possible to create garments that fit
perfectly at only a small premium.

I would also like some way to design my own clothes, e.g. with
stretchy pieces so my shirt won't pull out when I lift my arms, or
with more spacious crotch. (I have often thought it odd that men wear
pants when it is women who can wear them most comfortably.)

Further into the future, I imagine garments woven/knitted in one
seamless garment. The yarn would be died as it was woven, giving you
the ability to display any pattern of colours, died right into the
yarn. These would need no assembly.

Further in the future we will have LCD yarns, so you can control them
much the way a squid or chameleon does for a dazzling ever-changing
display.
--
Roedy Green Canadian Mind Products
http://mindprod.com

"Nature provides a free lunch, but only if we control our appetites."
~ William Ruckelshaus, America’s first head of the EPA

 

[Lew]

My partner is partial to the trim custom-tailored looks of the 1940s,
today too expensive. It might be possible to create garments that fit
perfectly at only a small premium.

You can save money and get decent custom-tailored clothes by having them made
in Nepal.

Further into the future, I imagine garments woven/knitted in one
seamless garment. The yarn would be died [sic] as it was woven, giving you
the ability to display any pattern of colours, died right into the
yarn. These would need no assembly.

And how would the dye not bleed onto adjacent yarns in the warp and weft?

Further in the future we will have LCD yarns, so you can control them
much the way a squid or chameleon does for a dazzling ever-changing
display.

I truly think you are on to something here.

 

[Roedy Green]

d how would the dye not bleed onto adjacent yarns in the warp and weft?

Perhaps you would have to pre dye the fibres and assemble them into
yarns on the fly. That would not let you get sharp edge changes in
colour though.

Perhaps if you used synthetic fibres they could be extruded on the fly
in the correct colour. They might quickly harden before the dyes had a
chance to mix.

Perhaps the dyes could be sprayed on the fibres/yarns then sealed or
dried before they were allowed to touch other fibres.

I just discovered Levis had a perfect fit scheme a decade ago where
you could get jeans for little more than regular price.

So much clothes buying is impulse, the wait for assembly would
discourage purchase. For it to catch on, it would need automated
assembly while you wait.

I like clothes that last for decades. They become old friends. It
feels disloyal to discard them. I would be happy to spend more for
clothes that would last a long time and fit properly so that I did not
put undue stress on them.
--
Roedy Green Canadian Mind Products
http://mindprod.com

"Nature provides a free lunch, but only if we control our appetites."
~ William Ruckelshaus, America’s first head of the EPA

 

[Martin Gregorie]

Perhaps you would have to pre dye the fibres and assemble them into
yarns on the fly. That would not let you get sharp edge changes in
colour though.

Daedalus (of New Scientist column fame and the chief scientist at
DREADCO) came up with a really neat idea. Make the clothes from
photochromic cloth and simply flash a new pattern onto them when you need
a new look.

That should suit Roedy, since he could keep his clothes forever, just re-
flashing them whenever necessary to complement a new season, house or car.

 

[Philipp]

I thought perhaps you could toss the pieces randomly on an infinite
plane then gravitate them closer together till they touch rotating
them till you got to get the best fit.  Do this N times and pick the
pattern that gave the best fit.

A way to go about is the annealing approach (which comes pretty close
to your idea). See http://en.wikipedia.org/wiki/Simulated_annealing
Define some (eg. gravitational) force between the pieces. This defines
an energy, which can be minimized. A minimized energy would be a
pretty good start for the placement of the pieces.

After random placement of the piece on the available space, let the
system evolve using the forces until they stop moving because each one
is stuck in a position where, if moved, it will overlap another piece
(or the border). The position you just found is a local energy minimum
in the piece-position space, you can record the position and its
corresponding energy. (probably you are more interested in some sort
of bounding box as a metric, than in an energy, but you get the point)

Now you can perturbate the sytem, to try to make it fall into a deeper
energy well. Perturbation can be done by simulating thermic activity,
or simply by adding a random move to some or each piece. After
perturbation, let the system evolve again to a local minimum. In this
way, some pieces may find a better, more compact placing.

This works very well with a high number of small pieces. As in your
case, you have a rather small set of large pieces, the initial
positions are strongly correlated to the end result, thus you will
need to restart the simulation several times (for example, when a
given number of perturbation did not yield a better solution), varying
the intial placement of the pieces.

Note that you can add some heuristics from other algorithms eg. place
largest pieces first, let them evolve to a minimum, then only place
the smaller ones, if possible inthe free space between the larger
pieces
Note also, that you might meet more constraints, for example that the
fabric must be in a given direction with respect to the cut out-pieces
(so that those lines are actually horizontal on the t-shirt)

HTH Phil