c++ - 四叉树和递归构造函数堆栈溢出

Question

我正在创建一个分块的 QuadTree 地形，我试图确保两个节点之间的细节差异永远不会超过一个级别。我当前的构造函数代码是这样的:

QuadNode::QuadNode(Rect area, QuadNode * p, QuadRoot * r)
{
    Root = r;

    Parent = p;
    Level = p->Level + 1;

    InitializeGeometry(area);

    for(int iii = 0; iii < 4; iii++)
            Children[iii] = 0;

    for(int iii = 0; iii < 4; iii++)
    {
            if(QuadrantNeedsChild(iii))
                    Children[iii] = new QuadNode(GetRect(iii), this, Root);
    }
}

而且效果很好。但是为了强制两个相邻节点之间的差异不超过一级，我试图将其添加到构造函数的末尾:

QuadNode * neighbour;

for(int direction = 0; direction < 4; direction++)
{
    neighbour = FindNeighbour(direction);
    if(neighbour)
    {
        while(Level - neighbour->Level > 1)
        {
            neighbour->Subdivide();
            neighbour = FindNeighbour(direction);
                    //neighbour should now be a child of the previous neighbour
        }
    }
}

但是那个堆栈溢出了。我认为的一个原因是 Children[iii] = new QuadNode(GetRect(iii), this, Root); 语句的赋值部分永远不会执行并且 FindNeighbour() 要求设置子项以找到合适的邻居。但我不认为这是唯一的问题，因为代码实际上从未到达第二个 neighbor = FindNeighbour(direction); 行，我不知道是什么原因造成的。

如果我在树的基本创建之后在新函数中运行第二个代码片段，它或多或少会起作用，但它需要多次传递以确保新创建的节点本身不会产生大于 1 的层差。所以如果可能的话，我宁愿在构造函数中包含这段代码。任何人都可以想出一种方法来实现这一点吗？

关于类(class)的一些注意事项，以防它有助于 QuadrantNeedsChild(int quadrant) 确保级别永远不会超过 8，所以我知道我不会说得太深。 Subdivide() 只是在所有象限上运行 Children[iii] = new QuadNode(GetRect(iii), this, Root);。 FindNeighbour(int direction) 可以返回父对象或祖先对象。例如，如果 D 正在寻找北邻居，如果 B 从未 segmentation 为以下内容，它将获得其祖 parent (整个图表):

 - - - - - -
|     |     |
|  A  |  B  |
|     |     |
|- - - - - -|
|     | D|  |
|  C  |-----|
|     |  |  |
 - - - - - -

如果提供了超出范围的象限，则 segmentation 函数只会 segmentation 给定的象限或所有象限。

void QuadNode::Subdivide(int quadrant)
{
    if(quadrant > -1 && quadrant < 4)
    {
        if(!Children[quadrant])
            Children[quadrant] = new QuadNode(GetRect(quadrant), this, Root);
    }
    else
        for(int iii = 0; iii < 4; iii++)
            if(Children[iii] == 0)
                Children[iii] = new QuadNode(GetRect(iii), this, Root);
}

Answer 1

当构建节点的第一个子节点时，它是否找到它自己的父节点作为邻居，因为该父节点还没有子节点(第一个节点即将创建)？

这将导致节点在其自己的父节点上调用 Subdivide()，这将构造一个新的子节点，该子节点将再次调用 Subdivide()，...

即使没有这个，在新层上构建第一个节点也会 Subdivide() 它的所有邻居，这反过来又会递归地 segmentation 这些邻居的所有邻居。这是它应该如何工作的吗？对于最深层次，这将导致类似 4⁸ 层次的递归。