最小边界四叉树节点

我

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

不 在位置(-.5,-.5),因为它都是基于整数的]

new Rectangle(0,0,2,2) new Rectangle(2,2,2,2) ,但是 new Rectangle(1,1,2,2)

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