Personal tools
You are here: Home Courses Computational Geometry Spring 2020 Assignments Programming Assignment, Additional Information
« September 2020 »
Log in

Forgot your password?

Programming Assignment, Additional Information


Please provide an archive that contains all source and documentation files in a flat directory structure (that is, place all files in one directory); Use Moodle to submit the file. Do not forget to state your names and IDs. Specify how to run the program in case the instructions deviates from the instructions below.

Your implementation must be robust and accurate; therefore, you should use CGAL. However, you can develop your code in pure C++ or in Python and use Python bindings.

You may send questions about the exercise to Dr. Efi Fogel via email (


If you develop in C++, your solution should consist of at least one source file, CMakeLists.txt (input to cmake), and a pdf file called nesting.pdf that describes the implemented algorithm and discusses the performance. Running cmake on the provided CMakeLists.txt followed by compilation and linkage should produce an executable called nesting.

If you develop in Python, provide a script as well as the nesting.pdf file as described above.

For instructions on how to use the CGAL Python bindings (Windows 10):

1. Download the precompiled bindings for Windows

2. Make sure you work with Python 3.7 64 bit

3. If Microsoft Visual C++ is not installed on your computer download and run vc_redist.x64.exe from here:

4. Put the python bindings file (.pyd) in the directory containing the file (from the zip we supplied)

5. Put the libgmp-10.dll and libmpfr-4.dll in the directory containing the file

You should now be able to import the library and use the provided classes and functions in your code.

Compiling the CGAL Python bindings yourself (Specific for Ubuntu)

  • Install Python >= 3.4, 64 bit.
  • Install boost
    1. Download boost_1_73_0.tar.gz from this link
    2. Extract the tar file using the following command (with the correct path to tar file). It will extract the file to your current directory.
        tar -zxvf <PATH-TO-boost-TAR-FILE>
    3. In the extracted directory you'll find a file named Run the following command:
        ./ --with-python=python3.7 --with-python-version=3.7
    4. Run:
        sudo ./b2 install
      The last step (boost installation) should take a while.
  • Install other CGAL dependencies:
    sudo apt-get install libgmp-dev
    sudo apt-get install libmpfr-dev
    sudo apt-get install cmake
  • Install CGAL
    1. Extract the tar file to a location at your choice.
    2. Set the environment variable CGAL_DIR to temporarily point to the directory where CGAL was extracted. (replace <PATH-TO-EXTRACTED-DIRECTORY> with the correct path)
  • Download the archive file of the CGAL Python bindings sources [link]
  • Uncompress and extract the files.
    tar -zxvf cgal-python-bindings.tar.gz
  • Run cmake in the sources root directory. You can set the following variables depending on your needs:
    plain - Default DCEL
    faceExtended - DCEL extented with face data
    allExtended - DCEL extended with data for faces, halfedges and vertices
    (Other options, although presented in the cmake GUI, are not supported)
    epec [exact predicates exact constructions kernel - uses rational number type]
    epic [exact predicates inexact constructions kernel - faster]
    CGALPY_GEOMETRIC_TRAITS_NAME - determines the curve type of the arrangement:
    The recommended values are marked in bold.
    The following command sets the values in bold (replace <PATH-TO-CGAL-PYTHON_BINDINGS> with the correct path to cgal-python-bindings directory) :
  • Compile the bindings library via the makefile or the solution generated by cmake.
  • Set the environment variable PYTHONPATH to point at the directory where the generated library resides.


The program nesting accepts 2 arguments on the command line:

  1. the name of the file that contains the description of the bounding rectangle R.
  2. the name of the file that contains the description of the simple polygon P.

Both files have the same format: An integral number that specifies the number of vertices followed by the vertices of the polygon in counterclockwise order; each vertex is a pair of rational numbers.

A rational number is given by a numerator and denominator separated by '/' (e.g., 1/3), where the numerator and denominator are both unlimited integers.

You may assume the first vertex of P is located at (0,0), and second vertex lies of the positive side of the X axis. You may assume R is axis aligned, and the first vertex of R is the bottom left vertex of the rectangle, located at (0,0).

m x1 y1 x2 y2 ... xm ym


The program should export a series of quadruples (x,y,c,s)—one quadruple for every congruent copy of P. Each number in a quadruple is a rational number.
  • (x,y) is the location of v1 = (x1,y1).
  • (c,s) is the normalized direction of the vector (v1,v2). (cosine & sine, s^2 + c^2 should sum to exactly 1.)
You may use the function CGAL::rational_rotation_approximation() (also exposed through the CGAL Python bindings) to obtain rational sine and cosine approximations of any desired level of precision for a given direction. See:

Solution verification and visualization

You are provided a python program to verify and visualize your solutions.
The program ( accepts 4 arguments:
  1. the name of the file that contains the description of the bounding rectangle R.
  2. the name of the file that contains the description of the simple polygon P.
  3. the name of the file that contains your solution (as described in the output subsection).
  4. a path to a file that contains some angle (c,s) (as described in the output subsection).
The program verifies that the provided solution is valid and displays the placements of P inside the bounding rectangle on the screen.
Additionally, the program displays the remaining valid placements for the first vertex of P when P is rotated by the angle in the 4th argument (By using Minkowski sums, see
How to run the program:
1. Download the program files: [link]
2. The program requires the installation of PyQt5 (pip install PyQt5).
3. On Linux you may need to install libxcb-xinerama0 (sudo apt-get install libxcb-xinerama0).
4. The program uses the CGAL python bindings (The code can serve as a demonstration of how they may be used). On Windows, make sure that the python bindings file (.pyd), libgmp-10.dll and libmpfr-4.dll are 
in the same directory as, or alternatively make sure libgmp-10.dll and libmpfr-4.dll are reachable from the PATH system variable and the python bindings file from your PYTHONPATH system variable.
5. Run with the four command line arguments as described above (the folder includes example input files).
8.6.20 Update: The solution verification and visualization program has been updated, please download and use the version currently provided in the link above (updated). 
Document Actions