我正在编写一个基于整数的四叉树结构,它是从节点向上构建的而不是向下。为了做到这一点,我需要找到包含所有元素的下一个最大节点。如果我已经定义了一个现有节点,并尝试添加一个超出该节点边界的项,则需要创建一个更大的节点来包含它们两个。我已经(我认为很聪明)编写了代码以找到单个点周围的边界框:
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));
}