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);
}
}
Line<Point>
andLine<PointF>
. \$\endgroup\$