Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

DZone's Guide to

# Utility Classes to Check if lines and/or rectangles intersect

· ·
Free Resource

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

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>();
result);
result);
result);
result);
return result;
}

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)
{
}
}

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

Topics:

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.