Самый быстрый алгоритм обнаружения краев между двумя простыми прямоугольниками.

Question

Имеются два простых прямоугольника:

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

Rectangle a;
Rectangle b;

и следующее перечисление:

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

Какой самый быстрый способ обнаружить ребра прямоугольника a , с которыми сталкивается прямоугольник b?

Edges e = EdgeDetect(a, b);

Answer 1

public Edges DetectEdge(Rect A, Rect B) { 
   rectC = rectA.Intersect(rectB);
    if(rectC.IsEmpty) return Edges.None;
    Edge edge = Edges.Inside;
    if(rectA.X+rectA.Width == rectB.X || rectA.X == rectB.X){
     edge = Edges.Left;
    }
    if(rectA.Y+rectA.Height == rectB.Y || rectA.Y == rectB.Y){
     edge = edge | Edges.Top;
    }
    if(rectA.X  == rectB.X + rectB.Width 
         || rectA.X + rectA.Width == rectB.X + rectB.Width){
     edge = edge | Edges.Right;
    }
    if(rectA.Y == rectB.Y + rectB.Heigth 
         || rectA.Y + rectA.Height == rectB.Y + rectB.Height){
     edge = edge | Edges.Bottom;
    }
    return edge;
}

Answer 2

Прежде всего, вы должны явно определить значения вашего перечисления, чтобы флаги работали правильно. В твоем случае Left == Top + Bottom + None. Вот возможная декларация:

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

Далее возможна реализация обнаружения краевых столкновений. Обратите внимание, что я использую встроенный System.Drawing.Rectangle вместо переписывания класса. Непосредственным преимуществом является доступность метода Intersect. :

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

Вот набор тестов, который проверяет эту реализацию:

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