Массовая загрузка точки quadtree

Я реализовал метод массовой загрузки дерева квадрантов точек. Но для некоторых входных данных это работает неправильно, например, если есть много точек с одинаковыми координатами x или y. Пример набора данных:

test = [(3, 1), (16, 1), (11, 4), (5, 4), (9, 6), (5, 10),
        (1, 15), (11, 5), (11, 15), (12, 16), (19, 17)]
tree = create(test)

Проблема возникает в точках: (11,4),(11,5),(11,15) и (5,10),(5,4).

Это функция create:

def create(point_list, presorted=False):
    if not point_list:
        return QuadNode()

    if not presorted:
        point_list.sort(key=lambda p: [p[0],p[1]])

    median = len(point_list) >> 1

    relevantPoint = point_list[median]
    relevantYCoordinate = relevantPoint[1]

    node = QuadNode(data=relevantPoint)

    leftBins = point_list[:median]
    rightBins = point_list[median + 1:]

    nwBins = [bin for bin in leftBins if bin[1] >= relevantYCoordinate]
    swBins = [bin for bin in leftBins if bin[1] < relevantYCoordinate]

    neBins = [bin for bin in rightBins if bin[1] >= relevantYCoordinate]
    seBins = [bin for bin in rightBins if bin[1] < relevantYCoordinate]

    node.nwNode = create(nwBins, presorted=True)
    node.swNode = create(swBins, presorted=True)

    node.neNode = create(neBins, presorted=True)
    node.seNode = create(seBins, presorted=True)
    return node

и QuadNode:

class QuadNode(object):
    def __init__(self, data=None, nwNode=None, neNode=None, swNode=None, seNode=None):
        self.data = data
        self.nwNode = nwNode
        self.neNode = neNode
        self.swNode = swNode
        self.seNode = seNode

Я хочу следовать правилу вставки, удаления и т.д.:

  • swNode point.x < parent.x и point.y < parent.y
  • seNode point.x >= parent.x и point.y < parent.y
  • nwNode point.x < parent.x и point.y >= parent.y
  • neNode point.x >= parent.x и point.y >= parent.y

python data-structures quadtree
person greedsin    schedule 10.05.2017    source источник
comment
Таким образом, выход теперь равен [(1, 15), (3, 1), (5, 4), (5, 10), (9, 6), (11, 4), (11, 5), (11, 15), (12, 16), (16, 1), (19, 17)]. Что бы вы хотели получить на выходе? Я немного забыл, как работают quadtrees..   -  person gsamaras    schedule 17.05.2017

Ответы (1)


arrow_upward
3
arrow_downward

Ваш метод выбора середины является правильным (как описано в исходная статья Finkel о составных данных Aquadrieval ), но то, как вы создаете подколлекции для поддеревьев, неверно.

Например, с этим отсортированным списком:

[(1, 1), (1, 2), (1, 3)]

медиана равна 1, 2, и, учитывая ваши правила для границ, 1,1 должно быть на юго-востоке, а 1,3 на северо-востоке.
В оригинальной статье юго-запад и северо-запад «открыты», а северо-запад и юго-восток закрыты: 1,1 находится на северо-западе, а 1,3 на ЮВ. Как вы можете видеть с этим определением границ, все элементы перед медианой будут на ЮВ или СЗ, а все элементы после медианы будут на ЮЗ или СВ. Но это не соответствует вашему определению границ.

Таким образом, либо что-то не так с определением ваших границ, либо вы должны проверить каждый элемент списка, чтобы убедиться, что он попадает в нужную область. Например:

relevantPoint = point_list[median]
node = QuadNode(data=relevantPoint)
del point_list[median]

nwBins = [(x,y) for x,y  in point_list if x < relevantPoint[0] and y >= relevantPoint[1]]
swBins = [(x,y) for x,y  in point_list if x < relevantPoint[0] and y < relevantPoint[1]]
seBins = [(x,y) for x,y  in point_list if x >= relevantPoint[0] and y <= relevantPoint[1]]
neBins = [(x,y) for x,y  in point_list if x <= relevantPoint[0] and y > relevantPoint[1]]

Однако это довольно уродливо и не гарантирует, что дерево будет сбалансировано. Я лучше проверю определение границ....

person Pierre Rust    schedule 17.05.2017
comment
Можете ли вы предоставить документ или статью/блог, где обсуждается выбор медианного значения? - person greedsin; 17.05.2017
comment
На самом деле, я только что понял, что мой ответ совершенно неверен, изменю его через несколько минут, извините... - person Pierre Rust; 17.05.2017