Как эффективно вставить неточечные объекты в квадри

Question

Я пытаюсь создать структуру Quadtree в Python для обнаружения столкновений между полигонами, и я продвинулся довольно далеко (см. Конец поста). Тем не менее, я понял, что эта структура работает только для точек, потому что я решаю, на какой лист поместить объект, основываясь на его центре.

Поэтому мне нужно выяснить, как изменить это дерево квадрантов, чтобы я мог обнаруживать столкновения областей (например, круг!).

Есть несколько способов думать об этом:

• Только помещайте объекты в тот узел, который они полностью заполняют - это кажется неэффективным, потому что весь смысл Quadtrees состоит в том, чтобы помещать объекты в листы для легкого поиска / извлечения и уменьшения количества извлекаемых объектов.
• Поместите объект в каждый лист, с которым он перекрывается - это кажется хорошим решением, но я не совсем уверен, как подходить к принятию решения с перекрытием (и мне интересно, будет ли это неэффективно).
• ??? -- Есть ли лучшее решение?

Вариант № 2 (размещение объекта в нескольких узлах), я чувствую, что было бы лучше нарисовать ограничивающий прямоугольник вокруг объекта, а затем использовать экстенты объекта, чтобы решить, в какой лист его поместить - но это потребует эффективной вставки каждого объекта 4 раза (по одному на каждый угол), и это кажется неэффективным способом решения проблемы.

Есть лучшие предложения?

    class Quadtree(object):
    """
    A simple Quadtree implementation.  This works with any child object that has a getPosition() method that returns a list or tuple.
    """
    def __init__(self, depth, min_x, min_y, max_x, max_y):
        self.mDepth = depth
        self.mMaxDepth = 4
        self.mMinX = min_x
        self.mMaxX = max_x
        self.mMidX = (max_x - min_x) / 2.0
        self.mMinY = min_y
        self.mMaxY = max_y
        self.mMidY = (max_y - min_y) / 2.0
        self.mHasChildren = False
        self.mMaxChildren = 8
        self.mChildren = []
        self.mSubtrees = []

    def insert(self, newChild):
       """
       Insert an object into the tree.  Returns True if the insert was successful, False otherwise.
       """
       if self.mSubtrees:
           #if subtrees exist, add the child to the subtrees
           index = getIndex(newChild)
           if index != -1:
               self.mSubtrees[index].insert(newChild)
               return True

       #if no subtrees exist, add the child to the child list.
       self.mChildren.append(newChild)

       #and then check if we need to split the tree
       #if there are more than the max children, and we haven't maxed out the tree depth, and there are no subtrees yet
       if len(self.mChildren) > self.mMaxChildren and self.mDepth < self.mMaxDepth and not self.mSubtrees:
           split()
           for child in self.mChildren:
               index = getIndex(child)
               if index != -1:
                   self.mSubtrees[index].insert(child)
           return True

       return False

    def retrieveNeighbors(self, targetChild):
       index = getIndex(targetChild)
       if index != -1 and self.mSubtrees:
           return self.mSubtrees[index].retrieve(targetChild)
       return self.mChildren

    def getIndex(self, child):
       """
       Returns the index of the node that the object belongs to.  Returns -1 if the object does not exist in the tree.
       """
       index = -1
       childPosition = child.getPosition()
       #check if it fits in the top or bottom
       isInTopQuadrant = childPosition[1] > self.mMidY and childPositoin[1] < self.mMaxY
       #check if it fits left
       if childPosition[0] < self.mMidX and childPosition[0] > self.mMinX:
           if isInTopQuadrant:
               index = 1
           else:
               index = 2
       #check if it fits right
      if childPosition[0] > self.mMidX and childPosition[0] < self.mMidX:
          if isInTopQuadrant:
              index = 0
          else:
              index = 3

      return index

    def split(self):
       """
       Split the trees into four subtrees.
       """
       #top right
       self.mSubtrees.append(Quadtree(depth + 1, self.mMidX, self.mMidY, self.mMaxX, self.mMaxY))
       #top left
       self.mSubtrees.append(Quadtree(depth + 1, self.mMinX, self.mMidY, self.mMidX, self.mMaxY))
       #bottom left
       self.mSubtrees.append(Quadtree(depth + 1, self.mMinX, self.mMinY, self.mMidX, self.mMidY))
       #bottom right
       self.mSubtrees.append(Quadtree(depth + 1, self.mMidX, self.mMinY, self.mMaxX, self.mMidY))

    def clear(self):
       """
       Clears the quadtree of children, and all subtrees of children.
       """
       self.mChildren[:] = []
       self.mHasChildren = False
       for tree in range(0,4):
           if self.mSubtrees[tree].mHasChildren:
               self.mSubtrees[tree].clear()

Answer 1

Лучший способ, который я нашел, - это изменить _get_index() проверить весь размер частицы - если он не полностью помещается в поддерево, то он становится дочерним по отношению к родительскому узлу:

def _get_index(self, child):
    """
    Returns the index of the node that the object belongs to.  Returns -1 if the object does not exist in the tree.
    """
    index = -1
    child_position = child.get_position()
    child_radius = child.get_radius()
    if len(child_position) != 2:
        print "Quadtree is only designed to handle two-dimensional objects! Object will not be added."
        return index
    #check if it fits in the top or bottom
    is_in_top_quadrant = child_position[1] - child_radius > self.mid_y and child_position[1] + child_radius < self.max_y
    #check if it fits left
    if child_position[0] + child_radius < self.mid_x and child_position[0] - child_radius > self.min_x:
        if is_in_top_quadrant:
            index = 1
        else:
            index = 2
    #check if it fits right
    if child_position[0] - child_radius > self.mid_x and child_position[0] + child_radius < self.mid_x:
        if is_in_top_quadrant:
            index = 0
        else:
            index = 3
    return index

затем retrieve_neighbors() может пройти по дереву и добавить дочерние элементы каждого проходящего узла вплоть до конечного узла.