COMP2401 - Consider A Robotic Environment Where Obstacles Are Represented As A Set Of Rectangles - IT/Computer/Science Assignment Help

Assignment Task

In this assignment you will gain additional practice in using pointers to structs as well as allocating  dynamic memory and creating linked lists. 
Consider a robotic environment where obstacles are represented as a set of rectangles as shown  below. The robot would like to travel through the environment as efficiently as possible (i.e., shortest  route) without hitting any obstacles.  

To find a good route through the environment, we will assume that the robot is a single point in size  (This can be easily adjusted later by “growing” the obstacles according to the robot’s shape so that  the robot does not bump into the obstacles when it gets close… although we will ignore this “growing”  concept for this assignment). One algorithm to find the best route through the obstacles is based on  computing the shortest path in a graph of edges that connects the obstacle corners.  
On the next page, you will see screen snapshots showing is what is known as a “complete graph” of  the vertices (i.e., corners) of the obstacles. It is essentially a graph in which each vertex is connected  to all other vertices. If there are N rectangular obstacles, then there are exactly 4N*4N=16N2 edges  of this complete graph. That can be a lot of edges. Finding the shortest path in this graph can be  done. But it is better to reduce the graph size beforehand. As you can see, there are many edges  of the graph that cross through the obstacles. Obviously, these are not edges that can be travelled  on by the robot, as it will intersect/hit the obstacles.  
Instead, we want to remove all edges of this graph that intersect with an obstacle. That will  significantly reduce the number of edges in the graph, making it faster to find the shortest path.

How do we determine if a line segment intersects a rectangle ? We can just check to see if that edge  intersects/crosses any of the obstacle edges. The easiest way to do this is to determine the cro 
Consider the two line segments shown on the right. We can  
compute ua and ub below: 
Then, the line segments intersect if 0 < ua < 1 and 0 < ub < 1. This does not include the case where  the line segments intersect at a vertex. 
We can use this simple intersection test to determine if an edge of the graph intersects a rectangle by  checking all 4 sides of the rectangle. You will have to check for the special case of a edge that  connects diagonal vertices of the same obstacle … as this is not a valid edge either. 
Once we eliminate all edges that are invalid, we should have a graph that looks like this: 

This reduced graph has 168 edges (instead of the complete one which had 756 edges). Each edge  shown above is actually two edges in the graph… representing travel in both directions (i.e., one  edge from vertex v1 to vertex v2 and another from vertex v2 to vertex v1). In addition, there are  edges in both directions along the obstacle borders. 
The shortest path from one vertex to another vertex within this graph is guaranteed to be a sequence  of consecutive edges along this reduced graph. We will not be computing the shortest path in this  assignment. Instead, we are just interested in computing this reduced graph, which is called a  visibility graph. 
 

This COMP2401 - IT/Computer/Science Assignment has been solved by our IT/Computer/Science Experts at My Uni Paper. Our Assignment Writing Experts are efficient to provide a fresh solution to this question. We are serving more than 10000+ Students in Australia, UK & US by helping them to score HD in their academics. Our Experts are well trained to follow all marking rubrics & referencing style.

Be it a used or new solution, the quality of the work submitted by our assignment experts remains unhampered. You may continue to expect the same or even better quality with the used and new assignment solution files respectively. There’s one thing to be noticed that you could choose one between the two and acquire an HD either way. You could choose a new assignment solution file to get yourself an exclusive, plagiarism (with free Turnitin file), expert quality assignment or order an old solution file that was considered worthy of the highest distinction.