提问者:小点点

使用Python将点插入四叉树时超过了最大递归深度(正在寻找bug)


我试图建立一个点区域四叉树存储点在二维地图上与Python,但当我试图插入两个点这是接近(不太接近)彼此,我遇到一个错误: RuntimeError:最大递归深度超过在cmp.我试图提高最大递归数到10000,但不起作用。所以我想有什么问题在我的代码。有人能帮我这个好吗?我是一个新人在编程,已经被困在这两天。BTW,如果你发现任何代码写得不“专业”我真的很感激,如果你能教我如何写在适当的方式。提前非常感谢!

每个点由它的坐标(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)

共1个答案

匿名用户

    h = (x1 - x0)/2

如果使用Python2.7,并且x1和x0都是整数,则此除法的结果将被截断为最接近的整数。例如,如果x1为1,x0为0,则可能期望它们的中点为0.5。但是(1-0)/2等于0。这会导致sub分中的问题,其中四个子rect中的三个将非常小,而第四个将与父rect相同大小。尝试强制执行浮点除法。

    h = (x1 - x0)/2.0