Perhaps the most difficult part of the assignment is the collision detection; deciding
whether or not a line segment (representing the robot's path) intersects a rectangle
(representing an obstacle). This is complicated by the fact that it is allowed to be
(in fact, must be) on a vertex of an obstacle for the source and destination of the
segment.
There are a number of ways to do this detection, and there's no one way I'm looking
for; whatever technique you use is fine (if it results in a correct answer, that is).
I will briefly outline the methods I used here.
The first thing you need is the ability to detect the point of intersection of 2 line
segments. To get this, you'll need to look at their 2 equations for the lines in
question, find their intersection point (if any; they may be parallel), and check to
see if that point is within the bounds of the line segments. While I used the
standard formula y=ax+b for my lines, it gets very messy because you need to check for
weird cases such as when the slope is infinite, and handle those separately. You may
consider using parametric equations for this reason; it's up to you.
A quick review for those of you a bit rusty on your geometry:
If you do decide to use y=ax+b (y=slope*x+ l2-intercept) as your linear equation, you
can find the point of intersection by setting 2 such equations equal to each other and
solving for x, then calculating y from it:
given y=ax+b and y=cx+d
set ax+b=cx+d
then x=(d-b)/(a-c).
Now calculate y using this value. This point (x,y) is the intersection of the 2
lines, but may not be on the line segments themselves; you need to check the bounds
of the segments to make sure.
Once you have in place a method that takes a line segment and a rectangle as input,
and returns their various intersections, you need to consider what these intersections
mean. The robot is allowed to travel from one vertex of a rectangle to an adjacent
vertex of the same rectangle, despite the fact that the robot's path intersects the
entire side. You need to consider that the robot's path is guaranteed to technically
intersect several line segments; the line segments that the start and end vertices make-up.
You need to consider that while it is ok for the robot to move to an adjacent vertex on
the same rectangle, it is not ok to move to the opposite vertex.
Another note: I will test these on data sets other than the ones given, so I recommend that
you do too. Try it out on cases for which you know the answer, so you can check that your
algorithm is actually correct.
If you have any questions on any of this, or any other questions regarding the assignment,
let me know.
