python - Python QuadTree

Question

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プラットフォーム）.Platformsオブジェクト（0x0236FAB0）platform.Platformsオブジェクト（0x0236FAB0）platform.Platformsオブジェクト（0x0236FAB0）platform.Platformsオブジェクト（0x0）

これは良いことですが、可変ツリーに2つの異なるオブジェクトが必要ですが、それを呼び出すと、リストの2番目のオブジェクトしかありません。

だから私は関数を作りました

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）プラットフォーム）.Platformsオブジェクト（0x02320A70 rect（350、630、110、110）プラットフォーム）.Platformsオブジェクト（0x02320A70 rect（350、630、110、110）プラットフォーム）プラットフォームは0x02320A70rect（350、630、110、110）でオブジェクト化されます

score 2 · Accepted Answer

クラスadd_objectには、すでに1つある場合でも、毎回新しい下位レベルのクワッドツリーが作成されます。

以前のquadtreeの質問でこれを提案するつもりでしたが（確かにあなたでした）、チャンスが来る前に削除しました。QuadTreeクラスに、適切なものを検索または作成するメソッドがあると、おそらくより良いでしょう。場所を指定したサブツリー（とrectの両方add_objectsで呼び出すものget_elements）。これは、各オブジェクトが完全に1つのサブツリー内にあることを前提としていることに注意してください。これは、ポイントには当てはまりますが、任意の長方形には当てはまりません。（最も明白なケースは、非常に大きな長方形（フィールド全体をカバーする長方形）が、任意のレベルの四分木の4つのサブツリーすべてを占めることです。）

たとえば、のロジックが基本的に正しいと仮定すると、次の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を返す）、またはオブジェクトを追加する場合はオブジェクトを作成する方法（既存の最大レベルのクアッドツリーを返すか、適切な象限に新しい最大レベルのクアッドツリーを作成する）ができます。

getattrandsetattr操作では、計算したものを使用して、nameself.top_left、self.top_rightなどを取得および設定できます。

その場合、オブジェクトの追加は非常に簡単です。

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

位置の計算とテストを処理するためのより良い方法もありますが、それは演習として残しておきます。（もちろん、rectsが複数のサブツリーにまたがることができる場合（ポイントでない場合）、単一の適切な左上/右上/ではなく、すべての適切なサブツリーのリストを計算する必要があります。左下/右下のサブツリー。）

python - Python QuadTree

1 に答える 1

Related

Reference