遍历四叉树

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

补充阅读：

Two Rectangles intersection

遍历四叉树

Traversing a Quad Tree

java

quadtree