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

これのコンテキストは、ボックスがWebページ上の要素を表すということです。データ構造は基本的なマークアップを生成することを目的としているため、上記の構造は次のようになります。

<div>
    <div></div>
    <div></div>
    <div></div>
    <div></div>
</div>
  1. ソース/ゴールのデータ構造はこれに適していますか？そうでない場合は、何ですか？
  2. ソースからゴールに到達するにはどうすればよいですか？
  3. 友人がr-treeの使用を提案しました。それはここで意味がありますか？
4

2 に答える 2

3

クラスを使用します。これは、オブジェクト指向プログラミングの典型的なユースケースです。クラス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の2つのポイントと、子のリストで構成されます。親子関係を見つけるロジックは、このクラスのメソッドに入ります（ところで、あなたのメソッドは機能しますか？意味がないので変更しました。長方形がどのように定義されているかについて、別の理解があるかもしれません）。

あなたがウェブサイトとについて話しているように<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()

これにより、次のようなプロットが得られます。 ここに画像の説明を入力してください

この例では、ちょうど1つの長方形に子がありました（紫は緑の子です）。

于 2013-01-11T07:11:13.787 に答える
0

クワッドツリーまたはRツリー（または他の2次元空間データ構造）がそれに適しています。ただし、このネストされたボックスの数が少ない場合（数十または数百）は、データ構造をクエリする必要があるたびにそれらを列挙することができます。数千以上あり、それらを効率的にクエリする必要がある場合は、空間データ構造を使用してください。

于 2013-01-11T07:19:42.453 に答える