6.338J/18.337J Project Proposal

Polygon Packing in Parallel

Asanka Herath (asanka AT mit.edu)
Buddhika Kottahachchi (buddhika AT mit.edu)

Problem Statement

Given a set of n polygons (p₁, p₂, ... p_n) such that each polygon is non-self-intersecting and topologically equivalent to disc, compute the dimensions of the rectangle r of minimal area and an arrangement of the polygons, allowing rotations, transpositions and mirroring, such that no two polygons overlap and all polygons are contained within the rectangle r.

Problem Formulation

Each polygon p_i (1 ≤ i ≤ n), will be defined by an ordered sequence of points S_i = { (x₀,y₀), (x₁,y₁), ... (x_m,y_m) } such that each edge of p_i is the line from (x_j,y_j) to (x_k, y_k) such that k ≡ j+1 (mod m) and there are m distinct edges. The points (x,y) in each S_i lie on the Cartesian plane. The position or orientation of each polygon relative to the axes will be irrelevant.

The output of the process, will be the dimensions w and h of the rectangle r as defined in the problem statement, and a set of matrices X_i, such that the position and orientation of each polygon p_i can be obtained by applying the transformation X_i to each point of S_i. Each matrix X_i will be a combination of transposition, rotation and mirroring.

Motivation & Applications

We're both from Sri Lanka where the garment industry is a significant part of the economy. An interesting optimization problem faced by the industry is to maximize the use of fabric during production. Each item of clothing involves assembling polygon fabric components that are cut out of a larger sheet of fabric.

Class Deliverables

Project Presentation

Progress Report