Personal tools
You are here: Home Courses Algorithmic Robotics and Motion Planning Fall 2019/2020 Assignments Assignment 2
« September 2020 »
Log in

Forgot your password?

Assignment 2


Please submit an archive that contains all source and documentation files in a flat directory structure for each exercise (that is, place all files of a given exercise in one directory); Upload the archive to moodle, in the relevant submission box. Make sure to include in the archive a file where you state your names, IDs and explain in detail how to run the program.

You are free to use any programming language for this exercise.

Exercise 2.3


You may develop in Python or C++
Provide either a plain text fie called ex23.txt or a file in pdf format called ex23.pdf that contains the following:
  1. Instructions how to build and execute the program, and
  2. Assumptions and related information made while developing the code, such as whether the code handles degenerate cases.

Use a single source file called
Use Python 3, but do not use 3.8.
implement your code as described in the instructions below

Use a single source file called ex23.cpp
Provide a CMakeLists.txt file, such as this file
Running cmake on the provided  CMakeLists.txt followed by compilation and linkage should produce an executable called ex23
Make sure your program compiles and runs using a standard version of gcc on Linux


The program should accept the absolute path (as a string) to an input scene text file,

The structure of the text file (polygon_scene.txt) is as in the following example:

700 1000
3 300 400 250 250 450 100
4 600 700 550 550 550 400 750 400
3 200 700 150 400 200 400
  • The first line represents the target position of the robot reference point as x and y coordinates. These should be integral values.
  • The second line describes the robot in its start position: 
    • The first integral value represents the number m of vertices. 
    • It is followed by m pairs of coordinates, separated by spaces, representing the vertices of the polygonal robot in a counter-clockwise order. 
    • The first vertex is the reference point of the robot.
    • For instance, in the example above, the robot has 3 vertices
  • The next lines describe the pairwise-disjoint polygonal obstacles, each obstacle is defined in a separate line as follows:
    • The first integral value represents the number n of vertices of the specific obstacle. 
    • It is followed by n pairs of coordinates, separated by spaces, representing the vertices of the polygonal obstacle in a counter-clockwise order.
    • In the example above we have 2 obstacles. The first has 4 vertices and the second has 3 vertices
  • You can obtain an example of an input file here


  • If you are developing in Python then you should implement the function generate_path(path, robot, obstacles, destination) that receives 4 parameters:
    • path: a list that should hold the resulting path in the end of the call to generate_path
    • robot: a list of (x,y) tuples representing the robot in its start position
    • obstacles: a list of lists of tuples, where the i-th list represents the i-th obstacle
    • destination: a tuple (x,y) of the destination position of the robot's reference point
  • This function can be implemented in a separate file. In our example it is implemented in a file named
  • The function should add the vertices along the generated path by appending objects of type Point_2 to the list represented by the input parameter path. Note that: there cannot be two consecutive points along the returned path with the same coordinates. Here is an example of a possible implementation:
