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.

whereis the line,a point of the line,an scalar andis the direction vector.

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

- The lines are parallel
- They overlap
- 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:

We equaland equations:

Isolate&:

And solve:

Using the parametric equation of the line we can useto 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 hold?

When the lines overlap the equation system will have infinite solutions sowill hold a (0/0) division result.

If the lines don’t intersect the equation system won’t have any solution at all, sowill 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 computeand 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 or without being +/- infinity, so checking if the inverse of the cross product (which is the denominator of theequation) 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!