Search all valid positions of a rectangle in map with obstacles

Question

I'm trying to find a solution to locate valid positions for a provided rectangle in a limited space that already contains other rectangles (obstacles) of different sizes.

The space can be described as a 2-Dimensional Boolean Array where true values describe a claimed coordinate.

The rectangles to check of can be of size 1 or greater up till the size of the whole space.

The focus of the algorithm is on speed with no regard for memory usage.

The solution I came up with so far divides the available space into smaller rectangles each time an area is claimed and merges them back together when it is released.

private readonly Rect[,] _matrix;
public SortedSet<Rect> Rects { get; } = new();

public void Claim(Rect rect)
{
    Rect parentRect = _matrix[rect.X, rect.Y];

    if (parentRect.Claimed) 
        throw new InvalidOperationException("Area already claimed");

    if (parentRect == rect)
    {
        parentRect.Claimed = true;
        return;
    }

    if (!parentRect.Contains(rect)) 
        throw new InvalidOperationException("Rect was not placed inside a valid space");

    rect.Claimed = true;

    List<Rect> newRects = new() { rect };

    if (parentRect.Left != rect.Left) 
        newRects.Add(new Rect(parentRect.Left, rect.Left, parentRect.Top, parentRect.Bottom));

    if (parentRect.Right != rect.Right) 
        newRects.Add(new Rect(rect.Right, parentRect.Right, parentRect.Top, parentRect.Bottom));

    if (parentRect.Top != rect.Top) 
        newRects.Add(new Rect(rect.Left, rect.Right, parentRect.Top, rect.Top));

    if (parentRect.Bottom != rect.Bottom) 
        newRects.Add(new Rect(rect.Left, rect.Right, rect.Bottom, parentRect.Bottom));

    foreach (Rect newRect in newRects)
    {
        SetRect(newRect);
        Rects.Add(newRect);
    }
}

public void Unclaim(Rect rect)
{
    if (!Rects.TryGetValue(rect, out Rect? targetRect)) 
        throw new Exception("The unclaimed area does not exist");

    if (!targetRect.Claimed) 
        throw new Exception("The target area was not claimed");

    targetRect.Claimed = false;

    while (targetRect is not null) 
        targetRect = TryMerge(targetRect);
}

private void SetRect(Rect rect)
{
    for (int x = 0; x < rect.Width; x++)
    {
        for (int y = 0; y < rect.Height; y++) 
           _matrix[x, y] = rect;
    }
}

private Rect? TryMerge(Rect rect)
{
    Rect left = _matrix[rect.Left - 1, rect.Top];

    if (!left.Claimed && left.Top == rect.Top && left.Bottom == rect.Bottom)
    {
        Rect newRect = new(left.Left, rect.Right, left.Top, rect.Bottom);
        SetRect(newRect);
        Rects.Remove(left);
        Rects.Remove(rect);
        Rects.Add(newRect);

        return newRect;
    }

    Rect right = _matrix[rect.Right + 1, rect.Top];

    if (!right.Claimed && right.Top == rect.Top && right.Bottom == rect.Bottom)
    {
        Rect newRect = new(rect.Left, right.Right, right.Top, rect.Bottom);
        SetRect(newRect);
        Rects.Remove(right);
        Rects.Remove(rect);
        Rects.Add(newRect);

        return newRect;
    }

    Rect top = _matrix[rect.Left, rect.Top - 1];

    if (!top.Claimed && top.Left == rect.Left && top.Right == rect.Right)
    {
        Rect newRect = new(rect.Left, rect.Right, top.Top, rect.Bottom);
        SetRect(newRect);
        Rects.Remove(top);
        Rects.Remove(rect);
        Rects.Add(newRect);

        return newRect;
    }

    Rect bottom = _matrix[rect.Left, rect.Bottom + 1];

    if (!bottom.Claimed && bottom.Left == rect.Left && bottom.Right == rect.Right)
    {
        Rect newRect = new(rect.Left, rect.Right, rect.Top, bottom.Bottom);
        SetRect(newRect);
        Rects.Remove(bottom);
        Rects.Remove(rect);
        Rects.Add(newRect);

        return newRect;
    }

    return null;
}

With a lot of work done when modifying the area, the actual lookup code is rather short. To calculate all positions you would need to iterate the larger rectangles again, but in my application case I can skip this step.

public IEnumerable<Rect> GetRectsOfSizeAndLarger(int minSize) => Rects.SkipWhile(x => x.Area < minSize);
public IEnumerable<Rect> GetRectsOfSizeAndSmaller(int maxSize) => Rects.TakeWhile(x => x.Area <= maxSize);

The biggest issue of this solution is that some positions are still missed. This concerns cases where you could place the target rectangle on two or more unclaimed rectangles at once.

A simple solution would probably be to just check all unclaimed rectangles but that counteracts the goal of the focus on speed.