Fastest algorithm to edge detect between two simple rectangles.

Question

Given two simple, rectangles:

class Rectangle
{
    int x;
    int y;
    int width;
    int height;
}

Rectangle a;
Rectangle b;

and the following enumeration:

[Flags]
enum Edges
{
    None,
    Top,
    Bottom,
    Left,
    Right,
    Inside,
}

What is the quickest way to detect the edges on rectangle a which are collided with by rectangle b?

Edges e = EdgeDetect(a, b);

Answer 1

First of all, you have to defines explicitly values of your enum in order to have flags working correctly. In you case Left == Top + Bottom + None. Here is a possible declaration :

[Flags]
public enum Edges
{
    None = 0,
    Top = 1,
    Bottom = 2,
    Left = 4,
    Right = 8,
    Identical = Top + Bottom + Left + Right,
    Inside = 16,
    Covers = 32
}

Next, a possible implementation of edge collision detection. Note that I use the builtin System.Drawing.Rectangle instead of rewriting the class. The immediate advantage is the availability of the Intersect method. :

public static Edges DetectEdgesCollision(Rectangle a, Rectangle b)
{
    var result = Edges.None;

    if (a == b) return Edges.Identical;
    b.Intersect(a);
    if (b.IsEmpty) return Edges.None;
    if (a == b) return Edges.Covers;


    if (a.Top == b.Top && (a.Right >= b.Right && a.Left<=b.Left )) 
        result |= Edges.Top;
    if (a.Bottom == b.Bottom && (a.Right >= b.Right && a.Left<=b.Left ))
        result |= Edges.Bottom;
    if (a.Left == b.Left && (a.Bottom >= b.Bottom && a.Top <= b.Top)) 
        result |= Edges.Left;
    if (a.Right == b.Right && (a.Bottom >= b.Bottom && a.Top <= b.Top)) 
        result |= Edges.Right;


    return result == Edges.None ? Edges.Inside : result;
}

Here is a set of tests that validates this implementation :

    [TestMethod]
    public void RectDoesNotIntersect()
    {
        var a = new Rectangle(0, 0, 10, 10);
        var b = new Rectangle(20, 20, 10, 10);

        var result = Program.DetectEdgesCollision(a, b);

        Assert.AreEqual<Edges>(Edges.None, result);
    }


    [TestMethod]
    public void RectAreNested()
    {
        var a = new Rectangle(0, 0, 30,30);
        var b = new Rectangle(10, 10, 10, 10);

        var result = Program.DetectEdgesCollision(a, b);

        Assert.AreEqual<Edges>(Edges.Inside, result);
    }      
    [TestMethod]
    public void RectCollidesOnTopAndLeft()
    {
        var a = new Rectangle(10, 10, 10, 10);
        var b = new Rectangle(0, 0, 10, 10);

        var result = Program.DetectEdgesCollision(a, b);

        Assert.AreEqual<Edges>(Edges.Left | Edges.Top, result);
    }     
    [TestMethod]
    public void RectCollidesOnBottom()
    {
        var a = new Rectangle(0, 0, 20, 20);
        var b = new Rectangle(10, 10, 5, 50);

        var result = Program.DetectEdgesCollision(a, b);

        Assert.AreEqual<Edges>(Edges.Bottom , result);
    }        

    [TestMethod]
    public void RectAreIdenticals()
    {
        var a = new Rectangle(10, 10, 10, 10);
        var b = new Rectangle(10, 10, 10, 10);

        var result = Program.DetectEdgesCollision(a, b);

        Assert.AreEqual<Edges>(Edges.Identical, result);
    }  
    [TestMethod]
    public void RectBCoversA()
    {
        var a = new Rectangle(10, 10, 10, 10);
        var b = new Rectangle(0, 0, 30, 30);

        var result = Program.DetectEdgesCollision(a, b);

        Assert.AreEqual<Edges>(Edges.Covers, result);
    }