View Question
Q: Determining whether two rotated rectangles intersect ( Answered,   3 Comments )
 Question
 Subject: Determining whether two rotated rectangles intersect Category: Computers > Algorithms Asked by: dbright-ga List Price: \$30.00 Posted: 09 Jun 2005 06:52 PDT Expires: 09 Jul 2005 06:52 PDT Question ID: 531318
 ```Hello, I'm looking for C# code to determine whether two RectangleF objects intersect. The catch is that these rectangles may be rotated by a given angle. Ideally, I'd like a function that takes two RectangleF objects and an angle in degrees and returns a boolean value indicating whether the rectangles intersect. As a starting point, there is some C++ code and an explanation of how to do this at http://www.ragestorm.net/tutorial?id=22 . Unfortunately, I don't have time to translate this into C# using the required objects so I'm hoping to get some help here. Thanks in advance, Doug``` Request for Question Clarification by mathtalk-ga on 11 Jun 2005 03:04 PDT ```Hi, dbright-ga: The RectangleF object, as you imply, does not include a rotation angle. In the code presented by Oren Becker, he manages the data in terms of: - rectangle 1, centered at the origin but with an arbirary rotation - rectangle 2, sides parallel to axes but with an arbitrary center Since RectangleF objects only have sides parallel to the axes, one approach to declaring parameters for your method would be to have two RectangleF objects plus a rotation angle, as you describe, but we should be a bit careful about what interpretation is intended by the angle. In connection with the code you linked, the easiest interpretation for the sake of implementation is that the angle corresponds to the rotation of rectangle 1 about its center, ie. the rotation applied to it after both rectangles are given a common translation to center rectangle 1 about the origin. If this is acceptable, please let me know, or if not, then suggest a different interpretation for these more or less minimal calling arguments. regards, mathtalk-ga``` Clarification of Question by dbright-ga on 11 Jun 2005 07:10 PDT ```Hello, You're absolutely right, I failed to specify the rotation point -- the rectangle is rotated about the lower left corner of the RectangleF. Also, the coordinate system is classical Cartesian -- not the inverted drawing system used by Windows. The rectangles can exist in all four quadrants of the system. Though I'm not sure that it will have an impact on the function, our convention is that positive angles specify counter-clockwise rotation. Please don't hesitate to contact me if you need any further clarification. Thanks for your help. Doug``` Clarification of Question by dbright-ga on 11 Jun 2005 07:16 PDT ```One more thing -- This function will be used as part of a O(n^2) algorithm in time so the leaner you can make it the better. Of course, I didn't specify this in the question so it is not required, but it would be really helpful if the function were as quick as possible. Thanks again, Doug``` Clarification of Question by dbright-ga on 11 Jun 2005 10:52 PDT ```Ugh, sorry to keep posting, but upon further inspection, the rectangle as actually rotated about the *midpoint* of the left side, not the lower left corner. Sorry for the confusion.``` Request for Question Clarification by mathtalk-ga on 16 Jun 2005 06:38 PDT ```Hi, dbright-ga: Just an update. I'm working with a different, hopefully faster algorithm to check for intersection of rectangles. I'll post more details below as a Comment. regards, mathtalk-ga``` Clarification of Question by dbright-ga on 21 Jun 2005 07:27 PDT ```Hi mathtalk, Sounds good. Thanks for your consideration of the efficiency of the algorithm -- I look forward to the result.``` Request for Question Clarification by mathtalk-ga on 28 Jun 2005 06:54 PDT ```Hi, dbright-ga: I've run my code, which implements a public static method returning boolean as part of a simple Console application class, on a few simple cases. Obviously more testing will be needed to find any reversed inequalities or other goofs. Would you like me to go ahead and post the code as an Answer, so we can test in parallel? You may want to begin looking at how to adapt the code for your framework. regards, mathtalk-ga```
 Subject: Re: Determining whether two rotated rectangles intersect Answered By: mathtalk-ga on 28 Jun 2005 21:18 PDT
 ```Hi, dbright-ga: Before I dive into the C# code I wrote, a few comments about the context and potentially untapped optimizations may be useful. One motivation for detecting rectangle-to-rectangle intersections is collision detection in computer graphics/video games/robotics. In such applications some (or most) pairs of rectangles may be tracked for many "frames" before any collision occurs (if ever). This puts a premium on quickly determining that no intersection exists, and also creates some additional computational tasks for the "rare" events when objects do intersect. For a broad but informative discussion, see: [Collision Detection and Response] http://www.harveycartel.org/metanet/tutorials/tutorialA.html Nothing was stated about the application you have in mind, so I've not gone fully in the direction of optimizing for empty intersection being much the likeliest outcome. I aim for a sort of balance in chances between the two possible outcomes (empty vs. nonempty), and while I think the approach presented here improves on Oren Becker's and on the group effort at CodWiki (see Comment below), but I've got a feeling there is substantial room for improvement left. If one wants to do the above sort of optimization, often one appeals to ideas of "frame coherence", basically meaning that not much changes from one frame of motion to the next frame. Thus one can "remember" from one frame to the next, for each pair of rectangles that require collision detection, some easily computed expression that suffices to imply the intersection is empty. As we will see in discussing the algorithm I chose, such "witnesses" are pretty easy to identify in the process. But my implementation assumes nothing about any prior execution, and it makes no effort to store what turns out to be the key expression "proving" empty intersection. One other quibble to point out, before we begin in earnest, is that I take "intersection" between two figures to mean "set intersection" of two closed polygonal regions, ie. the interiors plus boundaries. Other approaches may require an interior overlap. There are arguments for disregarding certain overlaps limited to some boundary points from counting as a "collision" or as an intersection. In particular when one deals with a low-resolution "pixel based" figures, it is tempting to ignore an overlap limited to corners of two rectangles, as that overlap is in a sense two dimensions below the figures themselves (points being zero dimensional). However we are using here floats to describe the figures, and the high resolution convinces me that an intersection is an intersection, if even a single point is common to both rectangles. * * * * * * * * * * * * * * * * * * * Let's begin with the nearly trivial case of two unrotated rectangles, which we will label P and Q for consistency with our later notation. The sides of both rectangles are assumed parallel to axes, and they will have nonempty intersection exactly when their x-coordinate ranges overlap and their y-coordinate ranges overlap. (Possibly one figure is contained entirely within the other; the characterization still is true.) Imagine the object P and Q to be endowed with defining members xMax, yMax, xMin, and yMin, having the obvious meanings. Then our C# code may read something like: if ( P.xMin > Q.xMax || Q.xMin > P.xMax || P.yMin > Q.yMax || Q.yMin > P.yMax ) return false; else return true; Indeed we handle the special case angle = 0.0 in our code like this, for it is hard to imagine improving on its efficiency without programming closer to the metal. Algorithms to check for intersection of polygons sometimes spend time checking whether the vertices of one are contained in the other. This is intuitively likely, if one imagines one polygon having just bumped into the other, but it is not conclusive for empty intersections if no vertex of either polygon is contained in the other, even for rectangles. What is conclusive (for two convex polygons) is the following: Two convex polygons have empty intersection if and only if one polygon has an edge whose "halfplane" excludes all vertices of the other polygon. [By halfplane here is meant the line through the endpoints of a polygon's edge segment, together with all the points of the plane that happen to fall on the same "side" of that line as the other vertices of that polygon. The convex polygonal region is then an intersection of all the halfplanes corresponding to its edges. Clearly the complement of a (closed) halfplane, while not closed in the sense that it lacks its boundary points, is a convex set. So if the other polygon's vertices all belong to the complement of one of the halfplanes, it proves that the two polygons do not intersect (because the convex hull of the other polygon's vertices is the other polygonal region and will be excluded by this). The other half of the implication is more difficult, showing that two disjoint convex polygons must have between them an edge of one that excludes the other. It seems to be a "folk theorem" among the computer graphics community, but I could find (or cook up!) a short proof. Perhaps I can tack on such a proof later, but I'm certain we can rely upon this criterion.] Let P be a rectangle, centered at the origin and rotated about the origin through an angle a (we'll deal with your requirement to rotate instead around the midpoint of the left side of P in just a bit). Since the original rectangle was symmetric around the origin, it remains so no matter how it is rotated. In fact then the vertex whose x-coordinate is now greatest is opposite (through the center/origin) to the vertex whose x-coordinate is least, and similarly the other pair of vertices gives the range of least to greatest y-coordinates. One can then easily frame the tilted rectangle P inside a "bounding box" of a standard/untilted rectangle which matches its range of x-coordinates and y-coordinates exactly. This bounding box will then be easily checked, by the method already described, for any intersection with standard rectangle Q. Clearly if the bounding box and Q have empty intersection, then it implies P and Q have empty intersection as well. While the converse is not necessarily true, what we can say is that if the bounding box and Q have nonempty intersection, then no edge of Q excludes every vertex of P. It is in this sense, modulo the folk theorem above, that a nonempty intersection between the bounding box of P and the original rectangle Q tells us half of what we need to conclude that P and Q have nonempty intersection. So let's lay out the program when angle is nonzero in these terms: Phase 1: Determine if all vertices of P are excluded by some edge of Q (equivalent to the bounding box check just described). Phase 2: Determine if all vertices of Q are excluded by some edge of P (implemented in a similar way, but with "sloping" edges). If the result in either Phase 1 or Phase 2 is "success" at finding an edge of one rectangle that excludes all vertices of the other, then we report the intersection of P and Q is empty. Otherwise we know from "failure" in both Phases that the intersection is nonempty! Now I've positioned the Phases in this order because testing the vertices of P against the edges of Q uses less computation. We will need the sine and cosine of the angle, so there's a couple of calls to the Math functions in C#, and we won't agonize over that for the time being. By a simple test of the signs of the sine and cosine (no confusion intended!) we can figure out which of the rotated vertices of P give the maximum and the minimum x-coordinates, and which pair (the other pair, in fact) gives the maximum and the minimum y-coordinate. If one of these ranges does not overlap with the x- or y-ranges of the coordinates of rectangle Q, it means some edge of Q excludes all the vertices of P (such an edge of Q excluding the vertices of P being equivalent to the empty intersection of rectangle Q and the bounding box on P). This latter computation requires multiplying the width and the height of P by the sine and cosine of a, so that's four multiplications (but we might get lucky with the first pair of multiplications and not need the second pair). In the best case Phase 1 tells us that the two rectangles have empty intersection. In the worst case we proceed to Phase 2, where at most 8 multiplications will be needed if there is a nonempty intersection. We'll have ruled out any possibility by then that an edge of P excludes all vertices of Q. Well, enough discussion. What follows is the code for my C# project. The only "hidden" aspect is that I added a project reference for the System.Drawing.dll .Net component, since that's where the RectangleF class you wanted to use is implemented, so that shouldn't surprise you. regards, mathtalk-ga * * * * * * * * * * * * * * * * * * * * * * * using System; using System.Drawing; namespace mathtalk_GA.Rectangle_Collision { /// /// Placeholder top-level class to implement /// collision detection between RectangleF objects. /// class Class1 { /// /// A simple console application to host a method /// which returns a Boolean True/False for nonempty /// intersection between two rectangles, represented /// as .Net Framework RectangleF objects. /// [STAThread] static int Main(string[] args) { // // Minimal code need to instantiate two RectangleF objects // and call Class1 method RectCollide. // RectangleF rP, rQ; rP = new RectangleF(-1.0f,1.0f,6.0f,4.5f); rQ = new RectangleF(2.0f,0.0f,1.0f,0.5f); bool result; result = RectCollide(-1.4,rP,rQ); // false; increase angle // slightly to get true Console.WriteLine("result is {0}", result); if (result) return 1; else return 0; } public static bool RectCollide(double angle, RectangleF rP, RectangleF rQ) { // Calling arguments similar to a C implementation by Oren Becker // but different algorithm for detecting rectangle intersection. // angle gives rotation of the first rectangle around its left side's // midpoint. The second rectangle is unrotated, aligned to axes. double xPmin, xPmax, yPmin, yPmax, xQmin, xQmax, yQmin, yQmax; if ( angle == 0.0 ) { xPmax = ( xPmin = rP.X ) + rP.Width; yPmax = ( yPmin = rP.Y ) + rP.Height; xQmax = ( xQmin = rQ.X ) + rQ.Width; yQmax = ( yQmin = rQ.Y ) + rQ.Height; return ( xPmin > xQmax || xQmin > xPmax || yPmin > yQmax || yQmin > yPmax ) ? false : true; } // Otherwise we need two trigonometric function calls double c = Math.Cos(angle), s = Math.Sin(angle); bool cPos = ( c > 0.0 ), sPos = ( s > 0.0 ); /* Phase 1: Form bounding box on tilted rectangle P. * Check whether bounding box and Q intersect. * If not, then P and Q do not intersect. * Otherwise proceed to Phase 2. */ double xPdif, yPdif, xPctr, yPctr, cxPdf, sxPdf, cyPdf, syPdf; xPdif = 0.5 * rP.Width; yPdif = 0.5 * rP.Height; /* P rotates around the midpoint of its left side. */ xPctr = rP.X + ( cxPdf = c * xPdif ); yPctr = rP.Y + ( sxPdf = s * xPdif ) + yPdif; cyPdf = c * yPdif; syPdf = s * yPdif; /* Translate coordinates of Q so P is re-centered at origin. */ xQmax = ( xQmin = rQ.X - xPctr ) + rQ.Width; yQmax = ( yQmin = rQ.Y - yPctr ) + rQ.Height; /* Compute the bounding box coordinates for P. */ if ( cPos ) if ( sPos ) { xPmin = -( xPmax = cxPdf + syPdf ); yPmin = -( yPmax = cyPdf + sxPdf ); } else /* s <= 0.0 */ { xPmin = -( xPmax = cxPdf - syPdf ); yPmin = -( yPmax = cyPdf - sxPdf ); } else /* c <= 0.0 */ if ( sPos ) { xPmax = -( xPmin = cxPdf - syPdf ); yPmax = -( yPmin = cyPdf - sxPdf ); } else /* s <= 0.0 */ { xPmax = -( xPmin = cxPdf + syPdf ); yPmax = -( yPmin = cyPdf + sxPdf ); } /* Now perform the standard rectangle intersection test. */ if ( xPmin > xQmax || xQmin > xPmax || yPmin > yQmax || yQmin > yPmax ) return false; /* Phase 2: If we get here, check the edges of P to see * if one of them excludes all vertices of Q. * If so, then P and Q do not intersect. * (If not, then P and Q do intersect.) */ if ( cPos ) { if ( sPos ) return ( c*xQmax + s*yQmax < -xPdif || c*xQmin + s*yQmin > xPdif || c*yQmax - s*xQmin < -yPdif || c*yQmin - s*xQmax > yPdif ) ? false : true; else /* s <= 0.0 */ return ( c*xQmax + s*yQmin < -xPdif || c*xQmin + s*yQmax > xPdif || c*yQmax - s*xQmax < -yPdif || c*yQmin - s*xQmin > yPdif ) ? false : true; } else /* c <= 0.0 */ { if ( sPos ) return ( c*xQmin + s*yQmax < -xPdif || c*xQmax + s*yQmin > xPdif || c*yQmin - s*xQmin < -yPdif || c*yQmax - s*xQmax > yPdif ) ? false : true; else /* s <= 0.0 */ return ( c*xQmin + s*yQmin < -xPdif || c*xQmax + s*yQmax > xPdif || c*yQmin - s*xQmax < -yPdif || c*yQmax - s*xQmin > yPdif ) ? false : true; } } } }```
 ```Okay, seems pretty straightforward. -- mathtalk-ga```
 ```The algorithm discussed and implemented by Oren Becker at the link noted above is to use one pair of limits from the rectangle in "standard position" (sides parallel to the coordinate axes) to cut off a new convex polygon from the other (tilted) rectangle, which results in as many as six vertices to consider for the final step of comparing their range (in the other coordinate direction) to the range given by the first rectangle's other pair of limits. It will in general be necessary to compute as many as four points of intersection in the first phase of that algorithm. A preliminary part of this calculation is finding an edge (consecutive pair of vertices) of the tilted rectangle that "straddle" one or both of the pair of limits involved in this initial "truncation" phase. It seems more expeditious to me to exploit this characterization of when two convex polygons (in a plane) have empty intersection: Two convex polygons have empty intersection if and only if one polygon has an edge that defines a closed halfplane excluding all vertices of the other polygon (while including all its vertices). This test is especially attractive in our case of a pair of rectangles because the "separating edge" test can be done for the two parallel edges in combined fashion (which simply amounts to a coordinate comparison for the edges of the untilted rectangle). The computational cost, at least on average, with this approach appears to me better, as we never compute points of intersection. There is an opportunity for an "early" exit if some edge of the untilted rectangle excludes all vertices of the tilted rectangle or if certain other inclusions of those vertices imply a nonempty intersection. No divisions are required, even if we must check if some edge of the tilted rectangle excludes the vertices of the untilted rectangle. regards, mathtalk-ga```
 ```I'm the throes of re-compiling and re-optimizing my C# code. I did find a site that has some C# code for various "collision detection" problems, including the rotated rectangle to rectangle figure: [CODWiki: CollideMeUpBaby] http://www.freelunchdesign.com/cgi-bin/codwiki.pl?DiscussionTopics/CollideMeUpBaby It's from a Nov. 2003 posting, and he simply treats the rotated rectangle to rectangle problem as a special case of the rotated rectangle to rotated rectangle problem, setting one angle to zero. My own analysis shows that Oren Becker's intuition of splitting the symmetry/asymmetry between the two rectangles (having one centered at the origin but maybe tilted, the other centered elsewhere but with sides parallel to axes) does result in a simplified computation. If we take as the "benchmark" the two untilted/unrotated rectangles case, which is pretty trivial (almost no arithmetic, just some inequality checks), then my rotated rectangle to "standard" rectangle cost turns out to be (in worst case) two of those rectangle to rectangle comparisons (in terms of the same sorts of inequality checks) plus two trig evaluations (sine and cosine of the one angle) and at most 12 multiplications and half as many additions/subtractions. The floating point arithmetic may be less if the intersection is empty, but cases where the two rectangles intersect will require all of them to make the determination. regards, mathtalk-ga```