5

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

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) 周围的框在位置 (0,0) 处是大小为 (1,1) 的框， 而不是在位置 (-.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));
}
4

1 回答 1

3

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

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

假设 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 轴的 XOR。然后，我们将这两个结果组合在一起。最后，找到最重要的设置位。

所以，在伪代码中：

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

要获得实际的矩形，只需使用帖子中的函数。传入新点（X，Y）。

于 2010-07-20T22:13:18.847 回答