c - 给定宽度和长度的矩形的包装

Question

我有一棵树，叶节点中有矩形，内部节点有“V”或“H”。我想打包矩形，给定它们的宽度和高度。如果有“V”，我将把左 child 和右 child 打包在一起，如果有“H”，我想把左 child 打包在右 child 的上面。最后我想确定每个矩形的坐标。我附上了一张显示树和构造包装的图像。

我正在做的是，我正在遍历树中的每个节点。当它到达叶节点时，它会构建一个结构体矩形并将其存储到一个数组中。然后，当它到达“V”时，我只需通过添加数组中倒数第二个矩形的宽度来更改数组中最后一个矩形的 x 坐标。我构造一个新的矩形，它适合最后一组矩形，并将其放入数组中。如果我得到“H”，我会增加数组中特定矩形的 y 坐标。但是，我在执行此操作时遇到了麻烦，因为我不知道哪些所有矩形 y 坐标都应该更改。可以有任意数量的这样的矩形。请帮忙!!

Answer 1

经过多次检查您的问题，我想我可能已经理解了您的问题。

您的包装有一条规则(您没有说明)，对于左/右包装，矩形需要底部对齐。对于顶部/底部包装，矩形需要左对齐。你的坐标系使用左下角作为(0,0)

我还假设打包完成后您需要生成每个矩形的坐标(假设每个矩形的尺寸都是已知数据，对于每个矩形您只需要生成1个坐标，例如左下角的坐标)

使用数组来保存此类数据可能不起作用。您输入的打包关系存储在树中，您可以使用完全相同的树来存储打包结果。

树中的每个节点都代表一个矩形。内部节点将表示“包装”子矩形的矩形。对于每个节点，您需要定义变量来存储其尺寸、绝对坐标和相对坐标(相对于其直接父节点)。

然后可以对树进行两次遍历，第一次遍历从下往上计算所有相对坐标(深度优先搜索)，第二次遍历从上到下扣除绝对坐标。

下面是第一次遍历的伪代码(在 DFS 的递归函数中)

packtree(treeroot)
{
    if(treeroot is a leaf) return; // do nothing and return the function

    packtree(leftchild);
    packtree(rightchild);
    if(treeroot is V type)
    {
      treeroot.width = leftchild.width+rightchild.width
      treeroot.height = leftchild.height > rightchild.height ? leftchild.height : rightchild.height
      leftchild.relative_cor = (0,0)
      rightchild.relative_cor = (leftchild.width, 0)
    }
    else if(treeroot is H type)
    { 
      treeroot.width = leftchild.width> rightchild.width ? leftchild.width:rightchild.width
      treeroot.height = leftchild.height + rightchild.height
      leftchild.relative_cor = (0, rightchild.height) // because he is sitting on top of the rightchild
      rightchild.relative_cor = (0,0)
    }
}

我将把第二次遍历留给你。 :)