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

wherelis the line,pa point of the line,kan scalar and\vec vis 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 equall_0andl_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}

Isolatek_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 solvek_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 usek_1to 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 willk_1 hold?

When the lines overlap the equation system will have infinite solutions sok_1will hold a (0/0) division result.
If the lines don’t intersect the equation system won’t have any solution at all, sok_1will 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 compute1 / (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 thek_1equation) 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!

Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s