Assignment 4: 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 4.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.
ex42.py
ex42.cpp
CMakeLists.txt
file, similar to this filecmake
on the provided CMakeLists.txt followed by compilation and linkage should produce an executable called ex42
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:
10/1 12/1 13/1 10/1 4 13/1 8/1 14/1 8/1 14/1 9/1 13/1 9/1 4 10/1 11/1 11/1 11/1 11/1 10/1 10/1 10/1 10 8/1 6/1 9/1 6/1 9/1 13/1 31/2 13/1 31/2 7/1 10/1 7/1 10/1 6/1 16/1 6/1 16/1 14/1 8/1 14/1 4 9/2 9/2 5/1 9/2 5/1 17/1 9/2 17/1 4 33/2 9/2 17/1 9/2 17/1 17/1 33/2 17/1 4 5/1 9/2 33/2 9/2 33/2 5/1 5/1 5/1 4 5/1 33/2 33/2 33/2 33/2 17/1 5/1 17/1
 The first line represents the goal position (x,y coordinates) of the center of the first robot. The x,y coordinates should be represented as rational numbers.
 The second line represents the goal position (x,y coordinates) of the center of the second robot. The x,y coordinates should be represented as rational numbers.
 The third and fourth lines represent the first and second robots, respectively, at their start positions. Each line is composed of the following:
 The first integral value indicates that the robot has 4 vertices.
 It is followed by 4 pairs of coordinates (as rational numbers), separated by spaces, representing the vertices of the unitsquare robot in a counterclockwise order, starting with the bottomleft vertex.
 Note that the order of vertices is important here. The position of the center of the robot is not specified explicitly.
 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 (as rational numbers), separated by spaces, representing the vertices of the polygonal obstacle in a counterclockwise order.
 You can obtain an example of an input file here.
 You may assume that the scene is bounded by rectangular obstacles forming a bounding box.
Output
 If you are developing in Python then you should implement the function generate_path(path, robots, obstacles, destination) that receives 4 parameters:
 path: a list that should hold the resulting path in the end of the call to generate_path
 robots: a list of (two) lists of Point_2 objects, where the ith list represents the vertices (as Point_2) of the ith robot
 obstacles: a list of lists of Point_2 objects, where the ith list represents the vertices (as Point_2) of the ith obstacle
 destination: a list of (two) Point_2 objects representing the destination positions of the centers of the two robots
 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 2 each) of Point_2 objects to the list represented by the input parameter path. Each tuple represents a configuration of the two robots: the first Point_2 is the position of the center of the first robot, and the second is the position of the second. Here is an example of a possible implementation:
def generate_path(path, robots, obstacles, destination): path.append([Point_2(1,1), Point_2(2,2)]) path.append([Point_2(3,5), Point_2(5,1)])
 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 (center) of the first robot, followed by the x,y (rational) coordinates of the reference point (center) of the second. Below is an example of the content of an output file:
27/2 17/2 21/2 23/2 1/1 2/1 0/1 5/2 1/1 6/1 4/1 5/2 1/1 6/1 4/1 5/2 2/1 6/1 6/1 4/1 10/1 49/4 13/1 10/1
 Your program should continue running until a valid path is found.
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_hw4.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 polygons_scene.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 destinations: set the x y coordinates of the centers of the two robots specified in the text boxes above the button as the destination coordinates
 generate path: calls the function generate_path(path, robots, 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
 animate movement along path
 Check path validity: display the swept volume of the robots along the path. Prints to the standard output whether the path is valid or not.
Examples of scene files
Useful CGAL binding tips
kdtrees in CGAL for fourdimensional points
from arr2_epec_seg_ex import * #Point_d demonstration p_d = Point_d(4, [FT(1), FT(2), FT(3), FT(4)]) print(p_d.dimension()) print(p_d.cartesian(0)) print(p_d[2]) tree = Kd_tree([p_d]) lst = [] tree.points(lst) for i in range(10): tree.insert(Point_d(4, [FT(i), FT(i), FT(i), FT(i)])) query = Point_d(4, [FT(1), FT(2), FT(3), FT(4)]) k = 5 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)
from arr2_epec_seg_ex import * k = 3 points = [] points.append(Point_d(4, [FT(3), FT(4), FT(0), FT(1)])) points.append(Point_d(4, [FT(3), FT(4), FT(0), FT(1)])) points.append(Point_d(4, [FT(30), FT(40), FT(0), FT(1)])) points.append(Point_d(4, [FT(30), FT(40), FT(0), FT(1)])) points.append(Point_d(4, [FT(1), FT(1), FT(0), FT(1)])) tree = Kd_tree(points) all_points = [] tree.points(all_points) for x in all_points: print(x) query = Point_d(4, [FT(0), FT(0), FT(0), FT(1)]) #The following function returns the transformed distance between two points # (for the squared 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. #(For knearest search you may leave the following implementation) 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 (a number) # 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 (a number) # 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])
Point location
from arr2_epec_seg_ex import * p0 = Point_2(0, 0) p1 = Point_2(100, 100) p2 = Point_2(0, 100) p3 = Point_2(100, 0) s0 = Segment_2(p0, p1) c0 = Curve_2(s0) c1 = Curve_2(Segment_2(p2, p3)) arr = Arrangement_2() insert(arr, c0) insert(arr, c1) #construct a point location data structure naive_pl = Arr_naive_point_location(arr) #Perform some pointlocation queries using the naive strategy. q1 = Point_2(1, 4) res = naive_pl.locate(q1) print (type(res)) # should print arr2_epec_seg_ex.Arr_point_location_result print (res.is_face()) #should print True q2 = Point_2(50, 50) res = naive_pl.locate(q2) print (res.is_face()) #should print False if res.is_vertex(): v = Vertex() res.get_vertex(v) print (v.point()) #construct a different type of point location data structure landmarks_pl = Arr_landmarks_point_location(arr) q1 = Point_2(1, 4) res = landmarks_pl.locate(q1)