Algorithm to compute the difference between a set of rectangles and a single rectangle

Question

Let's say I have a red rectangle with coordinates (x,y), (x1,y), (x1,y1), (x,y1) which is overlapped by an undefined number of different blue rectangles (which may have different width and/or height) and are randomly positioned on a surface (they might even not overlap the red rectangle at all). Anyway, something like this:

I have the blue rectangles stored in an array of rectangles and I have the coordinates of each blue rectangle too.

Now, what I need to do is select the parts of the red rectangle which are not overlapped by any of the blue rectangles of the rectangles array (basically I need to do a difference between the union of all the blue rectangles and the red rectangle). In the previous example, these parts would be (delimited by a black border):

And also, I need to compute new rectangles from these parts and the result as an array. Therefore, the previous parts should became the following rectangles:

Or the following rectangles (it doesn't really matter how they are generated, of course as few as possible will be better (but looking at the following image I guess that there can't be less than n rectangles given the parts of it, they will always be n, where n = 13 in this case (correct me if I am wrong))):

After that, I should return an array containing these rectangles created from the parts of the red rectangle.

So the requirements are:

If there aren't blue rectangles that overlap the red rectangle, return an array containing the red rectangle;
If there are blue rectangles that overlap the red rectangle, compute the difference, get the parts which are not overlapped by any of the blue rectangles and given these parts, divide each part so that each part is formed by one or more rectangles, place all the found rectangles in an array and return this array.

Please note that we are not on a web page-like surface, meaning that x < x1 like on the web (left < right), but y > y1 (whereas on the web top < bottom), therefore I have the following Rectangle data structure (pseudo code) which has an overlaps() method:

class Rectangle {
    this.x,
    this.x1,
    this.y,
    this.y1;

    /**
    * @constructor
    */
    Rectangle(x, y, x1, y1) {
        this.x = x;
        this.y = y;
        this.x1 = x1;
        this.y1 = y1;
    }

    /**
    * Tests whether this rectangle overlaps or is overlapped by the rectangle given as parameter.
    * 
    * @returns True if the rectangle is overlapped or overlaps the rectangle given as parameter, false otherwise.
    */
    Boolean overlaps(Rectangle rect) {
       compareX = function(coordX1, coordX2) {
          less = coordX1[0] > coordX2[0] ? coordX2: coordX1;
          greater = coordX1[0] > coordX2[0] ? coordX1: coordX2;
          return less[1] > greater[0] || less[0] == greater[0];

       }

       compareY = function(coordY1, coordY2) {
          less = coordY1[0] > coordY2[0] ? coordY2 : coordY1;           
          greater = coordY1[0] > coordY2[0] ? coordY1 : coordY2;
          return greater[1] < less[0] || greater[0] == less[0];
       }

       coordX1 = [this.x, this.x1]; // [] brackets create a new array
       coordX2 = [rect.x, rect.x1];
       coordY1 = [this.y, this.y1];
       coordY2 = [rect.y, rect.y1]
       return compareX(coordX1, coord) && compareY(coordY1, coordY2);
    } 
}

Now, what is an efficient way to compute the rectangles of the difference? (e.g. a differenceRectangles function)

    //...
    blueRectangles = [ blueRect1, blueRect2, blueRect3, ... ] // This is an array of blue rectangles, I don't know how many there are, but each item of the array is a `Rectangle` data structure with an `overlaps()` method
    redRectangle = new Rectangle(x, x1, y, y1);

    differenceRectangles = differenceRectangles(blueRectangles, redRectangle);

M Oehm M Oehm · Accepted Answer · 2015-10-24T12:54:54

Create condensed axes that contain only the relevant coordinates. For example the x axis should contain the x and x1 of the outer rectangle plus all x and x1 of all rectangles that lie in the big rectangle. Duplicate coordinates are merged.

You now have a grid of possible rectangles:

In this example, you get a 6×5 grid.

Iterate over all rectangles and mark the grid cells that they occupy as "holes". This can be done efficiently if the axes are sorted and if there is a dictionary to look up grid indices by coordinate. You get:

Now combine the remaining rectangles. You could, foe example, join horizontally adjacent rectangles:

There is room for improvement. It might be good to use one big rectangle for the big red area in the bottom right. But as a first draft, this should work.

Algorithm to compute the difference between a set of rectangles and a single rectangle

1 Answers