Data structure(s) for storing nested boxes?

Question

I have a list of rectangles stored as points. Currently, the data looks something like this:

boxes = [{'p1': (0,0), 'p2': (100,20)},
         {'p1': (5,5), 'p2': (15,15)}, 
         {'p1': (20,5), 'p2': (30,15)},
         {'p1': (35,5), 'p2': (45,15)},
         {'p1': (70,5), 'p2': (80,15)}]

I also have a basic function that tests if a rectangle is contained within another:

def isChild(b1,b2):
    return (b1 != b2 and 
            (b1['p2'][0]-b1['p1'][0] * b1['p2'][1]-b1['p1'][1]) > (b2['p2'][0]-b2['p1'][0] * b2['p2'][1]-b2['p1'][1]) and
            b1['p1'][0] < b2['p2'][0] and 
            b1['p2'][0] > b2['p1'][0] and 
            b1['p1'][1] < b2['p2'][1] and 
            b1['p2'][1] > b2['p1'][1])

I'd like to wind up with a set of rectangles and their children, but I'm not sure how I should store them. I'm thinking something like this:

[{'p1': (0,0), 
  'p2': (100,20),
  'children': [{'p1': (5,5), 'p2': (15,15)}, 
               {'p1': (20,5), 'p2': (30,15)},
               {'p1': (35,5), 'p2': (45,15)},
               {'p1': (70,5), 'p2': (80,15)}]}]

The context of this is that the boxes represent elements on a web page. The data structure is meant to generate the basic markup, so the structure above would wind up being something like this:

<div>
    <div></div>
    <div></div>
    <div></div>
    <div></div>
</div>

1. Are the source/goal data structures a good fit for this? If not, what is?
2. How can I get from the source to the goal?
3. A friend suggested using r-trees. Would that make sense here?

Answer 1

Use classes. This is a typical usecase for OO programming. Create a class Rectangle

from random import random

class Rectangle(object):
    def __init__(self, x1, y1, x2, y2):
        self._p1 = (x1, y1)
        self._p2 = (x2,y2)
        self._children = []

    def __str__(self):
        return "Rectangle defined by %s, %s, %i children" % (self._p1, self._p2, len(self._children))

    def is_child_of(self, other):
        return (self is not other and 
            self._p1[0] > other._p1[0] and 
            self._p2[0] < other._p2[0] and 
            self._p1[1] > other._p1[1] and 
            self._p2[1] < other._p2[1])

    def add_child(self, other):
        self._children.append(other)

    def check_relation_and_connect(self, other):
        if self.is_child_of(other):
            other.add_child(self)
        elif other.is_child_of(self):
            self.add_child(other)


if __name__=="__main__":
    rectangles = [Rectangle(random()*5, random()*5, random()*5+5, random()*5+5) for i in range(10)]

    for i in range(len(rectangles)):
        for j in range(i):
            rectangles[i].check_relation_and_connect(rectangles[j])

    for rectangle in rectangles:
        print rectangle

The class consist of two points, _p1 and _p2, and a list of children. The logic of finding parent-child relation goes into a method of this class (btw, does your method work? I changed it, as it returned nonsense for me. Maybe I have a different understanding of how the rectangle is defined.)

As you're talking about websites and <div>, I assume you won't have thousands of rectangles. So this approach should be fine.

This example can also be extended to plot all rectangles, so one can check the rectangles and the calculated kinship. Keeping class Rectangle unchanged, one can write:

if __name__=="__main__":
    import matplotlib.pyplot as plt
    from matplotlib import patches

    rectangles = [Rectangle(random()*5, random()*5, random()*5+5, random()*5+5) for i in range(5)]

    for i in range(len(rectangles)):
        for j in range(i):
            rectangles[i].check_relation_and_connect(rectangles[j])

    for rectangle in rectangles:
        print rectangle

    colormap = plt.get_cmap("Paired")
    for i, rect in enumerate(rectangles):
        ax = plt.axes()
        color = colormap((1.*i)/len(rectangles))
        patch = patches.Rectangle(rect.p1, rect.p2[0]-rect.p1[0], rect.p2[1]-rect.p1[1], fc="none", ec=color, lw=2)
        ax.add_patch(patch)
    plt.xlim(-1,11)
    plt.ylim(-1,11)
    plt.show()

This gives a plot like:

For this example, exactly one Rectangle had a child (violet is a child of green).

Answer 2

Quad tree or R-tree (or any other 2-dim spatial data-structure) will be a good fit for that. But if you don't have many of this nested boxes(tens or hundreds), you can just enumerate them each time you need to query your data-structure. If you have many, thousands or more, and need to query them efficiently - use spatial data-structure.