用於存儲嵌套框的數據結構？

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. 一位朋友建議使用r-trees。這有意義嗎？

Answer 1

使用類。這是面向對象編程的典型用例。創建一個類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，和孩子的名單。找到父子關係的邏輯進入了這個類的一個方法（順便說一下，你的方法是否工作？我改變了它，因爲它對我來說是無意義的，也許我對如何定義矩形有不同的理解。）

正如你在談論網站和<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() 

這給像一個情節：

在這個例子中，只有一個矩形有一個孩子（紫色是綠色的孩子）。

Answer 2

四叉樹或R樹（或任何其他2-dim空間數據結構）將非常適合這種情況。但是如果你沒有很多嵌套的盒子（幾十或幾百個），你可以在每次需要查詢數據結構時枚舉它們。如果您有很多，數千甚至更多，並且需要高效查詢它們 - 請使用空間數據結構。