1

我正在创建一个分块的 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()需要设置孩子以找到合适的邻居。但我认为这不是唯一的问题，因为代码实际上从未到达第二neighbour = FindNeighbour(direction);行，而且我不知道是什么原因造成的。

如果我在树的基本创建之后在新函数中运行第二个代码片段，它或多或少可以工作，但是它需要多次传递以确保新创建的节点本身不会产生大于 1 的级别差异。所以我如果可能的话，我宁愿在构造函数中包含这段代码。谁能想到实现这一目标的方法？

课堂上的一些笔记，以防它有助于QuadrantNeedsChild(int quadrant)确保水平永远不会超过 8，所以我知道我不仅仅是太深了。Subdivide()只是Children[iii] = new QuadNode(GetRect(iii), this, Root);在所有象限上运行。FindNeighbour(int direction)可以返回父级或祖先。例如，如果 D 正在寻找北邻居，如果 B 从未细分为以下内容，它将获得其祖父母（整个图表）：

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

如果提供了超出范围的象限，则细分功能仅细分给定的象限或所有象限。

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);
}
4

1 回答 1

2

当构造节点的第一个子节点时，它是否发现它自己的父节点作为邻居，因为该父节点还没有子节点（第一个节点即将创建）？

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

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

于 2012-06-16T01:47:19.697 回答