Assignment 3: additional information
Submission
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.
Exercise 3.2
General
 Instructions how to build and execute the program, and
 Assumptions and related information made while developing the code, such as whether the code handles degenerate cases.
ex32.py
ex32.cpp
CMakeLists.txt
file, similar to this filecmake
on the provided CMakeLists.txt followed by compilation and linkage should produce an executable called ex32
Input
The program should accept the absolute path (as a string) to an input scene text file,
The structure of the text file (scene.txt) is as in the following example:
200 230 500 0/3 230 700 1/5 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 length of the robot as an integral value.
 The second line represents the start position of the robot reference point as: x, y coordinates and an angle with the xaxis. The x,y coordinates should be integral values, while the angle is represented as a rational number, whose value is between 0 and 2*pi.
 The third line represents the target position of the robot (x,y, and angle).
 The next lines describe the pairwisedisjoint 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 counterclockwise order.
 You can obtain an example of an input file here.
Output
 If you are developing in Python then you should implement the function generate_path(path, length, obstacles, origin, destination) that receives 5 parameters:
 path: a list that should hold the resulting path in the end of the call to generate_path
 length: an integral value representing the length of the robot.
 obstacles: a list of lists of tuples, where the ith list represents the ith obstacle
 origin: a tuple (x, y, angle) of the origin position of the robot's reference point
 destination: a tuple (x, y, angle) of the destination position of the robot's reference point
 This function can be implemented in a separate py file.
 The function should add the configurations along the generated path by appending tuples (of length 4 each) to the list represented by the input parameter path. Each tuple represents a single configuration: its first 3 indices represent the x, y, angle values of the corresponding configuration as rational numbers. The last item in every tuple is either True or False, stating whether the transition from the previous configuration should be in a clockwise manner or not. Note that for the first configuration, representing the robot in its initial position, this value is meaningless. Here is an example of a possible implementation:
def generate_path(path, length, obstacles, origin, destination): path.append((FT(Gmpq(230)), FT(Gmpq(500)), FT(Gmpq("0/3")), True)) path.append((FT(Gmpq(300)), FT(Gmpq(1000)), FT(Gmpq("2/1")), True)) path.append((FT(Gmpq(230)), FT(Gmpq(700)), FT(Gmpq("1/5")), False))
 If you are not developing in Python then your program should generate an output file named "path.txt" containing the configurations along the path, each appearing in a separate line. Each line should contain the x,y (rational) coordinates of the reference point, and the angle with the xaxis (as a rational number), followed by either c or cc, defining whether the transition from the previous configuration along the path is in a clockwise or counterclockwise manner. Below is an example of the content of an output file:
230/1 500/1 0/3 c 300/1 1000/1 2/1 c 230/1 700/1 1/5 cc
 If there's no valid path, generate_path should not populate path with any tuples. Respectively, generated output files should be empty in this case.
Verifier
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 and in the additional information for assignment 2).

Install python 3.7 64 bit.

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

If Microsoft Visual C++ is not installed on your computer download and run vc_redist.x64.exe from here: https://support.microsoft.com/enus/help/2977003/thelatestsupportedvisualcdownloads

Download "Python_code_hw3.zip” from here. Extract the content of the zip file into a new directory. This zip contains a precompiled library containing Python bindings for CGAL as well as additional python files required for this assignment.

Important: The zip contained the compiled bindings in release mode. A compiled version of the bindings in debug mode is available here. The latter displays more informative errors, but is significantly slower than the bindings in release mode.

