python - 用于存储嵌套框的数据结构？

Question

我有一个存储为点的矩形列表。目前，数据看起来像这样:

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)}]

我还有一个基本函数可以测试一个矩形是否包含在另一个矩形中:

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])

我想以一组矩形及其子项结束，但我不确定应该如何存储它们。我在想这样的事情:

[{'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)}]}]

上下文是方框代表网页上的元素。数据结构旨在生成基本标记，因此上面的结构最终会是这样的:

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

1. 源/目标数据结构是否适合这个？如果不是，那是什么？
2. 我怎样才能从源头到目标？
3. 一位 friend 建议使用 r-trees。这在这里有意义吗？

Answer 1

使用类。这是 OO 编程的典型用例。创建类 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

该类由两个点组成，_p1 和 _p2，以及一个 child 列表。查找父子关系的逻辑进入了这个类的一个方法(顺便说一句，你的方法有效吗？我改变了它，因为它对我来说是废话。可能我对矩形的定义有不同的理解。)

当您谈论网站和 <div> ，我假设您不会有数千个矩形。所以这个方法应该没问题。

此示例还可以扩展为绘制所有矩形，因此可以检查矩形和计算出的亲缘关系。保持类 Rectangle 不变，可以这样写:

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()

这给出了一个像这样的情节:

对于这个例子，恰好有一个 Rectangle 有一个 child (紫色是绿色的 child )。