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

You may develop in Python or C++

Provide either a plain text fie called ex42.txt or a file in pdf format called ex42.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.

Python

Use a single source file called ex42.py

Use Python 3, but do not use 3.8.

implement your code as described in the instructions below

C++

Use a single source file called ex42.cpp

Provide a CMakeLists.txt file, similar to this file

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

Make sure your program compiles and runs using a standard version of gcc on Linux

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 unit-square robot in a counter-clockwise order, starting with the bottom-left 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 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 (as rational numbers), separated by spaces, representing the vertices of the polygonal obstacle in a counter-clockwise 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 i-th list represents the vertices (as Point_2) of the i-th robot
  • obstacles: a list of lists of Point_2 objects, where the i-th list represents the vertices (as Point_2) of  the i-th 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).

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: https://support.microsoft.com/en-us/help/2977003/the-latest-supported-visual-c-downloads
4. 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.
5. 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.
6. Run the polygons_scene.py script from this directory.

For Linux users: a tar file containing the bindings code is available here. Note that it should be compiled, as in the instructions given in the additional information for Assignment 2.

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

You may assume that all workspaces are bounded by a rectangle. This bounding box is part of the obstacles in every scene. You do not need to sample outside of this bounding box.

• scene0
• scene1
• scene2
• scene3
• scene4
• scene5
• scene6 (more difficult)

Useful CGAL binding tips

kd-trees in CGAL for four-dimensional points

In your implementation you may use CGAL kd-trees for 4D points to answer k-nearest queries.

In order to represent a four-dimensional point we will use CGAL Point_d. Note that due to compilation considerations the kd-trees assume that the dimension of the point set is 4 (this is fixed).

The following example demonstrates how to build a kd-tree for 4D points and use it for answering k-nearest queries in CGAL using the python bindings. The distance metric is the Euclidean distance.

The parameter eps is used for approximate NN queries (if eps > 0). Otherwise, if eps=0, then exact NN queries are performed.

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)

A user-defined distance metric can be used, rather than the Euclidean distance. The following example demonstrates how to specify a user defined distance metric for the k-nearest search.

As a reference, you may use this example from the CGAL manual.

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 k-nearest 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

You may process a 2D arrangement for point location queries, that is, construct a data structure to efficiently answer queries of the following form: given a point locate the arrangement component (face, halfedge, or vertex) containing it.

Several point location algorithm are supported. The following code demonstrates how to use two of them.

Note: If working with versions of the bindings downloaded from this page prior to 8.1.20, you need to keep a reference to the arrangement as long as you need to perform point location queries on it.

If working with the versions currently available for download on this page, this is no longer the case.

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 point-location 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)

Hash for immutable kernel objects

The python bindings now support hashing for immutable kernel objects