Find the Intersection Point of Two Line Segments

• Download source - 1.7 KB

Introduction

The following is an implementation of a Line Segment Intersection Algorithm that will test whether two line segments intersect. If so, it will calculate the actual intersection point. Gareth Rees describes the algorithm in a StackOverflow article on the subject.

See: http://stackoverflow.com/a/565282/292237.

Using the Code

The attached zip-file contains a single C# source file. Apart from the algorithm code itself, it contains a small test class using Visual Studio 2013's test framework.

My Motivation

While fooling around with some graphics code, I ran into the problem of clipping line segments using a bounding box. My approach was to test whether my line segment intersected one of the four sides of the bounding rectangle. I searched around for an implementation but was not immediately able to find something that I could copy/paste into my C# project. Therefore, I decided to do the implementation myself. I chose a very explicitly described algorithm, so that I was sure that I understood what was going on - my geometry lessons from school were buried deep within my brain, so I basically had to re-learn it all.

Background

Testing for intersection between segments is a bit more tricky than finding intersections between infinite lines on the form y = ax + b, as they are a bit easier to solve symbolically.

When testing for intersection between two line segments, there are five cases to consider. The code will go through these cases one by one.

1. The line segments are collinear and overlapping, meaning that they share more than one point.
2. The line segments are collinear but not overlapping, sort of "chunks" of the same line.
3. The line segments are parallel and non-intersecting.
4. The line segments have a single point of intersection.
5. The line segments do not intersect.

Implementing the Algorithm

This algorithm uses basic vector math including calculation of the so-called dot product and cross product. I will start by implementing a 2D vector class containing the basic arithmetic functions. This makes the algorithm code far more readable and similar to the symbolic description in Gareth's article.

A Simple 2D Vector Class

This class implements vector arithmetic such as addition, subtraction and scaling (multiplying with a constant). The '*' (asterisk sign) used between two vectors will return the dot product. Finally, the Cross() function returns the cross product between the vector and another vector. I will use two vectors to describe the start and end points of a line segment.

public class Vector
{
    public double X;
    public double Y;

    // Constructors.
    public Vector(double x, double y) { X = x; Y = y; }
    public Vector() : this(double.NaN, double.NaN) {}

    public static Vector operator -(Vector v, Vector w)
    {
        return new Vector(v.X - w.X, v.Y - w.Y);
    }

    public static Vector operator +(Vector v, Vector w)
    {
        return new Vector(v.X + w.X, v.Y + w.Y);
    }

    public static double operator *(Vector v, Vector w)
    {
        return v.X * w.X + v.Y * w.Y;
    }

    public static Vector operator *(Vector v, double mult)
    {
        return new Vector(v.X * mult, v.Y * mult);
    }

    public static Vector operator *(double mult, Vector v)
    {
        return new Vector(v.X * mult, v.Y * mult);
    }

    public double Cross(Vector v)
    {
        return X * v.Y - Y * v.X;
    }

    public override bool Equals(object obj)
    {
        var v = (Vector)obj;
        return (X - v.X).IsZero() && (Y - v.Y).IsZero();
    }
}

A Small Helper Class

When working with floating point numbers in computers, there is bound to be some rounding errors, which makes it difficult when you, for example, want to test if a number is equal to zero. Therefore, we choose a very small constant to test against, and if our number is lower than this constant, we consider it zero. Here, I have made a little extension method to help us. I use an extension method, merely because I find it visually pleasing.

public static class Extensions
{
    private const double Epsilon = 1e-10;

    public static bool IsZero(this double d)
    {
        return Math.Abs(d) < Epsilon;
    }
}

The Algorithm

At this point, I would suggest that you open Gareth's original article and follow along in his description. He gives a very good explanation and has some meaningful images to go along. Also I have chosen to stick very close to the naming used in his article.

The LineSegementsIntersect function takes the start and end points of the two line segments and an out parameter for the intersection point.

For the purpose of my own code, I have added a Boolean parameter to decide whether we should consider overlapping lines as "intersecting". If we do, the function will return true in these cases, but the intersection point will have no meaning and will have the value NaN (not a number) for both x and y.

