# 2D lines collision

After seeing in my last post that we could compute the intersection of 2 lines in 3D space but with a big error probability (due to floating point limited precision) today we will compute it for 2 dimensions in C/C++ with virtually no error!

To represent a line we will use the vector equation. $l = p + k \cdot \vec v$

where $l$is the line, $p$a point of the line, $k$an scalar and $\vec v$is the direction vector.

While trying to compute a 2D line intersection there are three possibilities:

1. The lines are parallel
2. They overlap
3. They intersect in one point

What we want is method that tell us whether they intersect in a point or not and (if they do), give us the intersection point:

bool TryGetIntersection(const Line2f& other, Vector2f& intersectionPoint);


We need to equal both lines equations to find the intersection point: $\begin{array}{rcr} l_0 & = & (x_0, y_0)+ k_0 \cdot (a_0, b_0)\\ l_1 & = & (x_1, y_1)+ k_1 \cdot (a_1, b_1) \end{array}$

We equal $l_0$and $l_1$ equations: $\begin{array}{rcl} x_0 + k_0 a_0 & = & x_1 + k_1 a_1 \\ y_0 + k_0 b_0 & = & y_1 + k_1 b_1 \end{array}$

Isolate $k_0$& $k_1$: $k_0 = (x_1 - x_0 + k_1 a_1) / a_0$ $k_1 = (y_0 - y_1 + k_0 b_0) / b_1$

And solve $k_1$: $k_1 = (a_0(y_0 - y_1) + b_0(x_1 - x_0)) / (a_0 b_1 - a_1 b_0)$

Using the parametric equation of the line we can use $k_1$to get the intersection point:

Vector2f Line2f::GetPoint(const float& k)
{
return new Vector2f(this->point.X + k * this->direction.X,
this->point.Y + k * this->direction.Y);
}


But what happens if there is no intersection point? What value will $k_1$ hold?

When the lines overlap the equation system will have infinite solutions so $k_1$will hold a (0/0) division result.
If the lines don’t intersect the equation system won’t have any solution at all, so $k_1$will hold a (x/0) division result; that being said we need to check if any of this happens to know if there is an intersection or not.

If we compute $1 / (a_0 b_1 - a_1 b_0)$and check if its +/- infinity we’ll know when there is no unique intersection point and we can return false. So here is the code:

bool Line2f::TryGetIntersection(const Line2f& other, Vector2f& intersectionPoint)
{
float crossProduct = this->direction.x * other.direction.y
+ other.direction.x * this->direction.y;
float crossInverse = 1 / crossProduct;

float infinity = std::numeric_limits::infinity();
if (-infinity >= crossInverse || crossInverse >= infinity)
{
return false; // overlapping or parallel lines
}

float k1 = (this->direction.x * (this->point.y-other.point.y)
+ this->direction.y * (other.point.x-this->point.x)) / crossProduct;

intersectionPoint = other.GetPoint(k1);
return true;
}


Notice that a value cannot be $\leq -infinity$ or $\geq +infinity$  without being +/- infinity, so checking if the inverse of the cross product (which is the denominator of the $k_1$equation) is infinity is enough to know whether the lines have a unique intersection point or not. This check is based on the b2Valid(float) function of the box2D physics engine, so should be pretty standard and cross platform.

Be aware that this implementation depends fully on the fact that a 1/0 division doesn’t throw any exception. I’ve read somewhere that this depends on the compiler (even that the result is defined in the floating point numbers standard) and can be activated/deactivated on some cases.

I hope you enjoyed this post and happy programming!