Calculating the area(s) of a rectangle that aren't being overlapped

Question

I've got two rectangles represented by structures that contain the x1, y1, x2, y2 coordinates. One rectangle can be considered the parent, another the child.

I already know how to detect if the child rectangle is within the parent rectangle; what I'm trying to figure out now is the simplest, fastest way to determine the rectangular areas within the parent that are not being overlapped by the child rectangle.

For example, consider a 100x100 parent rectangle, and a 50x50 child rectangle located exactly in the center of the parent. This would mean there would be four rectangles representing the four areas in the parent rectangle that aren't being overlapped by the child.

Of course, the child could be in the top left, top right, bottom left, bottom right corner, or a little to the left, a little to the right, etc... there might be one, two, three, or four rectangles that represent the non-overlapped areas.

I've had some ideas for implementations to figure this out, but all seem overly complex. Is there a simple, fast way to figure this out?

Answer 1

parent = Rectangle.new(x1,y1,mx1,my1)
child = Rectangle.new(x2,y2,mx2,my2)

rects = []
if (parent.contains(child))
  rects.push Rectangle.new(parent.x, parent.y, parent.mx, child.y) if child.y>parent.y
  rects.push Rectangle.new(parent.x, child.my, parent.mx, parent.my) if child.my<parent.my
  rects.push Rectangle.new(parent.x, parent.y, child.x, pareny.my) if child.x>parent.x
  rects.push Rectangle.new(child.mx, parent.y, parent.mx, parent.my) if child.mx<parent.mx
end

Answer 2

This is the basic algorithm:

For each point in the child, if it is inside the parent, the corresponding child and parent point form the diagonal a rectangle. Now, for each side of the child, if the two points are in the parent, those two points and the matching points on the edge of the parent form a rectangle. If only one of the points on the edge of the child is in the parent, this point and the parent point corresponding to the child edge point not in the parent form the diagonal for a rectangle. Return these rectangles.

You would get a maximum of eight rectangles (one for each corner, one for each edge). If you want the minimum possible rectangles, see if they share edges, and if they do, combine them.

Answer 3

So there could be up to 4 rectangles of non-overlapped area. Let's make a list of them.

leftrect = rightrect = toprect = bottomrect = None
trimmedparent = duplicate(parent)

if parent.x1 < child.x1:
    leftrect = duplicate(parent)
    leftrect.x2 = child.x1
    trimmedparent.x1 = child.x1

if parent.x2 > child.x2:
    rightrect = duplicate(parent)
    rightrect.x1 = child.x2
    trimmedparent.x2 = child.x2

if parent.y1 < child.y1:
    toprect = duplicate(trimmedparent)
    toprect.y2 = child.y1

if parent.y2 > child.y2:
    bottomrect = duplicate(trimmedparent)
    bottomrect.y1 = child.y2

The only tricky part is eliminating the part where e.g leftrect and toprect might intersect. I used 'trimmedparent' as an intermediate step to trim that section from toprect.

Answer 4

Here's another way to calculate the non-overlapped area of the parent:

Function max(ByVal v1 As Double, ByVal v2 As Double) As Double
    If v1 > v2 Then
        Return v1
    Else
        Return v2
    End If
End Function

Function min(ByVal v1 As Double, ByVal v2 As Double) As Double
    If v1 > v2 Then
        Return v2
    Else
        Return v1
    End If
End Function

Function IntervalOverLap(ByVal p1 As Double, ByVal p2 As Double, ByVal c1 As Double, ByVal c2 As Double) As Double
    'determine how much of the parent(p1 to p2) segment '
    ' is overlapped by the child(c1 to c2) segment      '

    'sort to standard direction  '
    Dim ph As Double = max(p1, p2)
    Dim pl As Double = min(p1, p2)
    Dim ch As Double = max(c1, c2)
    Dim cl As Double = min(c1, c2)

    'restrict the child to within the parent '
    ch = min(ph, max(pl, ch))
    cl = max(pl, min(cl, ph))

    'return the overlapped length  '
    Return (ch - cl)
End Function

Function NonOverLappedArea(ByVal parent As Rectangle, ByVal child As Rectangle) As Double
    'return the area of the parent        '
    ' that is not overlapped by the child '
    Return IntervalOverLap(parent.X1, parent.X2, child.X1, child.X2) _
        * IntervalOverLap(parent.Y1, parent.Y2, child.Y1, child.Y2)
End Function

Answer 5

From your description, the child is always wholly contained by the parent. So the non-overlapping area is always going to be a rectangular donut, although it could be degenerate on any of the 4 sides since, a child edge could abut a parent edge, the fully degenerate case being the child is the same as the parent.

The donut can be decomposed into 4 rectangles. The decomposition may not be unique, meaning you could get different rectangles depending on how you perform the decomposition. Of the 4 rectangles, discard the degenerate ones (those with 0 area) and you're done.

Here's a vertically biased decomposition

// assume the child is known to be in the parent bounds at this point
// assume parent and child are normalized
std::vector<CRect> rects;
CRect rect( parent.x1(), parent.y1(), child.x1(), parent.y2() ); // left
if ( rect.area() > 0.0 ) rects.push_back(rect);
rect.set( child.x1(), parent.y1(), child.x2(), child.y1() ); // bottom
if ( rect.area() > 0.0 ) rects.push_back(rect);
rect.set( child.x1(), child.y2(), child.x2(), parent.y2() ) ); // top
if ( rect.area() > 0.0 ) rects.push_back(rect);
rect.set( child.x2(), parent.y1(), parent.x2(), parent.y2() ) ); // right
if ( rect.area() > 0.0 ) rects.push_back(rect);

// yes, this could be written without all the code replication... :)