Hit testing for a rectangle with holes in it

Question

I have a rectangle of type Rect that defines the outline of some object, and another rectangle of type Rect that represents the selection rectangle that the user has drawn with the mouse to select some objects. The selection process now performs a hit test for every object by calling the following method of each object:

public override bool IntersectsWith(Rect selectionRect)
{
    return this.Rectangle.IntersectsWith(selectionRect);
}

But now my objects also have holes in them. One type of object does not only consist of a rectangle anymore, but has other rectangular holes that shall not be considered for the hit test.

How should my IntersectsWith method look like to perform such a hit test? What geometry classes does WPF offer me here? I know that the Win32 API (or was it Windows Forms?) had something called Region that I could add and cut retangles to/from. The WPF class Polygon looks promising, but it's a complete control which is way too heavy for a simple geometry test.

One simple solution that I can imagine is definitely wrong: I can't just test on the main outline positively and then on all hole rectangles negatively. Because if the selection rectangle is entirely within such one hole, the hit test shall return false. But when the selection rectangle covers both a hole and a non-hole region within the bounding rectangle, the hit test shall return true, even though a hole was touched.

Answer 1

This isn't so hard to do "by hand", i.e. just write your own geometry code rather than using built-in stuff. For example, here's some pseudocode:

function intersectsWith(Shape s, Rectangle rect):
  if not s.outerBoundary.itersectsWidth(rect):
    return false
  for holeRect in s.innerHoles:
    if fullyContains(holeRect, rect):
      return false
  return true

# tests if r1 completely contains r2
function fullyContains(Rectangle r1, Rectangle r2):
  return (r1.x < r2.x && r1.y > r2.y &&
          r1.x + r1.width > r2.x + r2.width &&
          r1.y + r1.height > r2.y + r2.height)