Lines, intersections and terrible unit tests

Question

I needed Line and LineF for the next stage of a project I'm working on, so I developed them. I also needed to determine if two lines intersected, preferably as cheaply as possible. (Lots of physics calculations.)

So, I built Line. Then I built LineTests, then LineF.

The intersection code is my favourite part, essentially it builds both lines in slope-intercept form (y = mx + b), then solves for x, then plugs x into the first line to get y, and returns that point.

For this method, I defined coincident lines as not intersecting. (Since they don't intersect at a single point, but instead an infinite number of points.)

Once the point is found, determining if line-segments intersect is simple: just check if the point falls within the bounds of the rectangle of the line. (Why? We already know the point is on some location of the line, which means we only need to determine if it's X falls in the range of our segment X. I built the method to also check the Y since I named it RectContainsPoint.)

So, code for Line.cs:

public struct Line
{
    public const float EqualThreshold = float.Epsilon * 2;

    public Point Start { get; }
    public Point End { get; }
    public Vector2F Vector { get; }

    public Rectangle Bounds => new Rectangle(Start.X, Start.Y, End.X - Start.X, End.Y - Start.X);

    public Line(Point start, Point end)
    {
        Start = start;
        End = end;
        Vector = new Vector2F(End.X - Start.X, End.Y - Start.Y);
    }

    /// <summary>
    /// Gets the <see cref="PointF"/> at which the current <see cref="Line"/> intersects the target <see cref="Line"/>.
    /// </summary>
    /// <param name="l">The target <see cref="Line"/> to test.</param>
    /// <returns>The <see cref="PointF"/> intersection point. Returns <code>null</code> if the lines are parallel, or do not intersect with each line's segment.</returns>
    public PointF? Intersect(Line l) => Intersect(this, l);

    public static PointF? Intersect(Line l1, Line l2)
    {
        var intPoint = IntersectForever(l1, l2);

        if (intPoint == null)
        {
            return null;
        }

        // So we know the intersection point were the lines extended forever, we just need to see if the point fits on our source lines.
        if (l1.WithinX(intPoint.Value) && l2.WithinX(intPoint.Value))
        {
            return intPoint;
        }

        return null;
    }

    /// <summary>
    /// Determines if the <see cref="Bounds"/> contains the specified <see cref="PointF"/>.
    /// </summary>
    /// <param name="pt">The <see cref="PointF"/> to test.</param>
    /// <returns>True if the <see cref="PointF"/> fits in the current <see cref="Bounds"/>.</returns>
    /// <remarks>
    /// If it is already know that the <see cref="PointF"/> fits on the <see cref="Line"/> at <b>some</b> location, then this is an inexpensive operation to see if the <see cref="PointF"/> is within the current <see cref="Line"/> segment.
    /// </remarks>
    public bool RectContainsPoint(PointF pt) => WithinX(pt) && WithinY(pt);

    public bool WithinX(PointF pt) => (pt.X >= Start.X && pt.X <= End.X) || (pt.X <= Start.X && pt.X >= End.X);
    public bool WithinY(PointF pt) => (pt.Y >= Start.Y && pt.Y <= End.Y) || (pt.Y <= Start.Y && pt.Y >= End.Y);

    /// <summary>
    /// Returns a <see cref="PointF"/> which represents the intersection of this line and the specified line if they were extended in each direction forever.
    /// </summary>
    /// <param name="l">The line to intersect with.</param>
    /// <returns>The intersection <see cref="PointF"/> of the two lines. If the lines are parallel then returns <code>null</code>. If the lines coincide, this also returns <code>null</code>.</returns>
    public PointF? IntersectForever(Line l) => IntersectForever(this, l);

    public static PointF? IntersectForever(Line l1, Line l2)
    {
        if (l1.End.X == l1.Start.X)
        {
            // First line is a vertical line
            if (l2.End.X == l2.Start.X)
            {
                // Second line is also vertical, parallel
                return null;
            }

            // Intersection point is a lot easier, just plug the `Start.X` into the second line's formula.
            var m = (float)(l2.End.Y - l2.Start.Y) / (l2.End.X - l2.Start.X);
            var b = -(m * l2.Start.X) + l2.Start.Y;

            return new PointF(l1.Start.X, m * l1.Start.X + b);
        }

        if (l2.End.X == l2.Start.X)
        {
            // Second line is a vertical line
            // Intersection point is a lot easier, just plug the `line.Start.X` into the first line's formula.
            var m = (float)(l1.End.Y - l1.Start.Y) / (l1.End.X - l1.Start.X);
            var b = -(m * l1.Start.X) + l1.Start.Y;

            return new PointF(l2.Start.X, m * l2.Start.X + b);
        }

        // We'll need the slopes of both lines
        var m1 = (float)(l1.End.Y - l1.Start.Y) / (l1.End.X - l1.Start.X);
        var m2 = (float)(l2.End.Y - l2.Start.Y) / (l2.End.X - l2.Start.X);

        // (Mostly) equal slopes indicate the lines are parallel and will never intersect.
        if (Math.Abs(m1 - m2) <= EqualThreshold)
        {
            return null;
        }

        // The slopes are different enough that we need the intercepts
        var b1 = -(m1 * l1.Start.X) + l1.Start.Y;
        var b2 = -(m2 * l2.Start.X) + l2.Start.Y;

        // Get the X and Y coordinates of the intersection, we'll solve the two formulas for `x`, which gives us the following transformations:
        //      y = m1 * x + b1, y = m2 * x + b2
        //      m1 * x + b1 = m2 * x + b2
        //      m1 * x = m2 * x + b2 - b1
        //      m1 * x - m2 * x = b2 - b1
        //      (m1 - m2) * x = b2 - b1
        //      x = (b2 - b1) / (m1 - m2)
        var x = (b2 - b1) / (m1 - m2);
        var y = m1 * x + b1;

        return new PointF(x, y);
    }
}

Code for LineF.cs:

public struct LineF
{
    public PointF Start { get; }
    public PointF End { get; }
    public Vector2F Vector { get; }

    public RectangleF Bounds => new RectangleF(Start.X, Start.Y, End.X - Start.X, End.Y - Start.X);

    public LineF(PointF start, PointF end)
    {
        Start = start;
        End = end;
        Vector = new Vector2F(End.X - Start.X, End.Y - Start.Y);
    }

    /// <summary>
    /// Gets the <see cref="PointF"/> at which the current <see cref="LineF"/> intersects the target <see cref="LineF"/>.
    /// </summary>
    /// <param name="l">The target <see cref="LineF"/> to test.</param>
    /// <returns>The <see cref="PointF"/> intersection point. Returns <code>null</code> if the lines are parallel, or do not intersect with each line's segment.</returns>
    public PointF? Intersect(LineF l) => Intersect(this, l);

    public static PointF? Intersect(LineF l1, LineF l2)
    {
        var intPoint = IntersectForever(l1, l2);

        if (intPoint == null)
        {
            return null;
        }

        // So we know the intersection point were the lines extended forever, we just need to see if the point fits on our source lines.
        if (l1.WithinX(intPoint.Value) && l2.WithinX(intPoint.Value))
        {
            return intPoint;
        }

        return null;
    }

    /// <summary>
    /// Determines if the <see cref="Bounds"/> contains the specified <see cref="PointF"/>.
    /// </summary>
    /// <param name="pt">The <see cref="PointF"/> to test.</param>
    /// <returns>True if the <see cref="PointF"/> fits in the current <see cref="Bounds"/>.</returns>
    /// <remarks>
    /// If it is already know that the <see cref="PointF"/> fits on the <see cref="LineF"/> at <b>some</b> location, then this is an inexpensive operation to see if the <see cref="PointF"/> is within the current <see cref="LineF"/> segment.
    /// </remarks>
    public bool RectContainsPoint(PointF pt) => WithinX(pt) && WithinY(pt);

    public bool WithinX(PointF pt) => (pt.X >= Start.X && pt.X <= End.X) || (pt.X <= Start.X && pt.X >= End.X);
    public bool WithinY(PointF pt) => (pt.Y >= Start.Y && pt.Y <= End.Y) || (pt.Y <= Start.Y && pt.Y >= End.Y);

    /// <summary>
    /// Returns a <see cref="PointF"/> which represents the intersection of this line and the specified line if they were extended in each direction forever.
    /// </summary>
    /// <param name="l">The line to intersect with.</param>
    /// <returns>The intersection <see cref="PointF"/> of the two lines. If the lines are parallel then returns <code>null</code>. If the lines coincide, this also returns <code>null</code>.</returns>
    public PointF? IntersectForever(LineF l) => IntersectForever(this, l);

    public static PointF? IntersectForever(LineF l1, LineF l2)
    {
        if (l1.End.X == l1.Start.X)
        {
            // First line is a vertical line
            if (l2.End.X == l2.Start.X)
            {
                // Second line is also vertical, parallel
                return null;
            }

            // Intersection point is a lot easier, just plug the `Start.X` into the second line's formula.
            var m = (float)(l2.End.Y - l2.Start.Y) / (l2.End.X - l2.Start.X);
            var b = -(m * l2.Start.X) + l2.Start.Y;

            return new PointF(l1.Start.X, m * l1.Start.X + b);
        }

        if (l2.End.X == l2.Start.X)
        {
            // Second line is a vertical line
            // Intersection point is a lot easier, just plug the `line.Start.X` into the first line's formula.
            var m = (float)(l1.End.Y - l1.Start.Y) / (l1.End.X - l1.Start.X);
            var b = -(m * l1.Start.X) + l1.Start.Y;

            return new PointF(l2.Start.X, m * l2.Start.X + b);
        }

        // We'll need the slopes of both lines
        var m1 = (float)(l1.End.Y - l1.Start.Y) / (l1.End.X - l1.Start.X);
        var m2 = (float)(l2.End.Y - l2.Start.Y) / (l2.End.X - l2.Start.X);

        // (Mostly) equal slopes indicate the lines are parallel and will never intersect.
        if (Math.Abs(m1 - m2) < float.Epsilon * 2)
        {
            return null;
        }

        // The slopes are different enough that we need the intercepts
        var b1 = -(m1 * l1.Start.X) + l1.Start.Y;
        var b2 = -(m2 * l2.Start.X) + l2.Start.Y;

        // Get the X and Y coordinates of the intersection, we'll solve the two formulas for `x`, which gives us the following transformations:
        //      y = m1 * x + b1, y = m2 * x + b2
        //      m1 * x + b1 = m2 * x + b2
        //      m1 * x = m2 * x + b2 - b1
        //      m1 * x - m2 * x = b2 - b1
        //      (m1 - m2) * x = b2 - b1
        //      x = (b2 - b1) / (m1 - m2)
        var x = (b2 - b1) / (m1 - m2);
        var y = m1 * x + b1;

        return new PointF(x, y);
    }
}

And the LineTests:

[TestClass]
public class LineTests
{
    [TestMethod]
    public void Intersect_OnePositive_OneNegative_Line_0_0_2_2_Line_2_0_0_2()
    {
        // \  /
        //  \/
        //  /\
        // /  \
        var expected = new PointF(1f, 1f);
        var l1 = new Line(new Point(0, 0), new Point(2, 2));
        var l2 = new Line(new Point(2, 0), new Point(0, 2));

        var actual = Line.Intersect(l1, l2).Value;

        Assert.AreEqual(expected, actual);
    }

    [TestMethod]
    public void Intersect_Coincident_Line_0_0_2_2_Line_0_0_2_2()
    {
        //    /
        //   /
        //  /
        // /
        var l1 = new Line(new Point(0, 0), new Point(2, 2));
        var l2 = new Line(new Point(0, 0), new Point(2, 2));

        var result = Line.Intersect(l1, l2);

        Assert.IsNull(result);
    }

    [TestMethod]
    public void Intersect_Coincident_Line_0_0_2_2_Line_1_1_3_3()
    {
        //      /
        //     /
        //    /
        //   /
        //  /
        // /
        var l1 = new Line(new Point(0, 0), new Point(2, 2));
        var l2 = new Line(new Point(1, 1), new Point(3, 3));

        var result = Line.Intersect(l1, l2);

        Assert.IsNull(result);
    }

    [TestMethod]
    public void Intersect_OneHorizontal_OnePositive_Line_0_0_2_2_Line_0_1_2_1()
    {
        //    /
        // __/_
        //  /
        // /
        var expected = new PointF(1f, 1f);
        var l1 = new Line(new Point(0, 0), new Point(2, 2));
        var l2 = new Line(new Point(0, 1), new Point(2, 1));

        var actual = Line.Intersect(l1, l2).Value;

        Assert.AreEqual(expected, actual);
    }

    [TestMethod]
    public void Intersect_OneVertical_OnePositive_Line_0_0_2_2_Line_1_0_1_2()
    {
        //   |/
        //   |
        //  /|
        // / |
        var expected = new PointF(1f, 1f);
        var l1 = new Line(new Point(0, 0), new Point(2, 2));
        var l2 = new Line(new Point(1, 0), new Point(1, 2));

        var actual = Line.Intersect(l1, l2).Value;

        Assert.AreEqual(expected, actual);
    }

    [TestMethod]
    public void Intersect_BothVertical_Line_0_0_0_2_Line_1_0_1_2()
    {
        // | |
        // | |
        // | |
        // | |
        var l1 = new Line(new Point(0, 0), new Point(0, 2));
        var l2 = new Line(new Point(1, 0), new Point(1, 2));

        var result = Line.Intersect(l1, l2);

        Assert.IsNull(result);
    }

    [TestMethod]
    public void Intersect_OneVertical_OneHorizontal_Line_1_0_1_2_Line_0_1_2_1()
    {
        //   |
        // __|_
        //   |
        //   |
        var expected = new PointF(1f, 1f);
        var l1 = new Line(new Point(1, 0), new Point(1, 2));
        var l2 = new Line(new Point(0, 1), new Point(2, 1));

        var actual = Line.Intersect(l1, l2);

        Assert.AreEqual(expected, actual);
    }

    [TestMethod]
    public void Intersect_BothPositive_Line_0_0_2_2_Line_1_0_2_2()
    {
        //   _/
        // _//
        //  /
        // /
        var expected = new PointF(2f, 2f);
        var l1 = new Line(new Point(0, 0), new Point(2, 2));
        var l2 = new Line(new Point(1, 0), new Point(2, 2));

        var actual = Line.Intersect(l1, l2);

        Assert.AreEqual(expected, actual);
    }

    [TestMethod]
    public void Intersect_BothHorizontal_Line_0_0_2_0_Line_0_1_2_1()
    {
        // 
        // ____
        // 
        // ____
        var l1 = new Line(new Point(0, 0), new Point(2, 0));
        var l2 = new Line(new Point(0, 1), new Point(2, 1));

        var result = Line.Intersect(l1, l2);

        Assert.IsNull(result);
    }
}

Answer 1

I don't see the benefits of having both static and non-static API: PointF? Intersect and static PointF? Intersect. It does not bring any new possibilities, but it does cause inconsistencies in usage (personally I hate it when there are multiple ways of doing exactly the same thing) and additional unit testing. I would remove static version completely and keep only non-static one. However I think that creating an external static class, similar to Math, and moving any complex math there from Line class - is a good strategy too.

---

There is a lot of copy-pasting even inside Line class itself, let alone between the two implementations.You should move common logic to private methods. You can even create an additional class to represent infinite line. This looks a lot better, IMHO:

struct InfiniteLine
{
    public InfiniteLine(Line line)
    {
        ...
    }

    public InfiniteLine(LineF line)
    {
        ...
    }

    bool IsVertical => ...
    float Slope { get; }
    float Intercept { get; }

    public PointF? Intersect(InfiniteLine other)
    {
        if (IsParallel(other)) return null;

        if (IsVertical) return other.IntersectWithVertical(this); 

        if (other.IsVertical) return IntersectWithVertical(other);

        var x = ...;
        var y = ...;
        return new PointF(x, y);
    }

    private PointF? IntersectWithVertical(InfiniteLine other) { ... }
    private bool IsParallel(InfiniteLine other) { ... }
}

and

struct Line
{
    ....

    public PointF? Intersect(Line other)
    {
        var l1 = this.ToInfinite();
        var l2 = other.ToInfinite();

        var point = l1.Intersect(l2);

        if (point.HasValue && WithinX(point.Value) && other.WithinX(point.Value))
        {
            return point ;
        }

        return null;
    }
}

However, I agree with sir I'll add comments tomorrow, you probably need to pick up a better mathematical model to describe infinite lines in order to avoid special cases for vertical lines. Maybe ax + by = c ? The formula for intersection will be a bit more complex, but there will be no special cases.

Answer 2

This is more of a long comment.

essentially it builds both lines in slope-intercept form (y = mx + b)

This doesn't work for vertical lines, because a vertical line cannot be a function (in the mathematical sense).

You detect this edge case in your code. I would prefer using some other mathematical model for a line to perform the calculations that doesn't have this shortcoming in the first place. That would mean to have less code dealing with special cases to distract the reader. Thus is subjective of course.

You have identical code in your classes except for the type of point:

public PointF Start { get; }
public PointF End { get; }
public Vector2F Vector { get; }

public RectangleF Bounds => new RectangleF(Start.X, Start.Y, End.X - Start.X, End.Y - Start.X);

I'd refactor that into an abstract generic superclass AbstractLine<PointType> and let the two line classes extend that. Going generic has the advantage that you work with the exact type in each sub class. Using a common superclass of both point objects would make casting necessary. The downside is that you'd have to first create a common super type in the form of an interface for both point types anyway in order to restrict the generic type.

I'm not sure what the point is (pun intended) in having those two versions of what's essentially the same class. The result is a PointF either way.

Answer 3

As discussed in comments, there are better ways of doing the calculation, which in particular avoid the need for so many special cases. This is important because the failure to consider all of the special cases means that the code you've posted is buggy. Consider the following unit test:

        var l1 = new Line(new Point(0, 0), new Point(2, 2));
        var l2 = new Line(new Point(1, 3), new Point(1, 4));
        var result = Line.Intersect(l1, l2);
        Assert.IsNull(result);

Answer 4

I quite like the ASCII art you've got at the top of your tests, it's a good way to illustrate the lines that you're working with for that test.

That said, I'd consider adding an expectation to your test names. Naming is obviously a subjective thing and there are various different approaches. One thing that most of them have in common is some combination of "What is being tested" and "What is expected to happen". At the moment, your test names are very much focused on the inputs to the test are, rather than the outcomes. So, taking two tests as example:

Intersect_OneVertical_OneHorizontal_Line_1_0_1_2_Line_0_1_2_1
Intersect_BothHorizontal_Line_0_0_2_0_Line_0_1_2_1

The first test validates that the two lines intersect and checks the position. The second test validates that the two lines do not intersect. There's no clue from the title that the tests are testing different outcomes. In fact, due to the method prefix (Intersect), the initial impression I got was that the second test was actually checking that two horizontal lines will intersect.

I'd consider adding an expectation, so something like:

Intersect_OneVertical_OneHorizontal_Line_Should_Intersect
Intersect_TwoHorizontal_Lines_ShouldNot_Intersect

I've removed the LinePoints from the suggested titles, because unless you're testing the same scenario with different points, I think they just add noise and confusion to the title. If I need to know the exact line points, I can look at the actual test, at a high level I just want to know about the scenario, not the detail.