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