遍历四叉树

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 
} 

您可以通过递归下降的子树之前添加下面的检查略微优化它阅读：

• Two Rectangles intersection