Search
Close this search box.

Cutting and Packing Workshop, Spring 2008

Software Workshop (sadna)

0368-3500-19

Lecture: Wednesday 14–16, Schreiber 007

Instructurs: Dan Halperin (TAU) and Eyal Flato (Plataine, Tel-Aviv)

Teaching Assistant: Ophir Setter

The workshop will start in the second week of the semester (due to Memorial Day)

The final project (due to December 5th) can be submitted electronically be e-mailing it to Ophir or by putting it on CGAL mailbox on the second floor (mailbox no.1 near room 210.) The final project should include:

  1. A compiled program.
  2. All code of the project.
  3. A detailed user-manual describing all the programs options and how to enable/disable them.
  4. A very detailed programmers manual containing a comprehensive description of the algorithms and optimizations you used and a detailed description of each class/software component you programmed.

The workshop is about a family of practical geometric optimization problems where we are given a sheet of material (say metal or fabric), and we are also given a set of patterns that one wishes to cut out of the material (say Jeans of size 44). The goal is to place copies of the patterns on the sheet of material such that they do not overlap and so as to use as much of the material as possible. In the workshop we will see real world examples from an Israeli company that develops software tools in this domain. The pictures above sketch two different packing solutions to the same problem.

Requirements and Dates

There are no formal prerequisites, but the workshop is suitable for CS students who have completed two years of study including the courses: software1, software project, data structures, and algorithms.
The deadline for submission of the final project is December 5th, 2008 . There will be several milestones for demonstration of progress, submission of parts of the project and smaller tasks.

By September 1st, each team has to submit (by email to Ophir) a description of its work-plan for the workshop. The description should outline the major milestones that you foresee for your work including algorithmic issues, high-level software design, and a rough scheme for experimentation. (Please also write the names of all the team members and their student id’s in this brief report.)

By November 2nd, 2008, the teams  should be ready to present a prototype of their projects. For a message to the students regarding prototype submission click here.

The final project (due to December 5th) can be submitted electronically be e-mailing it to Ophir or by putting it on CGAL mailbox on the second floor (mailbox no.1 near room 210.) The final project should include:

  1. A compiled program
  2. All code of the project
  3. A detailed user-manual describing all the programs options and how to enable/disable them
  4. A very detailed programmers manual containing a comprehensive description of the algorithms and optimizations you used and a detailed description of each class/software component you programmed

The students can choose to develop the project in their favorite programming language. HOWEVER, we will supply major ready-made components in C++.

An Example—Upholstery

This problem, of cutting and nesting (in this context the jargon word for packing is nesting), arises in various production areas. One of them is the upholstery. We are given, for example, these two couches and we need to cut the upholstery (RIPUD) for them:

(Actually, the cutting and packing problem also arises when cutting the wooden skeleton of couch.)

The material used for cutting the upholstery for this couch is an infinite roll of fabric (well, it is not really infinite, but for the algorithm it is close enough). For example, here are two fabric patterns that can be used to cover your own couch at home!

The cover for the couch is cut in pieces. Our goal in this problem is to save as much material as possible from those rolls of fabric. Two possible nestings of the pieces are shown at the top of the page.

Both of the nests use the same fabric width (height in the picture). The one on the bottom is a bit shorter. The upper nest is a “human-like” nest, while the bottom nest is more likely to have be done by a software. The colors were added for clarity.

Presentations

  1. Minkowski sum movie
  2. C++ Software Tools for Cutting and Packing Workshop presentation, Examples and Optional Exercises (for STL/boost)
  3. Motivation presentation

Reading

  1. Hundreds of papers have been written on cutting and packing. A nice starting point for the variant considered in the workshop is the paper by Ralf Heckmann and Thomas Lengauer, “A Simulated annealing approach to the nesting problem in the textile manufacturing industry“, in Annals of Operations Research 57 (1995) pages 103–133.
  2. Computational Geometry: Algorithms and Applications (CGAA), 2nd or 3rd edition by M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Recommended are chapters 2 and 13.

