Smallest bounding quadtree node

Question

I'm writing an integer-based quadtree structure which builds up from the node, and not down. To do this, I need to discover the next largest node which contains all my elements. If I have a preexisting node defined, then try to add an item outside of that node's bounds, it needs to create a larger node to encompass them both. I have (what I think is clever) code for finding the bounding box around a single point:

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

[Note that the box around point (0,0) is a boxof size (1,1) at location (0,0), not at location (-.5,-.5), since it's all integer-based]

This will always (from what I can tell,) return a box which would fit into a quadtree as a node. For example, new Rectangle(0,0,2,2) would be acceptable, as would new Rectangle(2,2,2,2), but new Rectangle(1,1,2,2) would not be.

My problem is that I can't figure out how to accomplish this for a rectangle, instead of a point. The only solution I can think of would be to loop through boxes of increasing magnitude, but I'm sure there has to be some O(1) solution I'm just not able to think of.

---

Examples:

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)

---

Implementation:

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

Let's consider the one-dimensional version of this first. Instead of a rectangle, we have an offset and length.

The 'magnitude' of your bounding rectangle is telling you how many bits to ignore.

Let's say offset = 1234 and length = 56. We want to ignore enough bits so that 'offset' (1234) and 'offset+length-1' (1289) map to the same number.

1234 = 10011010010
1289 = 10100001001

Clearly, we need to ignore all but the first 2 bits here (ignore 9 bits).

We can find this programmatically with 1234 XOR 1289 (which is 475)

1234 = 10011010010
1289 = 10100001001
 475 = 00111011011

and then finding the most significant set bit of 475. Most processors have this instruction (on Windows, it's _BitScanReverse).

Now, for your 2D case, we need to get the XOR for both the X-axis and Y-axis. Then, we OR those two results together. Finally, find the most significant set bit.

So, in pseudo-code:

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

To get the actual rectangle, just use the function in your post. Pass in new Point(X, Y).