Textile Layout
The problem here is, given a pattern in the form of a collection of
shapes (polygons), to arrange the shapes so they can be cut from a piece
of fabric with as little wasted fabric as possible. Essentially this is
a two-dimensional bin-packing problem with various complications: the
width of the fabric is fixed and one intends to minimize length; the
shapes can sometimes be placed only in a small number of possible
orientations so that the fabric pattern lines up correctly; the shapes
can be quite far from convex; and (for leather) the hides out of which
the shapes must be cut can be quite variable in shape and quality.
This area is also related to more tractible geometric problems
such as testing whether one polygon can be translated to fit inside
another. Textile layout has some visibility in the geometry community
largely due to the efforts of
Victor Milenkovic,
now at the University of Miami.
- Algorithms for Minimizing Overlap of Translating Polygons,
Victor Milenkovic, 5th MSI Worksh. Comp. Geom.
- Cutting
fabric for sails, Eugene Popov.
- Part Layout and Optimization of Part Shape,
L. Shanley, L. Anderson, and V. Milenkovic, research brief from the
National Textile Center.
- The Restrict/Evaluate/Subdivide Paradigm for Translational
Containment,
Karen Daniels, 5th MSI Worksh. Comp. Geom.
- Two dimensional cutting and packing problems in the textile and leather
manufacturing industry, T. Lengauer, Inst. for Algorithms and
Scientific Computing, German Natl. Research Ctr. for Information
Technology.
- US
Patents
5506784,
5510994,
and
5541847
use medial axes to generate embroidery patterns.
- Yahoo directory of textile software vendors
Part of
Geometry in Action,
a collection of applications of computational geometry.
David Eppstein,
Theory Group,
ICS,
UC Irvine.
Semi-automatically
filtered
from a common source file.
