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

## No comments:

Post a Comment