Обход четырех деревьев

Question

Я реализовал 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.

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

Answer 1

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

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

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

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

• Пересечение двух прямоугольников