El nodo quadtree delimitador más pequeño

Question

Estoy escribiendo una estructura cuádruple basada entera que se construye desde el nodo, y no hacia abajo. Para hacer esto, necesito descubrir el siguiente nodo más grande que contiene todos mis elementos. Si tengo un nodo preexistente definido, entonces intento agregar un elemento fuera de los límites de ese nodo, necesita crear un nodo más grande para abarcarlos a ambos. Tengo (lo que que es inteligente) código de la búsqueda de la caja alrededor de un único punto:

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

[Observe que el cuadro alrededor del punto (0,0) es un tamaño boxof (1,1) en la ubicación (0,0), no en la ubicación (-.5, -. 5), ya que está basado en un entero]

Esto siempre (de lo que puedo decir,) devuelve una casilla que encajar en un quadtree como un nodo. Por ejemplo, new Rectangle(0,0,2,2) sería aceptable, al igual que new Rectangle(2,2,2,2), pero new Rectangle(1,1,2,2) no lo sería.

Mi problema es que no puedo encontrar la manera de lograr esto para un rectángulo, en lugar de un punto. La única solución que se me ocurre sería recorrer cajas de magnitud creciente, pero estoy seguro de que tiene que haber alguna solución de O (1) en la que no pueda pensar.

---

Ejemplos:

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) 

---

Implementación:

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

Consideremos la versión unidimensional de esta primera. En lugar de un rectángulo, tenemos un desplazamiento y longitud.

La 'magnitud' de su rectángulo delimitador le indica cuántos bits ignorar.

Digamos que offset = 1234 y length = 56. Queremos ignorar suficientes bits para que 'offset' (1234) y 'offset + length-1' (1289) se asignen al mismo número.

1234 = 10011010010 
1289 = 10100001001 

Claramente, tenemos que ignorar aquí todos los primeros 2 bits (ignorar 9 bits).

Nos puede encontrar esta programación con 1234 XOR 1289 (que es 475)

1234 = 10011010010 
1289 = 10100001001 
475 = 00111011011 

y luego encontrar el bit más significativo del conjunto 475. La mayoría de los procesadores tienen esta instrucción (en Windows, es _BitScanReverse).

Ahora, para su carcasa 2D, necesitamos obtener el XOR tanto para el eje X como para el eje Y. Entonces, nosotros O esos dos resultados juntos. Finalmente, encuentre el bit establecido más significativo.

Así, en pseudo-código:

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

Para obtener el rectángulo real, sólo tiene que utilizar la función en su puesto. Pase en un nuevo punto (X, Y).