Project Specifications
Specifications for the cutting and packing project
Benchmark files
The Problem
Our problem is a two dimensional nesting problem taken from the fabric industry. We are given an infinite strip of fabric with fixed width on which we need to pack/nest/place polygonal stencils (several stencil types each with its own multiplicity) in a way that minimizes the marker length. The basic problem is packing with nonoverlapping interiors.
Each stencil type is allowed to be rotated only in some angles defined in the input file (see below).
We also wish to solve a more complicated version of the problem where you are given tolerance parameter epsilon, which means that you have to keep an epsilon material zone around each stencil (each stencil should have a "border" with at least epsilon width). If epsilon is zero then we are dealing with the basic instance of the problem.
Input files
The input (as well as the output) files are given in an XML based format. All the numbers in the input (as well as the output) files are given in an exact rational form. This means that each number consists of an unbounded integer "numerator" and an unbounded integer "denominator". The input files consists of two types of files:
 Stencil type database  Contains a list of the stencil types, each with and ID. Each stencil type contains a list of its polygon coordinates. Example for the stencil database file can be found here.
 Problem input  Contains the following parameters:
 The width of the fabric.
 The tolerance value (zero when we are in the basic problem).
 A list of valid rotations. Each rotation has an ID. You can assume that the rotation of zero degrees (sin = 0, cos = 1) is always there.
 A list of stencil types (defined by a name of stencil database and an ID) with quantities. This list of stencils is the list that should be nested on the fabric. Each stencil type is attached with a list of allowable rotation IDs. A stencil type can only be nested in a rotation whose ID is specified in this list. Instead of a list of IDs there could be a value of "ALL" and then the stencil type can be nested in all rotations specified in the problem input file.
 Time limit in seconds for the running time of the algorithm.
 An example problem input file can be found here.
Output File
The output file is also an XML based file and all the numbers are given in an exact rational manner. The output file contains:

The name (and path) of the input file.

A list of the stencils and their placements. Each entry in the list contains the name of the stencil types database, the ID of the stencil type, the ID of the rotation from the input file and the point position of the stencil. Meaning, In case there is no rotation (equivalently, rotation zero) then by "placing a stencil at position (x,y)" we mean translating the stencil by (x,y) from its placement given at the stencils DB, namely a vertex of the stencil whose coordinates are say (x1,y1) is placed at (x1+x, y1+y). When we specify a rotation t, with sine and cosine st and ct respectively, and translation (x,y), this means that we first rotate the stencil as it is given in the DB file counterclockwise by t around the origin, and then apply translation by (x,y) as before. The vertex with original coordinates (x1,y1) will now be placed at (ct*x1  st*y1 + x, st*x1 + ct*y1 + y).

An example of an output file can be found here.
Useful C++ routines using CGAL
There is a header file containing some routines you may find useful. It is written in C++ and it is using CGAL. It can be downloaded from here. The file contains the following routines:
 Given two polyogns, determine if they intersect in their interior.
 Given two linear polygons, determine if their exteriors intersect (pay attention to the fact if polygons that intersect in their interiors then their exteriors also intersect).
 Given two simple linear polygons, calculate the area of their overlap.
 Given two linear simple polygons and a direction, find the minimal vector in that direction that if translating the second polygon by it then the two polygons won't intersect in their interior. If the two polygons don't intersect in their interior then the function returns the vector (0, 0). This function uses the Minkowski sum routine.
 Given two linear simple polygons, find the minimal vector that if translating the second polygon by it then the two polygons won't intersect in their interior.
Minimal requirements from your program
Your program should get an input file and a name (and path) for the output file and write a legal output file with the best yield you can produce.