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

Aggressor

Are all rectangles aligned or might there be rectangles rotated by 45 degrees? – Lantz

Is the angle of the rectangles with respect to the coordinate system the same for all rectangles? – Ganymede

Necroing this because it was referenced by a new question. @Twibbles: When you get a chance, it would be good to accept the answer you used (salva's answer). – Worl

Answer 1

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

Erinnerinna

Thanks very much folks. Let me review the solutions that you have proposed. The rectangles are aligned on the X/Y axis by the way. – Aggressor

Answer 2

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

Ganymede

Answer 3

I have done something similar in the past. the idea was to compare the new rectangle with each of the existing (one by one)

if there is an intersection discard it (the intersected part), and add uncovered segments to a rectangle array

next, search for intersection between the new segments, and other existing (still unchecked) rectangles.

do the algorithm recursively discarding the intersections, and leaving only the uncovered parts.

in the end, if there is no rectangles in the array, you have a complete overlap

if there are still some rectangles in the array, the overlapping is not full as there are still some parts left.

hope this helps

I can try to find my code if this is what you are looking for. I think its in C#

another idea is to convert all existing rectangles into a polygon, and then check if new rectangle is inside the polygon, but I would not recommend this if you aren't using a language (or framework) which knows how to work with polygons.

Wareing

Hey, thanks. That sounds like it would certainly work. I'd love to see the code and C Sharp would be ideal. Much appreciated. – Aggressor

Answer 4

R-tree may be useful. if there might be rotated rectangles, you can enclose them in bounding rectangles.

Staal

Answer 5

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

Wareing

Answer 6

Try this

Source Rectangle : X0, Y0, breadth, height

// Basically comparing the edges

if(((X0 >= xi) && (X0+breadth <= Xi)) && ((Y0 >= Yi)&&(Y0+height <= Yi)) { //consider the rectangle } else { // discard }

Petepetechia

Answer 7

You can use the algorithm which is used to calculate the union area of rectangles. As you want to check whether rectangle a is covered by rectangles B={b_1, b_2, ..., }.

First you calculate the union area of rectangles in B, we get area_1 as the value.

Then you calculate the union area of rectangles in B+ {a}, we get area_2 as the value.
So if area_1 == area_2, then you are sure that rectangle a is covered by rectangles B. Otherwise, the answer is false.

So the main problem is how to calculate union area of rectangles. This problem can be solved by existing excellent algorithm. This algorithm can be brief introduced as first to discretize value of points of rectangles, and then using Segmentation Tree to accelerate calculation of areas of each block.

Fabian