最小边界四叉树节点

Question

我正在编写一个基于整数的四叉树结构，它从节点开始构建，而不是向下构建。为此，我需要发现包含所有元素的下一个最大节点。如果我定义了一个预先存在的节点，然后尝试在该节点的边界之外添加一个项目，则需要创建一个更大的节点来包含它们。我有（我认为很聪明）用于查找单个点周围的边界框的代码：

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

Answer 1

让我们首先考虑它的一维版本。我们没有矩形，而是有偏移量和长度。

边界矩形的“大小”告诉您要忽略多少位。

假设 offset = 1234 且 length = 56。我们希望忽略足够多的位，以便“offset”(1234) 和“offset+length-1”(1289) 映射到相同的数字。

1234 = 10011010010
1289 = 10100001001

显然，我们需要在这里忽略除前 2 位之外的所有位（忽略 9 位）。

我们可以通过编程方式使用 1234 XOR 1289（即 475）找到这一点，

1234 = 10011010010
1289 = 10100001001
 475 = 00111011011

然后找到 475 的最高有效设置位。大多数处理器都有这条指令（在 Windows 上，它是 _BitScanReverse）。

现在，对于 2D 情况，我们需要对 X 轴和 Y 轴进行异或。然后，我们将这两个结果进行“或”运算。最后，找到最高有效的设置位。

因此，在伪代码中：

magnitude = MSBof( ( X ^ (X+width-1) ) | ( Y ^ (Y+height-1) ) )

要获取实际的矩形，只需使用帖子中的函数即可。传入新的Point(X,Y)。