3D Line collision

Not long ago I found myself with the necessity of a Line class where I could compute the relative position of two lines and get the intersection point (if any). I’ve used C# to code this as I was using it at work when I needed this class, but should be easily portable to other languages like Java or C++.

A line can be represented in many different ways, but I chose to represent it with the vector equation:

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

To compute the relative position of two lines (A and B from now on) we could take 2 (or more) different approaches:

1. Compute their relative distance, if its zero (or close to) we can assume they intersect.
2. Determine if their direction vectors are parallel (so the lines are parallel or overlapping) and if they aren’t solve the resulting equation system when you equal their line equations. If there’s a solution that is the intersection point, if there is no solution, they don’t intersect.

The first option can be found here: http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm or here: http://www.vitutor.com/geometry/distance/distance_lines.html

For the second option we will follow this flow chart:

Line-line relative position algorithm (Option 2)

As you can see this algorithm takes two lines (A & B) as input and makes some checks/actions with them so we can know their relative position (don’t worry if you don’t understand that math notation; keep reading).

The first check is where we will know if the lines can be overlapping/parallel or intersecting/skew; this is the point where floating point math error will cause us trouble because every way that I found to check if two vectors are linearly dependent () depends on the equality operator (==) between floating point numbers (something you can’t trust). More info here: http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html

We could use the fact that vectorsandare linearly dependent if and only if their cross product equals the zero vector (0, 0, 0).

Assuming that they are dependent, we need to obtain a pointfrom the line A to check if it’s in line B.

As we are using the vector equation we have a point that it’s in the line, so we need to check if this point is in the other line; problem is that every way that I found to check if a point is contained in a line needs those equality checks (== operator) between floating point numbers.

If vectors are linearly independent we can go for the interesting part, the intersection!

This are the line equations:

To get the intersection point we need to solve the equation system that results from:

We isolateandfrom the x, y coordinates formulas:

I’ll skip all that error-prone & hard to follow math equation solving for you:

Withwe can use the parametric equations of the line to get the intersection point, for that purpose I have this function inside the line class:

/// <summary>
/// Returns a point from this line using the parametric equation.
/// </summary>
/// <param name="k">Parameter used to get the point from this line.</param>
public Vector GetPoint(float k)
{
    return new Vector(this.point.X + this.direction.X * k,
                      this.point.Y + this.direction.Y * k,
                      this.point.Z + this.direction.Z * k);
}

But if you take a look at the latestequation you’ll see that there’s a big chance that we end up dividing by something by zero or even 0 by 0 !!

This happens only when there is no intersection between the lines; in C# (I think that Java works the same way, can’t say for sure) float and double types have -Infinity, +Infinity and NaN values to avoid throwing an exception when that occurs, in other languages we must control this manually and avoid those divisions.

In this case ifends up with a “strange” value we know the lines do not intersect (skew).

Note that if you do not follow the option 2 algorithm strange values incould also mean that the lines overlap.

So this is the intersection method:

/// <summary>
/// Gets the intersection point of this and the given lines (if any).
/// </summary>
/// <returns>Whether this and the given line intersect.</returns>
public bool GetIntersection(Line3 other, ref Point intersectionPoint)
{
    // Don't worry about this, it's the k1 that we calculated before
    float k1 = (this.direction.X * (this.point.Y - other.point.Y)
                + this.direction.Y * (other.point.X - this.point.X))
               / (other.direction.Y * this.direction.X - this.direction.Y * other.direction.X);

    if (float.IsNaN(k1) || float.IsInfinity(k1))
    {
        // strange values indicate that lines are skew or overlapping
        return false;
    }
    else
    {
        intersectionPoint = other.GetPoint(k1);
        return true;
    }
}

While getting the relative position of a pair of lines gets pretty ugly (because of floating point number errors), getting the intersection point between two lines is not that hard; feel free to do whatever you want with it!

Advertisement