我正在创建一个分块的 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);
}
最佳答案
当构建节点的第一个子节点时,它是否找到它自己的父节点作为邻居,因为该父节点还没有子节点(第一个节点即将创建)?
这将导致节点在其自己的父节点上调用 Subdivide()
,这将构造一个新的子节点,该子节点将再次调用 Subdivide()
,...
即使没有这个,在新层上构建第一个节点也会 Subdivide()
它的所有邻居,这反过来又会递归地 segmentation 这些邻居的所有邻居。这是它应该如何工作的吗?对于最深层次,这将导致类似 48 层次的递归。
关于c++ - 四叉树和递归构造函数堆栈溢出,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11005224/