SubtractRect doesn’t always give you the exact difference


The Subtract­Rect function takes a source rectangle and subtracts out the portion which intersects a second rectangle, returning the result in a third rectangle. But wait a second, the result of subtracting one rectangle from another need not be another rectangle. It might be an L-shape, or it might be a rectangle with a rectangular hole. How does this map back to a rectangle?

The documentation for Subtract­Rect says that the function performs the subtraction when they "intersect completely in either the x- or y-direction." But I prefer to think of it as the alternate formulation offered in the documentation: "In other words, the resulting rectangle is the bounding box of the geometric difference."

I was reminded of this subject when I saw some code that tried to do rectangle manipulation like this:

// Clip rcA to be completely inside rcB.
RECT rcSub;
// rcSub = the part of rcA that stick out beyond rcB
if (SubtractRect(&rcSub, &rcA, &rcB)) {
    // Remove that part from rcA
    SubtractRect(&rcA, &rcA, &rcSub);
}

If the rectangle rcA extends beyond rcB in more than one direction, then the geometric difference will not be rectangular, and the result of Subtract­Rect will be expanded to the bounding box of the difference, which means that it will return rcA again. And then the second line will subtract it all out, leaving the rectangle empty.

Oops.

What they really wanted was

// Clip rcA to be completely inside rcB.
IntersectRect(&rcA, &rcA, &rcB);
Comments (15)
  1. Adam Rosenfield says:

    Never heard about SubtractRect before.  I feel like if I ever needed that sort of functionality, I'd just code it up myself instead of looking for a library function to do it.

  2. Maurits says:

    Pictures are very helpful when explaining these things:

    msdn.microsoft.com/…/dd162903(v=vs.85).aspx

    This shows IntersectRect and UnionRect, but sadly not SubtractRect.

  3. Maurits says:

    I threw together a toy app which accepts two rectangles on the command line and will union, intersect, or subtract them, then print out the result.

    blogs.msdn.com/…/sample-app-for-rect-functions.aspx

  4. Moris says:

    (UnionRect) I have never really understood how a union of two rects can be stored in a RECT struct.

    Doesn't make sense to me.

    Where is the opposite function of IntersectRect?

    To exclude the intersecting parts.

    [All of the ...Rect functions return the bounding box of the geometric result. And the function that excludes the intersecting part is Subtract­Rect. -Raymond]
  5. Exercise: implement BOOL SymmetricDifferenceRect(RECT *Out, RECT *A, RECT *B).

  6. Silly says:

    Total untested guess here. A frequency analyser and a timer can be used to determine the set of output points. This routine may take a while to run to completion.

    static void Check(LPRECT Out, LPCRECT A, LPCRECT B, LPBOOL emptySet) {

      for(int y = A->top; y < A->bottom; ++y) {

         for(int x = A->left; x < A->right; ++x) {

            if(x < B->left || x > B->right || y < B->top || y > B->bottom) {

               if(*emptySet) {

                  Out->left = Out->right = x;

                  Out->top = Out->bottom = y;

                  *emptySet = FALSE;

               }

               else { // probable redundant checking

                  if(y > Out->bottom) Out->bottom = y;

                  if(x > Out->right) Out->right = x;

                  if(x < Out->left) Out->left = x;

                  if(y < Out->top) Out->top = y;

               }

               Beep(x, y);

            }

         }

      }

    }

    BOOL SymmetricDifferenceRect(LPRECT Out, LPCRECT A, LPCRECT B) {

      BOOL emptySet = TRUE;

      Check(Out, A, B, &emptySet);

      Check(Out, B, A, &emptySet);

      return !emptySet;

    }

  7. Neil says:

    I've subtracted rectangular regions before, which of course does work as expected. I found the way CombineRgn worked confusing though.

  8. Joker_vD says:

    Rectangles are not closed under (set-theoretic) union/substration, so let's redefine those operation to return the "rectangular closure" of the original result! That is, the smallest rectangle that contains the original result. Sure, that works, since rectangles form a bounded semilattice under inclusion relation and intersection (if you account for the finiteness of DWORD, they form a bounded lattice), but such a redefinition should be reflected in the name. Just calling them "union" and "subtraction" is a misnomer.

    Besides, non-distributive (semi)lattices are neither terribly useful nor intuitive.

  9. parkrrrr says:

    (Disclaimer: I think this is true, based on a few sketches, but I haven't bothered to prove it and I'm prepared to be wrong.)

    SymmetricDifferenceRect(A,B) is either SubtractRect(UnionRect(A,B),IntersectRect(A,B)) or UnionRect(SubtractRect(A,B),SubtractRect(B,A)).

    In most cases, that is equivalent to UnionRect(A,B), but this simplification fails when A and B have any three of left/right/top/bottom equal.

  10. Matt says:

    @Silly: If you're using a FOR loop anywhere in your solution to this YOU'RE DOING IT WRONG.

  11. Silly says:

    @Matt. Awww… but then how else could one Beep out all the points? That's the bestest part of my solution :(

  12. Maurits says:

    @Dave_Bacher: needs more jQuery.

  13. dbacher says:

    var f = function(x,y)

    {

      // awesome!

      var g = function(x,y)

      {

        if (y < 20)

         f(x, y+1);

      }

      if (x < 20)

      {

         doSomething();

          x += 1;

          f(x, y);

      }

      else

      {

         g(x, y);

      }

    }

    $(function(){ f(0,0); })

    Satisfied?

  14. Dave Bacher says:

    @Silly:

    void someFunc(x, y)

    {

     x += 1;

     if (19 == x)

     {

         x = 0;

         y += 1;

         if (19 == y)

         {

            return;

         }

     }

     if (someCondition)

        { /* do something */ }

     someFunc(x, y);

    }

  15. Silly says:

    @Dave. Sweet! And with tail recursion too (methinks)! All I got left is:

      y = start_y;

      comefrom B;

      x = start_x;

      comefrom A;

      if (x < end_x) {

        if (whatevs) { stuff(); }

      }

    A: ++x;

    B: if y++ >= end_y return;

Comments are closed.