Geometry in Action

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.

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.