我正在编写一个基于整数的四叉树结构，它是从节点向上构建的而不是向下。为了做到这一点，我需要找到包含所有元素的下一个最大节点。如果我已经定义了一个现有节点，并尝试添加一个超出该节点边界的项，则需要创建一个更大的节点来包含它们两个。我已经（我认为很聪明）编写了代码以找到单个点周围的边界框：
public static Rectangle BoundingRectangle(Point p, int magnitude)
{
Rectangle bounds = new Rectangle()
{
X = (p.X & ~((1 << magnitude) - 1)),
Y = (p.Y & ~((1 << magnitude) - 1)),
Width = (1 << magnitude),
Height = (1 << magnitude)
};
return bounds;
}
注意，点（0,0）周围的框是大小为（1,1）位于（0,0）位置的框，而不是位于（-.5，-.5）的框，因为它是基于整数的。
据我所知，这将始终返回一个适合作为节点的四叉树的框。例如，
new Rectangle(0,0,2,2)是可接受的，new Rectangle(2,2,2,2)也是可接受的，但new Rectangle(1,1,2,2)则不行。我的问题是，我无法弄清如何为矩形而不是点完成此操作。我能想到的唯一解决方案是循环遍历不断增加的框，但我确定一定有一些O(1)的解决方案，只是我无法想出来。 示例：
Rectangle(X,Y,1,1) -> Rectangle(X,Y,1,1)
Rectangle(0,0,2,2) -> Rectangle(0,0,2,2)
Rectangle(1,1,2,2) -> Rectangle(0,0,4,4)
Rectangle(1,1,3,3) -> Rectangle(0,0,4,4)
Rectangle(0,5,2,2) -> Rectangle(0,4,4,4)
Rectangle(3,3,2,2) -> Rectangle(0,0,8,8)
实施：
private static int BitScanReverse(int mask)
{
int index = 0;
while (mask > 1)
{
mask >>= 1;
index++;
}
return index;
}
public static Rectangle BoundingRectangle(Point p, int magnitude)
{
Rectangle bounds = new Rectangle()
{
X = (p.X & ~((1 << magnitude) - 1)),
Y = (p.Y & ~((1 << magnitude) - 1)),
Width = (1 << magnitude),
Height = (1 << magnitude)
};
return bounds;
}
public static Rectangle BoundingRectangle(Rectangle r, int magnitude)
{
int msb = BitScanReverse((r.X ^ (r.X + r.Width - 1)) | (r.Y ^ (r.Y + r.Height - 1)));
return BoundingRectangle(r.Location, Math.Max(msb + 1, magnitude));
}