3

我有一个存储为点的矩形列表。目前，数据如下所示：

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. 一位朋友建议使用 r-trees。这有意义吗？
4

2 回答 2

3

使用类。这是面向对象编程的典型用例。创建一个矩形类

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，以及一个孩子列表。找到父子关系的逻辑进入这个类的一个方法（顺便说一句，你的方法有效吗？我改变了它，因为它对我来说是胡说八道。也许我对矩形是如何定义的有不同的理解。）

当您谈论网站<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 有一个孩子（紫罗兰色是绿色的孩子）。

于 2013-01-11T07:11:13.787 回答
0

四叉树或 R 树（或任何其他二维空间数据结构）将非常适合。但是如果你没有很多这样的嵌套框（几十个或几百个），你可以在每次需要查询数据结构时枚举它们。如果您有很多、数千或更多，并且需要有效地查询它们 - 使用空间数据结构。

于 2013-01-11T07:19:42.453 回答