Run the verifier.py 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 scene0.txt), whose name is specified in the text box above the button
 set destination: set the x y coordinates and angle value specified in the text box above the button as the destination coordinates
 generate path: calls the function generate_path(path, length, obstacles, origin, 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 path1.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.
Collision detector
is_position_valid(x, y, a, l, polygon_list, epsilon)where x,y,a represent the x,y, and angle values of a specific configuration. The value l represents the length of the robot and polygon_list represents a list of the polygonal obstacles as Polygon_2 objects. Finally, the value epsilon specifies if the robot will be checked for collision as is (if epsilon=FT(Gmpq(0))), or whether it will be transformed into a thin rectangle of width epsilon and length l+epsilon that will be checked for collision instead. The latter option is available since the path validity checker uses a thickened robot for verifying whether the returned path is valid. Here is an example demonstrating how to use the collision detector:
poly_list = [Polygon_2([Point_2(0,0), Point_2(1,0), Point_2(1,1)])] x = FT(0) y = FT(1) angle = FT(1) robot_length = FT(1) eps = FT(0) bool_res = is_position_valid(x, y, angle, robot_length , poly_list, eps)
Examples of scene files
How to use the bindings of CGAL kdtree
from arr2_epec_seg_ex import * k = 3 points = [] points.append(Point_3(3,4,0)) points.append(Point_3(3,4,0)) points.append(Point_3(30,40,0)) points.append(Point_3(30,40,0)) points.append(Point_3(1,1,0)) tree = Kd_tree(points) all_points = [] tree.points(all_points) for x in all_points: print(x) query = Point_3(0, 0, 0) eps = FT(Gmpq(0.0)) # 0.0 for exact NN, otherwise approximate NN search_nearest = True #set this value to False in order to search farthest sort_neighbors = False #set this value to True in order to obtain the neighbors sorted by distance search = K_neighbor_search(tree, query, k, eps, search_nearest, \ Euclidean_distance(), sort_neighbors) lst = [] search.k_neighbors(lst) print("Found", len(lst), "neighbors") for pair in lst: print("Neighboring point is: ", pair[0]) print("Distance from query is: ", pair[1])
from arr2_epec_seg_ex import * k = 3 points = [] points.append(Point_3(3,4,0)) points.append(Point_3(3,4,0)) points.append(Point_3(30,40,0)) points.append(Point_3(30,40,0)) points.append(Point_3(1,1,0)) tree = Kd_tree(points) all_points = [] tree.points(all_points) for x in all_points: print(x) query = Point_3(0, 0, 0) #The following function returns the transformed distance between two points # (for Euclidean distance the transformed distance is the squared distance) def transformed_distance(p1, p2): return FT(Gmpq(1)) #replace this with your implementation #The following function returns the transformed distance between the query # point q and the point on the boundary of the rectangle r closest to q. def min_distance_to_rectangle(q, r): return FT(Gmpq(1)) #replace this with your implementation #The following function returns the transformed distance between the query # point q and the point on the boundary of the rectangle r furthest to q. def max_distance_to_rectangle(q, r): return FT(Gmpq(1)) #replace this with your implementation #The following function returns the transformed distance for a value d # Fo example, if d is a value computed using the Euclidean distance, the transformed distance should be d*d def transformed_distance_for_value(d): return FT(Gmpq(1)) #replace this with your implementation #The following function returns the inverse of the transformed distance for a value d # Fo example, if d is a sqaured distance value then its inverse should be sqrt(d) def inverse_of_transformed_distance_for_value (d): return FT(Gmpq(1)) #replace this with your implementation distance = Distance_python(transformed_distance, min_distance_to_rectangle, \ max_distance_to_rectangle, transformed_distance_for_value, \ inverse_of_transformed_distance_for_value) eps = FT(Gmpq(0.0)) # 0.0 for exact NN, otherwise approximate NN search_nearest = True #set this value to False in order to search farthest sort_neighbors = False #set this value to True in order to obtain the neighbors sorted by distance search2 = K_neighbor_search_python(tree, query, k, eps, search_nearest, \ distance, sort_neighbors) lst = [] search2.k_neighbors(lst) print("Found", len(lst), "neighbors") for pair in lst: print("Neighboring point is: ", pair[0]) print("Transformed distance from query is: ", pair[1])