Utility classes to check if lines and/or rectangles intersect

I have a for a developer unusual confession to make: I don’t like math. As a tool, great, but as a thing, no. One thing that really infuriates me is than when you want something simple (like intersecting lines and rectangles) all you get is formulas. Even on StackOverflow. I want code. So whenever I translate something from formulas or another computer language, I take care to ‘give back’ the resulting code to prevent other people needing to do the same.

So when I needed a few lines of code to check if lines intersected with each other or with a rectangle – as I need to know when the ball moves over the screen of my Windows Phone app 2 Phone Pong, I was presented with the usual bunch of mathematical formulas… and finally some C code. Which I translated back to C#, so now every sod (like me) can check if a lines intersect with lines, or with a rectangle.

I am not even going to pretend to understand how this actually works, but it does. I have created a class LineF that you can create from two points, and that starts like this:

using System;
using System.Windows;

namespace Wp7nl.Utilities
{
  public class LineF
  {
    public double X1 { get; set; }
    public double Y1 { get; set; }
    public double X2 { get; set; }
    public double Y2 { get; set; }

    public LineF()
    {
    }

    public LineF(double x1, double y1, double x2, double y2)
    {
      X1 = x1;
      Y1 = y1;
      X2 = x2;
      Y2 = y2;
    }

    public LineF(Point from, Point to)
      : this(from.X, from.Y, to.X, to.Y)
    {
    }

    public Point From
    {
      get { return new Point(X1, Y1); }
    }

    public Point To
    {
      get { return new Point(X2, Y2); }
    }
  }
}

And added this method that gives you a Point if there are intersections, and null if there are not. The original method returned some structure that had a field that told you why there were no intersections, but I could not care less about that, so I simplified that a little. You can still see a little of that in the code - the reasons why there are no intersections are still in the comments

/// <summary>
/// Calculates intersection - if any - of two lines
/// </summary>
/// <param name="otherLine"></param>
/// <returns>Intersection or null</returns>
/// <remarks>Taken from http://tog.acm.org/resources/GraphicsGems/gemsii/xlines.c </remarks>
public Point? Intersection(LineF otherLine)
{
  var a1 = Y2 - Y1;
  var b1 = X1 - X2;
  var c1 = X2 * Y1 - X1 * Y2;

  /* Compute r3 and r4.
   */

  var r3 = a1 * otherLine.X1 + b1 * otherLine.Y1 + c1;
  var r4 = a1 * otherLine.X2 + b1 * otherLine.Y2 + c1;

  /* Check signs of r3 and r4.  If both point 3 and point 4 lie on
   * same side of line 1, the line segments do not intersect.
   */

  if (r3 != 0 && r4 != 0 && Math.Sign(r3) == Math.Sign(r4))
  {
    return null; // DONT_INTERSECT
  }

  /* Compute a2, b2, c2 */

  var a2 = otherLine.Y2 - otherLine.Y1;
  var b2 = otherLine.X1 - otherLine.X2;
  var c2 = otherLine.X2 * otherLine.Y1 - otherLine.X1 * otherLine.Y2;

  /* Compute r1 and r2 */

  var r1 = a2 * X1 + b2 * Y1 + c2;
  var r2 = a2 * X2 + b2 * Y2 + c2;

  /* Check signs of r1 and r2.  If both point 1 and point 2 lie
   * on same side of second line segment, the line segments do
   * not intersect.
   */
  if (r1 != 0 && r2 != 0 && Math.Sign(r1) == Math.Sign(r2))
  {
    return (null); // DONT_INTERSECT
  }

  /* Line segments intersect: compute intersection point. 
   */

  var denom = a1 * b2 - a2 * b1;
  if (denom == 0)
  {
    return null; //( COLLINEAR );
  }
  var offset = denom < 0 ? -denom / 2 : denom / 2;

  /* The denom/2 is to get rounding instead of truncating.  It
   * is added or subtracted to the numerator, depending upon the
   * sign of the numerator.
   */

  var num = b1 * c2 - b2 * c1;
  var x = (num < 0 ? num - offset : num + offset) / denom;

  num = a2 * c1 - a1 * c2;
  var y = (num < 0 ? num - offset : num + offset) / denom;
  return new Point(x, y);
}

Now because I needed to be able to find intersections with rectangles as well, I made some extension methods that work on the RectangleF class that is in my wp7nl library on codeplex.

namespace Wp7nl.Utilities
{
  public static class LineFExtensions
  {
    public static List<Point> Intersection(this LineF line, RectangleF rectangle)
    {
      var result = new List<Point>();
      AddIfIntersect(line, rectangle.X, rectangle.Y, rectangle.X2, rectangle.Y, 
                     result);
      AddIfIntersect(line, rectangle.X2, rectangle.Y, rectangle.X2, rectangle.Y2, 
                     result);
      AddIfIntersect(line, rectangle.X2, rectangle.Y2, rectangle.X, rectangle.Y2, 
                     result);
      AddIfIntersect(line, rectangle.X, rectangle.Y2, rectangle.X, rectangle.Y, 
                     result);
      return result;
    }

    private static void AddIfIntersect(LineF line, 
                                       double x1, double y1, double x2, 
                                       double y2, ICollection<Point> result)
    {
      var l2 = new LineF(x1, y1, x2, y2);
      var intersection = line.Intersection(l2);
      if (intersection != null)
      {
        result.Add(intersection.Value);
      }
    }

    /// <summary>
    /// If dx =1 , dy = ??
    /// </summary>
    /// <param name="line"></param>
    /// <returns></returns>
    public static double GetDy(this LineF line)
    {
       var dx = Math.Abs(line.X1 - line.X2);
      var dy = line.Y1 - line.Y2;
      return (dy / dx);
    }
  }
}

This I actually wrote myself, and what is simply does is break the rectangle into four lines and tries to find intersections with each of those lines. The result is a list of Point which is either empty or contains points.

And to prove it actually works, I wrote this little sample Windows Phone application that generates 15 random lines and tries to find the intersection points between all the 15 lines and one fixed rectangle. This gives a this kind of minimalistic art-like results:

Visual proof is maybe not the best, but most certainly the most fun. So this is what I use to determine where the ball in 2 Phone Pong needs to bounce – namely when its trajectory intersects with either the screen side or the paddle.

I hope this is useful to anyone. Write a game with it and ping me back ;-)