Rotated rectangle intersection.

http://answers.google.com/answers/threadview/id/531318.html

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

http://www.metanetsoftware.com/technique.html

http://www.metanetsoftware.com/technique/tutorialA.html

http://www.metanetsoftware.com/technique/tutorialB.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
{
/// <summary>
/// Placeholder top-level class to implement
/// collision detection between RectangleF objects.
/// </summary>
class Class1
{
/// <summary>
/// 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.
/// </summary>
[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;
}
}
}
}

Categorised in: Programming