python - Python QuadTree

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center。
                            
                        
                    
                
                                7年前关闭。
            
                    
我在QuadTree中添加了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对象位于0x0236F950 platform.Platforms对象位于
  0x0236F950平台.platforms对象位于0x0236F950平台.platforms
  0x0236F950平台上的对象.0x0236FAB0上的平台对象
  位于0x0236FAB0的platform.Platforms对象
  0x0236FAB0平台。位于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对象位于0x02320A70 rect（350，630，110，110）
  platform.Platforms对象位于0x02320A70 rect（350，630，110，110）
  platform.Platforms对象位于0x02320A70 rect（350，630，110，110）
  platform.Platforms对象位于0x02320A70 rect（350，630，110，110）

最佳答案

您的add_object类每次都会创建一个新的下层四叉树，即使那里已经有一个。

我将在您先前的四叉树问题（肯定是您）上建议这个问题，但是您在有机会的情况下将其删除：如果QuadTree类具有查找或创建适当方法的方法，您可能会更好子树指定了位置（在rect和add_objects中都称为get_elements）。请注意，这假定每个对象都完全位于一个子树中，这对于点是正确的，但对于任意矩形则不然。 （最明显的情况是，一个非常大的矩形（覆盖整个字段）占据了任意给定四叉树级别的所有四个子树。）

例如，假设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)

还有一种更好的方法来处理位置计算和测试，但我将其保留为练习。 （当然，如果rect可以跨越多个子树（如果不是点的话），则需要计算所有适当子树的列表，而不是单个适当的top-left / top -right /左下/右下子树。）

关于python - Python QuadTree ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10264631/