Line collision detection

So, the first thing we need to do is talk about the difference between a line and a line segment. We define a line using two points. That line continues after the points to infinity. A line segment terminates at the two points and does not continue indefinitely. Two lines that are not parallel will always intersect somewhere. Two non-parallel line segments may or may not intersect.

For the most part, in games, we are interested in knowing whether two line segments intersect:

It is relatively easy to determine whether a line intersects with a line segment. All you have to do is see whether the two points of the line segments are on opposite sides of your line. Since a line is infinite, that means your line segment has to intersect with your line somewhere. If you want to find out whether two line segments intersect, you can do it in two stages. First, find out whether line segment A intersects with an infinite line B. If they do intersect, then find out whether line segment B intersects with the infinite line A. If this is true in both cases, the line segments intersect.

So, the next question is, how do we know mathematically whether two points are on the opposite sides of a line? To do that, we are going to use the previously discussed dot product and something called a vector normal. A vector normal is just a 90-degree rotated version of your vector. See the following diagram:

We also need the vector that has an origin at the same point but has a direction aiming at point 1 of our line segment. If the dot product of those two vectors is a positive value, that means the point is on the same side of the line as the normalized vector. If the dot product is a negative value, that means the point is on the opposite side of the line to our normal vector. If the line segment intersects, that means one point has a positive dot product and the other side has a negative dot product. Since multiplying two negative numbers and two positive numbers both give you a positive result and multiplying a negative and a positive number gives you a negative result, multiply the two dot products together and see whether the resulting value is negative. If it is, the line segment intersects with the line: