Nodo quadrifoglio limite più piccolo

Question

Sto scrivendo una struttura quadtree basata su un numero che si accumula dal nodo e non verso il basso. Per fare questo, ho bisogno di scoprire il prossimo nodo più grande che contiene tutti i miei elementi. Se ho un nodo preesistente definito, quindi cerco di aggiungere un elemento al di fuori dei limiti del nodo, è necessario creare un nodo più grande per racchiuderli entrambi. Ho (quello che che è intelligente) il codice per trovare il rettangolo di selezione intorno a un unico 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; 
} 

[Si noti che la casella attorno al punto (0,0) è una dimensione Boxof (1,1) in posizione (0,0), non in posizione (-.5, -. 5), poiché è basato su numeri interi]

Questo restituirà sempre una casella (da quello che posso dire) inserirsi in un quadrifoglio come nodo. Ad esempio, new Rectangle(0,0,2,2) sarebbe accettabile, come lo sarebbe new Rectangle(2,2,2,2), ma non lo sarebbe new Rectangle(1,1,2,2).

Il mio problema è che non riesco a capire come eseguire questo per un rettangolo, invece di un punto. L'unica soluzione che posso pensare sarebbe quella di passare da una scatola di grandezza crescente, ma sono sicuro che ci deve essere una soluzione O (1) che non riesco proprio a pensare.

---

Esempi:

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) 

---

Implementazione:

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

Consideriamo la versione unidimensionale di questa prima. Invece di un rettangolo, abbiamo un offset e una lunghezza.

La "grandezza" del rettangolo di delimitazione indica quanti bit ignorare.

Diciamo offset = 1234 e lunghezza = 56. Vogliamo ignorare abbastanza bit in modo che 'offset' (1234) e 'offset + length-1' (1289) mappino allo stesso numero.

1234 = 10011010010 
1289 = 10100001001 

Chiaramente, dobbiamo ignorare tutti tranne i primi 2 bit qui (ignorare 9 bit).

possiamo trovare questo livello di codice con 1234 XOR 1289 (che è 475)

1234 = 10011010010 
1289 = 10100001001 
475 = 00111011011 

e poi trovare il bit più significativo insieme di 475. La maggior parte dei processori hanno questa istruzione (su Windows, è _BitScanReverse).

Ora, per il tuo caso 2D, abbiamo bisogno di ottenere lo XOR sia per l'asse X che per l'asse Y. Quindi, noi O quei due risultati insieme. Infine, trova il bit più significativo.

Così, in pseudo-codice:

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

Per ottenere il rettangolo reale, basta usare la funzione nel tuo post. Passa in un nuovo punto (X, Y).