使用Python將點插入四叉樹時超出最大遞歸深度

Question

我試圖建立一個點區域四叉樹，它在Python地圖上存儲二維地圖上的點，但是當我嘗試插入兩點時彼此接近（不太接近），我遇到了一個錯誤：RuntimeError：在cmp中超出最大遞歸深度。我試圖將最大遞歸數提高到10000，但不起作用。所以我想我的代碼有問題。有人可以幫我解決這個問題嗎？我在編程方面是一名新手，並且在這個問題上已經停留了兩天。順便說一句，如果你發現任何代碼不是「專業的」，我會非常感激，如果你能教我如何以適當的方式編寫它們。提前謝謝了！

每個點由它的座標（x，z）和一個指向另一個文件中該點數據的指針組成。在四叉樹中，每個點只存儲一個點，所以a）當插入一個點到沒有孩子和沒有點的區域時，點就進入這個區域; b）當一個地區有孩子的時候，我們試圖把這個觀點插入其中一個孩子。 c）當把一個點插入沒有孩子但已經被一個點佔據的區域時，該區域被細分爲四個相等的子區域，並且將舊點從該區域中取出並放入其中一個子區域。然後，我們嘗試將新的點插入到孩子中。

class point(): 
    def __init__(self,x,z,pointer): 
     self.x = x 
     self.z = z 
     self.pointer = pointer 


class Node(): 
    #_______________________________________________________ 
    # In the case of a root node "parent" will be None. The 
    # "rect" lists the minx,minz,maxx,maxz of the rectangle 
    # represented by the node. 
    def __init__(self, parent, rect): 
     self.parent = parent 
     self.children = None 
     self.point = None 
     self.leaf = 0 # node is a leaf(=1) if it contains a point 

     if parent == None: 
      self.depth = 0 
     else: 
      self.depth = parent.depth + 1 
     self.rect = rect 
     x0,z0,x1,z1 = rect 


    #_______________________________________________________ 
    # Subdivides a rectangle. Division occurs 
    def subdivide(self): 
     self.point = None 
     self.leaf = 0 
     self.children = [None,None,None,None] 
     x0,z0,x1,z1 = self.rect 
     h = (x1 - x0)/2 
     rects = [] 
     rects.append((x0, z0, x0 + h, z0 + h)) 
     rects.append((x0, z0 + h, x0 + h, z1)) 
     rects.append((x0 + h, z0 + h, x1, z1)) 
     rects.append((x0 + h, z0, x1, z0 + h)) 
     for n in xrange(len(rects)): 
      self.children[n] = Node(self,rects[n]) 

    #_______________________________________________________ 
    # A utility proc that returns True if the coordinates of 
    # a point are within the bounding box of the node. 
    def contains(self, x, z): 
     x0,z0,x1,z1 = self.rect 
     if x >= x0 and x <= x1 and z >= z0 and z <= z1: 
      return True 
     return False 



    def insert(self, p): 
     if self.contains(p.x, p.z) == False: 
      return 
     if self.children == None: 
      if self.leaf == 1: 
       temp_point = copy.copy(self.point) 
       self.subdivide() 
       self.insert(temp_point) 
       self.insert(p) 
      else: 
       self.point = p 
       self.leaf = 1 
     else: 
      for child in self.children: 
       child.insert(p) 

Answer 1

h = (x1 - x0)/2 

如果你正在使用Python 2.7，如果X1和X0這裏都是整數，這種劃分的結果將被截斷到最接近的整數。例如，如果x1是1並且x0是0，那麼您可能預期它們的中點爲0.5。但是(1-0)/2等於0.這導致subdivide中的一個問題，其中四個兒童教會中的三個將無限小，而第四個兒童教會的尺寸與父節點的大小相同。嘗試執行浮點除法。

h = (x1 - x0)/2.0