使用Python插入，消化和顯示點到四叉樹中

Question

我正在嘗試構建一個點區域quadtree，它使用Python在2D地圖上存儲點。

每個點由其座標(x, z)和一個指向另一個文件中的這個點的數據的指針組成。

在四叉樹，每個專賣店只有一個點，所以

插入點到沒有孩子，沒有點，點剛進入這個區域的區域時

1. ;
2. 當一個地區有孩子時，我們會嘗試將其插入其中一個孩子。
3. 將點插入到沒有子元素但已被點佔據的區域時，該區域被細分爲四個相等的子區域，並將舊點從該區域中取出並放入其中一個子區域。然後，我們嘗試將新的點插入到孩子中。之後我們可以從地圖2D中確定這一點並顯示它。

我試圖實現一個插入功能，刪除和打印，但我沒有成功。有人可以幫我解決這個問題嗎？我在編程方面是一個新手，並且在這個問題上停留了兩天。提前謝謝了！

Answer 1

我也試過，制定本辦法，但因爲我需要的葉子prendrend值（X，Y）這樣的事情不正常工作，確定位置，這裏的類四叉樹（對象）：

def __init__(self, items=[], depth=6, boundingRect=None): 
    # The sub-quadrants are empty to start with. 
    self.nw = self.ne = self.se = self.sw = None 

    # If we've reached the maximum depth then insert all items into this 
    # quadrant. 
    self.depth = depth 
    if self.depth == 0: 
     self.items = items 
     return 

    # Find this quadrant's centre. 
    if boundingRect: 
     l, t, r, b = self.l, self.t, self.r, self.b = boundingRect 
    else: 
     # If there isn't a bounding rect, then calculate it from the items. 
     l = self.l = min(item.rect.left for item in items) 
     t = self.t = min(item.rect.top for item in items) 
     r = self.r = max(item.rect.right for item in items) 
     b = self.b = max(item.rect.bottom for item in items) 
    cx = self.cx = (l + r) * 0.5 
    cy = self.cy = (t + b) * 0.5 

    self.items = [] 
    if not items: 
     return 
    nw_items = [] 
    ne_items = [] 
    se_items = [] 
    sw_items = [] 

    for item in items: 
     # Which of the sub-quadrants does the item overlap? 
     in_nw = item.rect.left <= cx and item.rect.top <= cy 
     in_sw = item.rect.left <= cx and item.rect.bottom >= cy 
     in_ne = item.rect.right >= cx and item.rect.top <= cy 
     in_se = item.rect.right >= cx and item.rect.bottom >= cy 

     # If it overlaps all 4 quadrants then insert it at the current 
     # depth, otherwise append it to a list to be inserted under every 
     # quadrant that it overlaps. 
     if in_nw and in_ne and in_se and in_sw: 
      self.items.append(item) 
     else: 
      if in_nw: nw_items.append(item) 
      if in_ne: ne_items.append(item) 
      if in_se: se_items.append(item) 
      if in_sw: sw_items.append(item) 

    # Create the sub-quadrants, recursively. 
    if nw_items: 
     self.nw = QuadTree(nw_items, self.depth-1, (l, t, cx, cy)) 
    if ne_items: 
     self.ne = QuadTree(ne_items, self.depth-1, (cx, t, r, cy)) 
    if se_items: 
     self.se = QuadTree(se_items, self.depth-1, (cx, cy, r, b)) 
    if sw_items: 
     self.sw = QuadTree(sw_items, self.depth-1, (l, cy, cx, b)) 

def insert(self, item): 
    # If we've reached the maximum depth then insert item in this quadrant. 
    if self.depth == 0: 
     self.items.append(item) 
     return 

    in_nw = item.rect.left <= self.cx and item.rect.top <= self.cy 
    in_sw = item.rect.left <= self.cx and item.rect.bottom >= self.cy 
    in_ne = item.rect.right >= self.cx and item.rect.top <= self.cy 
    in_se = item.rect.right >= self.cx and item.rect.bottom >= self.cy 

    # If it overlaps all 4 quadrants then insert it at the current 
    # depth, otherwise append it to the item list of every quadrant 
    # that it overlaps. 
    if in_nw and in_ne and in_se and in_sw: 
     self.items.append(item) 
    else: 
     if in_nw: 
      if self.nw: 
       self.nw.insert(item) 
      else: 
       self.nw = QuadTree([item], self.depth-1, 
            (self.l, self.t, self.cx, self.cy)) 
     if in_ne: 
      if self.ne: 
       self.ne.insert(item) 
      else: 
       self.ne = QuadTree([item], self.depth-1, 
            (self.cx, self.t, self.r, self.cy)) 
     if in_se: 
      if self.se: 
       self.se.insert(item) 
      else: 
       self.se = QuadTree([item], self.depth-1, 
            (self.cx, self.cy, self.r, self.b)) 
     if in_sw: 
      if self.sw: 
       self.sw.insert(item) 
      else: 
       self.sw = QuadTree([item], self.depth-1, 
            (self.l, self.cy, self.cx, self.b)) 

def remove(self, item): 
    # If we've reached the maximum depth remove the itam from this quadrant. 
    if self.depth == 0: 
     self.items.remove(item) 
     return 

    in_nw = item.rect.left <= self.cx and item.rect.top <= self.cy 
    in_sw = item.rect.left <= self.cx and item.rect.bottom >= self.cy 
    in_ne = item.rect.right >= self.cx and item.rect.top <= self.cy 
    in_se = item.rect.right >= self.cx and item.rect.bottom >= self.cy 

    # If it overlaps all 4 quadrants remove it, otherwise 
    # search the lower quadrants for it 
    if in_nw and in_ne and in_se and in_sw: 
     self.items.remove(item) 
    else: 
     if in_nw and self.nw: 
       self.nw.remove(item) 
     if in_ne and self.ne: 
       self.ne.remove(item) 
     if in_se and self.se: 
       self.se.remove(item) 
     if in_sw and self.sw: 
       self.sw.remove(item) 

class class物品（object）：

def __init__(self, left, top, right, bottom): 
     self.left = left 
     self.top = top 
     self.right = right 
     self.bottom = bottom