How can i extract rectangles from a rectangle intersection.

Question

Having a rectangle (A) and intersecting it with another rectangle (B), how could I extract the other rectangles created through that intersection (C,D,E & F)?

AAAAAAAAAAAAAA    CCCFFFFDDDDDDD
AAABBBBAAAAAAA    CCCBBBBDDDDDDD
AAABBBBAAAAAAA -> CCCBBBBDDDDDDD
AAAAAAAAAAAAAA    CCCEEEEDDDDDDD
AAAAAAAAAAAAAA    CCCEEEEDDDDDDD

And could this be extended to extract rectangles from several intersections, such as this example which intersects A with B & C and extracts D, E, F & G?

BBBBAAAAAAAAAA    BBBBDDDDDDDDDD
BBBBAAAAAAAAAA    BBBBDDDDDDDDDD
AAAAAACCCCCAAA -> EEEEEECCCCCFFF
AAAAAACCCCCAAA    EEEEEECCCCCFFF
AAAAAAAAAAAAAA    EEEEEEGGGGGFFF

Answer 1

If the answer to TJB's question is yes, then they are:

(left, top, right, bottom) notation

C = (A.left, A.top, B.left, A.bottom)

D = (B.right, A.top, A.right, A.bottom)

E = (B.left, B.bottom, B.right, A.bottom)

E = (B.left, A.top, B.right, B.top)

Answer 2

Assuming B is completely Contained in A, it would be something like:

Rectangle[] GetSurrounding( Rectangle outer, Rectangle inner )
{
   Rectangle left, top, right, bottom; // Initialize all of these...
   left = new Rectangle( outer.Left, outer.Top, outer.Height, inner.Left - outer.Left );
   top  = new Rectangle( inner.Left, outer.Top, inner.Top - outer.Top, inner.Width );
   // So on and so forth...

   return new Rectangle[]{ left, top, right, bottom };
}

//  This assumes:
Rectangle( x , y , height, width ); // Constructor

Also, deciding weather you stretch the left and right rectangles the full height or the top and bottom rectangles the full width is arbitrary, and will either need to be a constant decision or a parameter to the method. Other cases where the rectangles only partially overlap will require more logic looking at the MAX/MIN of values to check for going out of bounds etc.

Answer 3

If A completly contains B:

Rectange C = new Rectangle(A.X,A.Y,B.X-A.X,A.Height);
Rectange D = new Rectangle(B.Right,A.Y,A.Right-B.Right,A.Height);
Rectange E = new Rectangle(B.X,B.Bottom,B.Width,A.Bottom-A.Bottom);
Rectange F = new Rectangle(B.X,A.Y,B.Width,B.Y-A.Y);

this is .NET, I'm not sure about the language of your code, but I think most of the structures look simular in different languages, in .NET the constructor of a System.Drawing.Rectangle is (X,Y,Width,Height)

Answer 4

for more arbitrary shapes a scanline algorithm would work. you will get different results depending on whether you scan horizontally or vertically (your example matches a vertical scan)

essentially you scan along each column or row and break it into intervals between each shape, intervals on the next column or row with the same start and end can be merged.

Answer 5

for all rectangles A
   for all corners C of A
      for all other rectangles B
         if C is inside B
            for all corners D of B
               if D is inside A
                  got rectangle C-D
               endif
            endfor
         endif
      endfor
   endfor
endfor

Answer 6

Given a large rectangle with any number of smaller rectangles punched out of it, you can use a greedy algorithm to break up the remaining area of the large rectangle into smaller rectangles.

• Pick the leftmost, uppermost point that hasn't been covered yet.
• Start a rectangle there.
• Extend it downwards as far as it can go.
• Then extend it rightwards as far as it can go.
• Add that rectangle to your collection and repeat.

This is not guaranteed to produce the minimum number of rectangles.

The first step is the most complicated one. If you don't mind a little randomness, an easier thing to do would be to pick random points until you find one that isn't covered yet; then go left until you hit an edge; then go up until you hit an edge.