Python 四叉树

Question

很难说出这里问的是什么。这个问题是含糊的、模糊的、不完整的、过于宽泛的或修辞性的，无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开它， visit the help center 。

已关闭 11 年前。

我向四叉树添加了 2 个对象，但是当我查看整个对象列表时，我只能找到 1 个对象。这是为什么？我可以做什么来解决它？

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 object at 0x0236F950 platform.Platforms object at 0x0236F950 platform.Platforms object at 0x0236F950 platform.Platforms object at 0x0236F950 platform.Platforms object at 0x0236FAB0 platform.Platforms object at 0x0236FAB0 platform.Platforms object at 0x0236FAB0 platform.Platforms object at 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 rect(350, 630, 110, 110) platform.Platforms object at 0x02320A70 rect(350, 630, 110, 110) platform.Platforms object at 0x02320A70 rect(350, 630, 110, 110) platform.Platforms object at 0x02320A70 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

这为您提供了一种查找包含四叉树的方法(如果不存在则返回 None)，或者添加对象、创建它(返回现有的最大级别四叉树，或在适当的位置创建一个新的最大级别四叉树)象限)。

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

添加对象非常简单:

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

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