FAQ

Frequently Asked Questions

Q
 If I know JAVA and C how can I learn C++?
A There is a good free (online & electronic, printed costs money) book calles “Thinking in C++” by Bruce Eckel. Before he wrote this book, he wrote “Thinking in JAVA” so maybe this is an advantage. Also there are a lot of C++ tutorials for “C++ for JAVA programmers” and “C++ for C programmers”. Search in Google. I would go for the “C++ for JAVA programmers”.

Glossary

Definitions of common terms used in this workshop

(borrowed from: Ralf Heckmann and Thomas Lengauer, “A Simulated annealing approach to the nesting problem in the textile manufacturing industry“)

Term Definition
Layout An arrangement of stencils, placement of stencils on the fabric.
Length The maximal x-coordinate of all the placed stencils in a layout.
Marker A layout with no overlaps.
Nesting problem
 The problem where you have a set of irregularly shaped plane stencils that have to be placed on an rectangular surface which has unbounded length.
Position/Placement Defined by the stencil’s location point and its rational angle (orientation, rotation).
Stencil
 An instance of a stencil type. There could be multiple stencils with the same stencil type.
Stencil type
 A “type” of polygon to be placed on the fabric. Each stencil type can have multiple instances in the marker.
Width
 The width of the fabric with unbounded length.
Yield (Sum of area of stencils)/(Width * Length)

Exercises (optional)

To exercise STL, Boost and CGAL

STL & Functors

Taken from http://www.cset.oit.edu/~yangs/CST420/

  1. Write a functor class template SumsTo that generates function objects taking two objects of the same type (x and y) and returning true iff x+y==z, where z is specified at the time the functor object is created. For example, SumsTo<int>(10)(x, y) should return true iff x+y==10. Test your template by using the two-sequence form of transform(): pass it two sequences and have it print out whether corresponding elements in the sequences sum to a user-specified value.
  2. Use accumulate() to calculate the total length of all the strings in a set<string>. Be sure to use the correct return type for string::size().

 

STL & Boost (a little more advanced then the previous)

  1. Palindrome
    1. Use boost::reverse_iterator together with STL’s equal function to check if a given container is a palindrome.  The algorithm can do redundant work, but it should work for any container that has bidirectional iterators and comparable value_type.
    2.  Check your code on both vector<int> and string.
    3. Bonus: make the function a template function receiving an iterator range.
  2. Indirect sort – We wish to sort an array of pointers (iterators) according to the pointees values. This is a very useful thing as the standard sort function copies the elements which can be quite expensive.
    1. Write a predicate (functor returning bool) in the name of indirect_less that, using the regular sort algorithm, can be used to sort a sequence of pointers to integers according the integers’ values. Check your function for some integer array.
    2. Bonus: make the predicate a templated predicate to work for any iterator type. Use boost::counting_iterator together with copy algorithm to get a sequence of iterators to integers from a sequence of integers and use your predicate to sort the sequence. Print the result using boost::indirect_iterator, std::copy algorithm and std::ostream_iterator.
    3. Bonus: change indirect_less to indirect_predicate. The new templated functor will be templated by the iterator type and by a functor that operates on the value_type. The functor returns the value of the given predicate on the pointees.

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 non-overlapping 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:

  1. 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.
  2. Problem input – Contains the following parameters:
    1. The width of the fabric.
    2. The tolerance value (zero when we are in the basic problem).
    3. 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.
    4. 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.
    5. Time limit in seconds for the running time of the algorithm.
    6. 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:

  1. The name (and path) of the input file.
  2. 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).
  3. 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:

  1. Given two polyogns, determine if they intersect in their interior.
  2. 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).
  3. Given two simple linear polygons, calculate the area of their overlap.
  4. 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.
  5. 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.

 

Yair Oz - Webcreator

Contact

Mobile. 052-4703139 | WhatsApp
Email. [email protected]

Skip to content