Algorithm required to determine if a rectangle is completely covered by another set of rectangles

Question

I am searching for an algorithm that will determine if a new rectangle is completely covered by a set of existing rectangles. Another way of putting the question, is does the new rectangle exist completely with the area covered by the existing rectangles?

There seem to be lots of algorithms to determine rectangle overlap and so on, but I can't really find anything that solves this exact problem.

The rectangles will be represented using x, y coordinates. This problem relates to geographical mapping.

Edit - from comment posted by the OP:

The rectangles are aligned on the X/Y axis

Answer 1

here is my code, as you requested:

the first method "subtracts" (returns uncovered parts) of 2 rectangles.

the second method subtracts a list of rectangles from the base rectangle.

in your case list contains existing rectangles, and the new one is base

to check if there is a full intersection the list returned from the second method should have no elements.

public static List<Rectangle> SubtractRectangles(Rectangle baseRect, Rectangle splitterRect)
    {
        List<Rectangle> newRectaglesList = new List<Rectangle>();

        Rectangle intersection = Rectangle.Intersect(baseRect, splitterRect);
        if (!intersection.IsEmpty)
        {
            Rectangle topRect = new Rectangle(baseRect.Left, baseRect.Top, baseRect.Width, (intersection.Top - baseRect.Top));
            Rectangle bottomRect = new Rectangle(baseRect.Left, intersection.Bottom, baseRect.Width, (baseRect.Bottom - intersection.Bottom));

            if ((topRect != intersection) && (topRect.Height != 0))
            {
                newRectaglesList.Add(topRect);
            }

            if ((bottomRect != intersection) && (bottomRect.Height != 0))
            {
                newRectaglesList.Add(bottomRect);
            }
        }
        else
        {
            newRectaglesList.Add(baseRect);
        }

        return newRectaglesList;
    }

    public static List<Rectangle> SubtractRectangles(Rectangle baseRect, List<Rectangle> splitterRectList)
    {
        List<Rectangle> fragmentsList = new List<Rectangle>();
        fragmentsList.Add(baseRect);

        foreach (Rectangle splitter in splitterRectList)
        {
            List<Rectangle> toAddList = new List<Rectangle>();

            foreach (Rectangle fragment in fragmentsList)
            {
                List<Rectangle> newFragmentsList = SubtractRectangles(fragment, splitter);
                toAddList.AddRange(newFragmentsList);
            }

            if (toAddList.Count != 0)
            {
                fragmentsList.Clear();
                fragmentsList.AddRange(toAddList);
            }
        }

        return fragmentsList;
    }

Answer 2

If rectangles are aligned that's easy:

Let's say you have rectangle A0 and want to know if it is fully covered by (B1, B2, B3...) = B

A := (A0)
while P := pop B
  for R in A
    if P fully covers R:
      remove R from A
    else if P and R does overlap:
      remove R from A
      break R in subrentangles S := (S1, S2, S3,...) following the intersections \
                                                     with P edges
      push S into A
if A is empty:
   say B covers A0
else:
   say B does not fully cover A0

Answer 3

If the rectangles all have the same angle; then the following might me more efficient and easier to program:

Determine for every y coordinate which rectangles cover that y coordinate (you only have to do this for y coordinates at which the covering changes;i.e. that correspond to the upper or lower limit of a rectangle). Once you know that, solve the problem for each such y coordinate (i.e. check whether all x values are covered by the rectangles that are "active" for that Y coordinate).

Edit: I think this is O(n^2 log(n)^2) complexity, as two sorts are all the hard work you have to do