Python QuadTree

Question

我向QuadTree添加了两个对象，但是当我查看整个列表中的对象时，我只能找到一个对象。这是为什么，我能做些什么来解决这个问题？

from pygame import draw

class QuadTree(object):
    def __init__(self, box, current_level, max_level=3):# box (top_left_x, top_left_y, size_x, size_y)
        self.location = (box[0], box[1])
        self.size = (box[2], box[3])
        self.current_level = current_level
        self.max_level = max_level

        self.objects = []
        self.__setupchirldren__()

    def __setupchirldren__(self):
        self.top_right =        None
        self.top_left =         None
        self.bottom_right =     None
        self.bottom_left =      None

    def elements(self):
        if self.current_level == self.max_level:
            for x in self.objects:
                print x, x.rect
        else:
            if self.bottom_left != None:
                self.bottom_left.elements()
            if self.bottom_right != None:
                self.bottom_right.elements()
            if self.top_left != None:
                self.top_left.elements()
            if self.top_right != None:
                self.top_right.elements()

    def add_object(self, new_object, rect):
        if self.current_level == self.max_level:
            #print new_object, rect
            self.objects.append(new_object)
            #print self.objects
        else:
            half_size = (self.size[0]/2, self.size[1]/2)
            if rect.colliderect(self.location, half_size):
                self.top_left =         QuadTree((self.location[0], self.location[1], half_size[0], half_size[1]), self.current_level+1, self.max_level)
                self.top_left.add_object(new_object, rect)
            if rect.colliderect((self.location[0]+half_size[0], self.location[1]), half_size):
                self.top_right =        QuadTree((self.location[0]+half_size[0], self.location[1], half_size[0], half_size[1]), self.current_level+1, self.max_level)
                self.top_right.add_object(new_object, rect)
            if rect.colliderect((self.location[0], self.location[1]+half_size[1]), half_size):
                self.bottom_left =      QuadTree((self.location[0], self.location[1]+half_size[1], half_size[0], half_size[1]), self.current_level+1, self.max_level)
                self.bottom_left.add_object(new_object, rect)
            if rect.colliderect((self.location[0]+half_size[0], self.location[1]+half_size[1]), half_size):
                self.bottom_right =     QuadTree((self.location[0]+half_size[0], self.location[1]+half_size[1], half_size[0], half_size[1] ), self.current_level+1, self.max_level)
                self.bottom_right.add_object(new_object, rect)

    def draw(self, screen):
        #if self.current_level == self.max_level:
        draw.line(screen, (255, 0, 0), self.location, (self.location[0]+self.size[0], self.location[1]))
        draw.line(screen, (255, 0, 0), self.location, (self.location[0], self.location[1]+self.size[1]))
        draw.line(screen, (255, 0, 0), (self.location[0]+self.size[0], self.location[1]+self.size[1]), (self.location[0]+self.size[0], self.location[1]))
        draw.line(screen, (255, 0, 0), (self.location[0]+self.size[0], self.location[1]+self.size[1]), (self.location[0], self.location[1]+self.size[1]))
        if self.current_level != self.max_level:
            if self.bottom_left != None:
                self.bottom_left.draw(screen)
            if self.bottom_right != None:
                self.bottom_right.draw(screen)
            if self.top_left != None:
                self.top_left.draw(screen)
            if self.top_right != None:
                self.top_right.draw(screen)

    def get_elements(self, rect):
        #ret = self.objects
        if self.current_level == self.max_level:
            #print self.objects
            return self.objects
        else:
            half_size = (self.size[0]/2, self.size[1]/2)
            if self.top_left!= None and rect.colliderect((self.location, half_size)):
                return self.top_left.get_elements(rect)
                #for x in self.top_left.get_elements(rect):
                #   ret.append(x)
            if self.top_right!= None and rect.colliderect(((self.location[0]+self.size[0]/2, self.location[1]), half_size)):
                return self.top_right.get_elements(rect)
                #for x in self.top_right.get_elements(rect):
                #   ret.append(x)
            if self.bottom_left!= None and rect.colliderect(((self.location[0], self.location[1]+self.size[1]/2), half_size)):
                return self.bottom_left.get_elements(rect)
                #for x in self.bottom_left.get_elements(rect):
                #   ret.append(x)
            if self.bottom_right!= None and rect.colliderect(((self.location[0]+self.size[0]/2, self.location[1]+self.size[1]/2), half_size)):
                return self.bottom_right.get_elements(rect)
                #for x in self.bottom_right.get_elements(rect):
                #   ret.append(x)
            #print ret
        return []

当我插入对象时，它打印出来。

platform.Platforms对象0x0236F950 platform.Platforms对象0x0236FAB0 platform.Platforms对象0x0236FAB0

这很好，我希望在可变树中有两个不同的对象，但是当我称之为它时，列表中只有第二个对象。

所以我做了一个功能

def elements(self):
    if self.current_level == self.max_level:
        for x in self.objects:
            print x, x.rect
    else:
        if self.bottom_left != None:
            self.bottom_left.elements()
        if self.bottom_right != None:
            self.bottom_right.elements()
        if self.top_left != None:
            self.top_left.elements()
        if self.top_right != None:
            self.top_right.elements()

打印出来

platform.Platforms object at 0x02320A70 (350,630,110,110) platform.Platforms对象0x02320A70 (350,630,110,110) platform.Platforms object 0x02320A70 (350,630,110,110) platform.Platforms object 0x0232070 rect(350,630,110,110)

Answer 1

您的add_object类每次都会生成一个新的低级四叉树，即使已经有一个。

我本来打算在前面的四叉树问题(非常肯定是您)中提出这一点，但是在我有机会之前，您已经删除了它:如果quadtree类有一个方法来查找或创建给定位置的适当子树(在add_objects和get_elements中都称为rect )，那么情况可能会更好。请注意，这假设每个对象都存在于一个子树中，这对于点是正确的，但对于任意矩形则不是这样。(最明显的情况是，一个很大的矩形--一个覆盖整个字段的矩形--占据任意四叉树的所有四个子树。)

例如，假设get_elements中的逻辑基本正确，您可能定义如下：

def find_or_create(self, rect, create = False):
    "find or create the sub-tree that contains the given point"
    if self.current_level == self.max_level:
        return self # we contain it
    half_size = (self.size[0]/2, self.size[1]/2)
    if rect.collide_rect((self.location, half_size)):
        name = 'top_left'
        location = self.location
    else if rect.collide_rect(...):
        name = 'top_right'
        location = ... # top right location
    else ... [as before, each time setting name and location]
    # now, after deciding which sub-quadrant applies...
    quad = getattr(self, name)
    # if the sub-quadrant already exists, recurse
    if quad:
        return quad.find_or_create(rect, create)
    # otherwise, if we are supposed to create it, do that
    if create:
        quad = QuadTree(...) # this is why you also have to compute "location"
        setattr(self, name, quad)
    return quad # return the new quadtree, or None, as appropriate

这为您提供了一种查找包含四叉树的方法(如果不存在，则不返回任何)，或者，对于添加对象，可以创建它(返回现有的最大四叉树，或者在适当的象限中创建新的最大四叉树)。

getattr和setattr操作允许您使用计算出来的name来获取和设置self.top_left、self.top_right等。

然后添加一个对象就很简单了：

    quad = self.find_or_create(rect, True)
    quad.objects.append(new_object)

还有一个更好的方法来处理位置计算和测试，但我把它作为练习。(当然，如果rects可以跨越多个子树--如果它们不是点--则需要计算所有适当子树的列表，而不是单个适当的左上角/右上/左下/右下/下右子树。)