Google Answers Logo
View Question
Q: Determining whether two rotated rectangles intersect ( Answered,   3 Comments )
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

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 . 
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,

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

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

regards, mathtalk-ga

Clarification of Question by dbright-ga on 11 Jun 2005 07:10 PDT

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.


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

Thanks again,

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]

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

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>
    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 )
            (  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 */
            (  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 )
            (  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 */
            (  c*xQmin + s*yQmin < -xPdif
            || c*xQmax + s*yQmax >  xPdif
            || c*yQmin - s*xQmax < -yPdif
            || c*yQmax - s*xQmin >  yPdif
            ) ? false : true;
Subject: Re: Determining whether two rotated rectangles intersect
From: mathtalk-ga on 09 Jun 2005 19:41 PDT
Okay, seems pretty straightforward.

-- mathtalk-ga
Subject: Re: Determining whether two rotated rectangles intersect
From: mathtalk-ga on 20 Jun 2005 12:41 PDT
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
Subject: Re: Determining whether two rotated rectangles intersect
From: mathtalk-ga on 26 Jun 2005 19:42 PDT
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]

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

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

Google Home - Answers FAQ - Terms of Service - Privacy Policy