.NET Zone is brought to you in partnership with:

A.k.a. LocalJoost (which sounds very much like localhost); Senior software architect/Developer C#, ASP.NET, Windows Phone 7 Developer MVP, XAML enthusiast, MVVMLight addict, Rogue R&D hacker, Gardener, Photograper, Amateur philosopher. Joost is a DZone MVB and is not an employee of DZone and has posted 45 posts at DZone. You can read more from them at their website. View Full User Profile

Utility Classes to Check if lines and/or rectangles intersect

10.06.2013
| 2524 views |
  • submit to reddit

For a developer, I have an 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:

intersections1intersections2intersections3

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 ;-)

Published at DZone with permission of Joost Van Schaik, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)