Обход четырехъядерного дерева

Я реализовал Quadtree для сортировки точек на графике. Каждый раз, когда точка попадает в квадрант, который уже содержит точку, этот квадрант снова разделяется, чтобы позволить каждой точке попасть в свой собственный квадрант. Каждый узел имеет следующие атрибуты:

Rectangle bounds; //The bounds of the quadrant
int num = 0; //The number of points in or below this node
Point point; //The point stored in this node. If the quadrant is divided, this is set to null.
Quadtree sub[]; //Pointers to the 4 subdivided quadrants.

Скажем, я хотел просмотреть каждый узел, хранящийся в этом дереве, и подсчитать количество точек, попадающих в границы заданного прямоугольника, как мне рекурсивно проверить каждый узел в дереве (предполагая, что у меня уже есть методы, которые проверить, попадают ли они в определенный регион)?


java quadtree
person mattegener    schedule 08.03.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вы бы выполнили рекурсию по каждому узлу, границы которого перекрываются с данным прямоугольником.

Вот некоторый псевдокод, основанный на полях, которые вы упомянули в своем вопросе:

int countPointsInRect(Quadtree root, Rectangle r) {

    // Entire bound of current node outside of given rectangle?
    if (root.bounds outside r)
        return 0

    // Part, or whole of current bound inside given rectangle:
    // Recurse on each subtree
    int sum = 0
    for (Quadtree q : sub)
        sum += countPointsInRect(q, r)
    return sum
}

Вы можете немного оптимизировать его, добавив следующую проверку перед рекурсией по поддеревьям:

    // Entire bound of current node inside given rectangle?
    if (root.bounds inside r)
        return num  // return immediately. No need to recurse

Дополнительное чтение:

person aioobe    schedule 08.03.2015
comment
Хорошо, это имеет смысл. Где я борюсь, так это в том, как сделать рекурсивный метод для проверки каждого узла. - person mattegener; 08.03.2015
comment
Конечно, нет проблем. Обратите внимание, что я немного улучшил его в своем последнем редактировании. - person aioobe; 08.03.2015