/// <summary>
/// Test whether two line segments intersect. If so, calculate the intersection point.
/// <see cref="http://stackoverflow.com/a/14143738/292237"/>
/// </summary>
/// <param name="p">Vector to the start point of p.</param>
/// <param name="p2">Vector to the end point of p.</param>
/// <param name="q">Vector to the start point of q.</param>
/// <param name="q2">Vector to the end point of q.</param>
/// <param name="intersection">The point of intersection, if any.</param>
/// <param name="considerOverlapAsIntersect">Do we consider overlapping lines as intersecting?
/// </param>
/// <returns>True if an intersection point was found.</returns>
public static bool LineSegementsIntersect(Vector p, Vector p2, Vector q, Vector q2, 
    out Vector intersection, bool considerCollinearOverlapAsIntersect = false)
{
    intersection = new Vector();

    var r = p2 - p;
    var s = q2 - q;
    var rxs = r.Cross(s);
    var qpxr = (q - p).Cross(r);

    // If r x s = 0 and (q - p) x r = 0, then the two lines are collinear.
    if (rxs.IsZero() && qpxr.IsZero())
    {
        // 1. If either  0 <= (q - p) * r <= r * r or 0 <= (p - q) * s <= * s
        // then the two lines are overlapping,
        if (considerCollinearOverlapAsIntersect)
            if ((0 <= (q - p)*r && (q - p)*r <= r*r) || (0 <= (p - q)*s && (p - q)*s <= s*s))
                return true;

        // 2. If neither 0 <= (q - p) * r = r * r nor 0 <= (p - q) * s <= s * s
        // then the two lines are collinear but disjoint.
        // No need to implement this expression, as it follows from the expression above.
        return false;
    }

    // 3. If r x s = 0 and (q - p) x r != 0, then the two lines are parallel and non-intersecting.
    if (rxs.IsZero() && !qpxr.IsZero())
        return false;

    // t = (q - p) x s / (r x s)
    var t = (q - p).Cross(s)/rxs;

    // u = (q - p) x r / (r x s)

    var u = (q - p).Cross(r)/rxs;

    // 4. If r x s != 0 and 0 <= t <= 1 and 0 <= u <= 1
    // the two line segments meet at the point p + t r = q + u s.
    if (!rxs.IsZero() && (0 <= t && t <= 1) && (0 <= u && u <= 1))
    {
        // We can calculate the intersection point using either t or u.
        intersection = p + t*r;

        // An intersection was found.
        return true;
    }

    // 5. Otherwise, the two line segments are not parallel but do not intersect.
    return false;
}

Testing the Code

A few simple unit tests could look like the ones below. I am using Visual Studio 2013's test framework.

[TestMethod]
public void LineSegmentsIntersect()
{
    Vector intersection;
    var actual = LineSegementsIntersect(
        new Vector(0, 0),
        new Vector(5, 5),
        new Vector(0, 5),
        new Vector(5, 0),
        out intersection);

    Assert.IsTrue(actual);
    Assert.AreEqual(new Vector(2.5, 2.5), intersection);
}

[TestMethod]
public void LineSegmentsDoNotIntersect()
{
    Vector intersection;
    var actual = LineSegementsIntersect(
        new Vector(3, 0),
        new Vector(3, 4),
        new Vector(0, 5),
        new Vector(5, 5),
        out intersection);

    Assert.IsFalse(actual);
}

[TestMethod]
public void LineSegmentsAreCollinearAndOverlapping()
{
    Vector intersection;
    var actual = LineSegementsIntersect(
        new Vector(0, 0),
        new Vector(2, 0),
        new Vector(1, 0),
        new Vector(3, 0),
        out intersection, 
        considerCollinearOverlapAsIntersect: true);

    Assert.IsTrue(actual);
    Assert.AreEqual(double.NaN, intersection.X);
    Assert.AreEqual(double.NaN, intersection.Y);
}

Points of Interest

Proper and Non-proper Intersection

There exists a concept of proper and non-proper intersection. A proper intersection is when the two segments share exactly one point and this point lies in the interior of both segments, whereas a non-proper intersection would occur in one of the segments' start or end point. At the moment, the code does not distinguish between these two cases, but a check could be easily added by testing the intersection point for equality against the four input vectors. I guess the choice of whether you would like to include non-proper intersections is up to the use case of your code.

Collinearity and Non-proper Intersection

When two segments are overlapping, e.g. (0,0->2,0) and (1,0->2,0), we have no meaningful concept of an intersection point, as there in theory are an infinite amount of them. However, consider the two line segments along the x-axis (0,0->1,0) and (1,0 ->2,0). These two segments have a non-proper intersection in the point (1,0). If we include non-proper intersections, we actually would have a valid intersection point in this case. As they are collinear, the code will not calculate this intersection point. However, it will return true, if we have set the considerCollinearOverlapAsIntersect parameter to true. Again, the code could be modified to handle this edge case if you see fit.

Changes