Personal tools
You are here: Home Courses Algorithmic Robotics and Motion Planning Spring 2018 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); send the archive file via email to with the subject "Assignment2". State your name, and IDs.

From this assignment and on, you will have to use CGAL for the programming exercises of the assignment. 

You can develop on any platform, but the code must compile and run using g++ on Linux.

Exercise 2.3


Your solution to exercise 2.3 should consist of all the source file provided, CMakeLists.txt (input to cmake), and a pdf file called 2.3.pdf that describes the implemented algorithm.

Running cmake on the provided CMakeLists.txt followed by compilation and linkage should produce an executable called PathFinder.

The files can be found here. The zip contains one robot and one obstacles test file.

UPDATE 08/04 13:30 Notes by Efi:

In Exercise 2.3 you are also allowed to develop a planner that obtains only (completely) free paths. However, you need to indicate whether your planner obtains free paths or semi-free paths in the documentation.

In the following we assume that you maintain a 2D-arrangement data structure that represents the configuration space.
If you want your planner to obtain semi-free paths, you cannot rely on the operations provided by the 2D Regularized Boolean Operations package. Instead, you need to compute the arrangement directly. Here is one way of doing it:

  1. Extend the DCEL cells (i.e., vertex, halfedge, and face types) of the arrangement with a Boolean that indicates whether the cell is part of the free space or forbidden space.
  2. Insert every obstacle in configuration space into a separate arrangement. Then, for each arrangement traverse its cells and mark each  (as free space or forbidden space). Notice that in the general case the representation of an obstacle in configuration space is a polygon with holes.
  3. Apply the CGAL::overlay(arr_in1, arr_in2, arr_res, overlay_traits) operation on the arrangements computed in the previous stage (as many times as necessary) to obtain the final arrangement. Use the overlay_traits to compute the flag of each cell of the resulting arrangement based on the flags of the corresponding cells of the input arrangements.

UPDATE 05/04 00:11 Notes by Efi:

You can use a 2D Arrangement data structure to represent the configuration space and then use it to obtain a collision-free (or semi free) path from the start configuration to the end configuration. Some details that elaborate on this approach follow.

1. Use the free functions offered by the 2D Minkowski sum package to compute the Minkowski sums of the obstacles and the reflection of the robot about the origin. This results with a collection of polygons.

2. Use the join operation offered by the 2D Regularized Boolean Operation package to compute the union of the Minkowski sums constructed in the previous stage. Notice, that the underlying data structure of the 2D regularized Boolean operations is an arrangement. In particular, use an instance of the General_polygon_set_2 class template (and not the join() free function.) Obtain the underlying arrangement.

3. Finally, use the decompose() free function of the 2D Arrangement package to compute a pseudo trapezoidal decomposition of the free space, and use this decomposition to obtain a collision-free path.

Remark: If you want to extend one or more of the cells of the underlying arrangement, instantiate the General_polygon_set_2 class template with an appropriate DCEL type.

UPDATE 05/04 23:28 Fixed bug in the tester


The program PathFinder accepts 3 arguments on the command line:

  • The filename of the robot file, that contain all the data about the robot.
  • The filename of the obstacles file, that contain all the data about the obstacles. 
  • The filename of the output file.
inputRobot inputObstacles outputFile 


All polygons will be provided clockwise and in the following way:

n x1 y1 x2 y2 ... xn yn

Robot file:

startPoint.x startPoint.y endPoint.x endPoint.y 

The robot point of reference: the first point provided.  

This means that the robot should start it's movement when its first point is located at startPoint, and should end it's course when the first point is located at endPoint. 

Obstacles file:



Output file: 

This is handled by the code in main.cpp. The output consist of 3 lines:

  • The part of the path that was accepted.
  • The part of the path that was interrupted by obstacles.
  • The indexes of the obstacles that touched.
n x1 y1 x2 y2 ... xn yn
n x1 y1 xn yn (either 2 or 0)
n i_1 i_2 ... i_n
To make your life easier we already implemented the output and the classes surrounding verifying the output path!
    Instead, you should only implement the "findPath" function in main.cpp.

    findPath function


    vector<Point_2> findPath(const Point_2 &start, const Point_2 &end, const Polygon_2 &robot, vector<Polygon_2> &obstacles)
    • The start point and end point.
    • The robot polygon.
    • List of disjoint obstacles polygons.


    List of points starting from the start point and ending at the endpoint, that represents a path that doesn't touch any obstacles.

    The robot location on the path is always represented by the robot first point.


    We also added a small python script that enables you to view the results of your program, it can be found along with the files in the archive. It is cross-platform, so you can view it on any device.

    The tool draws the polygons in the file and if provided - also print the result of the PathFinder program.

    USAGE1: inputRobot inputObstacles            (without path)
    USAGE2: inputRobot inputObstacles outputFile (with path)

    Exercise 2.4

      Same as exercise 2.3. You should use the same source files for this task.

        Document Actions