How can I determine if one rectangle is completely contained inside another?

Question

I have a theoretical grid of overlapping rectangles that might look something like this:

But all I need to work with is a collection of Rectangle objects:

var shapes = new List<Rectangle>(); shapes.Add(new Rectangle(10, 10, 580, 380)); shapes.Add(new Rectangle(15, 20, 555, 100)); shapes.Add(new Rectangle(35, 50, 40, 75)); // ... 

What I would like to do is build a DOM-like structure, where each rectangle has a ChildRectangles property that contains the rectangles that are contained within it in the grid.

The end result should allow me to convert such a structure to XML, something like strings:

 <grid> <shape rectangle="10, 10, 580, 380"> <shape rectangle="5, 10, 555, 100"> <shape rectangle="20, 30, 40, 75"/> </shape> </shape> <shape rectangle="etc..."/> </grid> 

But basically it is the DOM-like structure in memory that I want, the XML output is just an example of how I can use such a structure.

The bit I'm stuck on is how to efficiently determine which rectangles belong.

NOTE No rectangles are partially contained inside another; they are always completely inside another.

EDIT Normally there will be hundreds of rectangles, do you just have to iterate over each rectangle to see if it contains another?

EDIT Someone suggested Contains (not my best moment, missed this!), But I'm not sure how best to build a DOM. For example, take the grandson of the first rectangle, the parent does contain a grandson, but he should not be a direct descendant, he must be a descendant of the parent's first child.

Answer 1

As @BeemerGuy points out, Rect.Contains will tell you if one rectangle contains another. Building a hierarchy is a little more important ...

There is an O (N ^ 2) solution in which for each rectangle you look at a list of other rectangles to see if it fits inside. The "owner" of each rectangle is the smallest rectangle that contains it. Pseudocode:

 foreach (rect in rectangles) { owner = null foreach (possible_owner in rectangles) { if (possible_owner != rect) { if (possible_owner.contains(rect)) { if (owner === null || owner.Contains(possible_owner)) { owner = possible_owner; } } } } // at this point you can record that `owner` contains `rect` } 

It is not very effective, but it can be "fast enough" for your purposes. I'm sure I saw the O (n log n) solution (it's just a sort operation, after all), but it was a bit more complicated.

Answer 2

Use Contains() for a Rectangle .

 Rectangle rect1, rect2; // initialize them if(rect1.Continas(rect2)) { // do... } 

UPDATE :
For future reference ... It is interesting to add that the Rectangle also has IntersectsWith(Rectangle rect) in case you want to check that the rectangle partially collides with another rectangle.

Answer 3

Average solution O (n log n):

Think of your set of rectangles as a tree where the parent nodes “contain” the child nodes — the same as the DOM structure. You will build a tree with a rectangle at a time.

Make a dummy node to serve as the root of your tree. Then, for each of your rectangles ("current_rect"), start with the root children and work down until you find where it goes:

 parent_node = root_node sibling_nodes = [children of parent_node] for this_node in sibling_nodes: if current_rect contains this_node: move this_node: make it a child of current_rect instead of parent_node elseif this_node contains current_rect: parent_node = this_node sibling_nodes = [children of parent_node] restart the "for" loop using new set of sibling_nodes make current_rect a child of parent_node 

The "contains" relationship asks if one rectangle contains another. "Parent", "child" and "sibling" refer to the tree structure.

EDITED . Fixed a bug that would skip some nodes in current_rect.

Answer 4

Make sure that each point in the rectangle is within the borders of the other rectangles. In .NET, the Rectangle class has a .Contains (Point) method. Or you can check the coordinates of the corner point again on the target rectangular .Left, .Right, .Top and .Bottom.

Answer 5

pseudo code:

 for i = 0 to rectangles.length - 2 for j = i + 1 to rectangles.length - 1 if rectangles[i].Contains(rectangles[j]) //code here }}}