遍历四叉树

Question

我已经实现了一个四叉树来对图形中的点进行排序。每当一个点落在已经包含一个点的象限内时，该象限就会再次细分，以允许每个点落入其自己的象限。每个节点都具有以下属性：

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

附加阅读:

< li >两个矩形的交集