The objective of the project is to obtain a two-dimensional mapping of the room represented by points in space, to efficiently fit parabolas to the walls of the room, and ultimately to find the exit from it.
- Load data from the file (xyz file in our case) into a two-dimensional array of two-dimensional points according to ( x, y ). Disregard points that are very high or very low to ignore noise from the ceiling and floor.
- Convert all points from Cartesian representation to polar representation and then sort all points by the angle theta.
- Use the Corsets algorithm to reduce the points to a significantly smaller set of points, where the result of the algorithm on them will be similar up to an epsilon (in our case, we defined epsilon to be 0.01). For example, on the lab mapping we received containing around 32,000 points, after running the Corsets algorithm on them, we were left with about 660 points. This reduction in the number of points significantly improved the runtime from around 8 hours to half a minute for the same input.
- Create a neighborhood matrix describing a directed acyclic graph (in this case, also a clique). The cost of each edge in the matrix is represented by the sum of distances of the points from the most suitable parabola according to linear regression (Polyfit).
- Use an algorithm to find the shortest path in the directed acyclic graph without cycles with a time complexity of ( O(V + E) ). This is done by performing topological sorting on the input and then running Dijkstra's algorithm. The output at this stage is the indices of points in the sorted polar room. These are the points dividing the room into k segments.
- Iterate over each of the k segments and search for the segment with the smallest point density. This is done by calculating: Density = (amount of points in segment)/(theta of the last point in the segment - theta of the first point in the segment). The chosen segment is the lightest segment and represents the "suspected exit area."
- Repeat step 6 on the lightest segment found, searching for the least dense sub-segment, which will be the exit from the room represented by 2 points representing the beginning and end of the exit segment. Finally, return the average of these 2 points, which is the point to which the drone will be directed.
Input- "perfect" square room with an exit:
Input- Full mapping of the laboratory space (after using Corsets algorithm):