def generate_path(path, robot, obstacles, destination):
  path.append(Point_2(300, 400))
  path.append(Point_2(300, 1000))
  path.append(Point_2(700, 1000))
    • If you are not developing in Python then your program should generate an output file named "path.txt" containing the coordinates of the path. Since the path is a poly-line it can be defined by the vertices along it. Each vertex will appear in the output file in a separate line. The x,y coordinates of the vertex will appear as rational numbers separated by space. Below is an example of the content of an output file:
    300/1 400/1
    300/1 1000/1
    700/1 1000/1

      In this example the resulting path contains 3 segments.

      • If there's no valid path, generate_path should not populate path with any points. Respectively, generated output files should be empty in this case.


      We provide Python code for viewing the scenes and for validating your solutions. This code contains python bindings to various structures and functionalities in CGAL.

      Here are the installation instructions for Windows 10. In case you are working in a separate environment you'll have to compile the bindings on your own (Instructions can be found below).

      1. Install python 3.7 64 bit.

      2. Install PyQt5 via the following command in the command line - “pip install PyQt5”.

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

      4. Download "PyCode_updated.zipfrom here. Extract the content of the zip file into a new directory. This zip contains a precompiled library containing Python bindings for CGAL. 

      5. Run the script from this directory.

      Running the script opens a UI window with the following options:

      • load scene: loads a scene from a scene txt file (as in polygon_scene.txt), whose name is specified in the text box above the button
      • save scene: saves a scene to a txt file, whose name is specified in the text box above the button
      • set destination: set the x y coordinates specified in the text box above the button as the destination coordinates
      • generate path: calls the function generate_path(path, robot, obstacles, destination), which is implemented in a py file whose name is specified in the text box above the button (relevant to Python implementations only)
      • load path: loads a path from a text file in the format of path0.txt , whose name is specified in the text box above the button
      • save path: saves a path to a text file, whose name is specified in the text box above the button
      • animate movement along path
      • check_path_validity: display the swept volume of the robot along the path. Prints to the standard output whether the path is valid or not.

      Examples of scene files 

      Useful information about the CGAL Python bindings

      The Python bindings currently include:
      • CGAL Arrangements: All objects and methods that are part of the following categories: Arrangement_2, Point Location, Free Functions. The following geometric traits are fully supported (but require a separate compilation for each traits option): segment_traits, linear_traits, circle_segment_traits, algebraic_segment_traits.
      • Kernel: All Kernel classes and global kernel functions, which are not related to objects in 3D space, are supported.
      • Minkowski sums: Everything other than approximated_inset_2, inset_polygon_2, offset_polygon_2 
      • 2D Regularized Boolean Set-Operations: Everything other than the arrangement() method of Polygon_set_2
      • Triangulations: Partial support: includes most of the basic methods for Triangulation_2  and for Delaunay_triangulation_2
      The bindings are currently compiled with segment_traits and extended DCEL.
      Iterators and circulators in CGAL are implemented as iterators in the Python bindings.
      For example, given an arrangement arr one can iterate over its vertices using a for loop. In C++ one should iterate from the begin-iterator arr.vertices_begin() until reaching the past-the-end iterator arr.vertices_end(). In Python the following code should be used instead:
      for v in arr.vertices(): 
      #v is of type Vertex
      Instead of circulators we use iterators. In the following example we demonstrate how to iterate over the halfedges around a vertex s :
      #s is of type Vertex
      for e in s.incident_halfedges(): 
      #e is of type Halfedge
      A code demonstrating vertical decomposition of an arrangement arr:
      d= []
      decompose(arr, d)
      for pair in d:
         #pair is a tuple 
         #pair[0] is an arrangement vertex 
         #pair[1] is a pair holding the objects (vertex, halfedge, or face) above and below the vertex, that is, the objects hit by the vertical walls emanating from the vertex
         v0 = pair[0]
         for obj in pair[1]:
            if obj.is_vertex():
               v1 = Vertex()
            elif obj.is_halfedge():
               he = Halfedge()
            elif obj.is_face():
               f = Face()
       Note that obj in the above example may also be empty (in which case obj.empty() would return True). See the official documentation for more information.
      A code demonstrating the computation of the overlay of two arrangements arr1, arr2:
      Note that in this example we use the extended DCEL, which extends every face, halfedge, and vertex with data. The function overlay requires an object of type overlay traits that specifies how to handle the data of each type in the resulting arrangement given the data of the two input objects.
      When constructing an Arr_overlay_traits object one has to provide 10 functions: 6 vertex creation functions, 4 edge creation functions, and 1 face creation function. The order of these function is according to the order here .
      In the example below, we specify a function for the face creation, when a face is created as an overlap between two faces f1,f2. The function that was passed here will assign the new face with the data of f1.
      def first(x, y):
        return x
      def empty(x, y):
        return None
      traits = Arr_overlay_traits(empty, empty, empty, empty, empty, empty, empty, empty, empty, first)
      res = Arrangement_2()
      overlay(arr1, arr2, res, traits)
      A code demonstrating the computation of the Minkowski sum of two polygons pgn1, pgn2 (objects of type Polygon_2). The vertices of the polygons are given in a counter-clockwise order
      ms = minkowski_sum_2(pgn1, pgn2)
      assert(isinstance(ms, Polygon_with_holes_2))
      # ms.outer_boundary()  is of type Polygon_2
      # ms.holes() returns an iterator of the holes in ms

      Compiling the CGAL Python bindings yourself (Specific for Ubuntu)

      • Install Python >= 3.4, 64 bit.
      • Install boost
        1. Download boost_1_71_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
        4. Run:
            ./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. Download CGAL-4.14.2.tar.xz from
        2. Extract the tar file to a location at your choice.
        3. 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 [cgal-python-bindings.tar.gz].
      • 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 verifier assumes you used the values 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.
      Document Actions