Plus petit nœud de quadtree de limitation

Question

J'écris une structure de quadtree basée sur un nombre entier qui se construit à partir du nœud, et non vers le bas. Pour ce faire, j'ai besoin de découvrir le prochain nœud le plus grand qui contient tous mes éléments. Si j'ai un nœud préexistant défini, alors essayez d'ajouter un élément en dehors des limites de ce nœud, il doit créer un nœud plus grand pour les englober tous les deux. J'ai (ce je pense est intelligent) code pour trouver la zone de délimitation autour d'un seul 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; 
} 

[Notez que la zone autour du point (0,0) est une taille Boxof (1,1) à l'emplacement (0,0), pas à l'emplacement (-.5, -. 5), puisque tout est basé sur les entiers]

Cela sera toujours (à partir de ce que je peux dire,) retourner une boîte qui serait s'intégrer dans un quadtree en tant que nœud. Par exemple, new Rectangle(0,0,2,2) serait acceptable, tout comme new Rectangle(2,2,2,2), mais new Rectangle(1,1,2,2) ne serait pas.

Mon problème est que je ne peux pas comprendre comment accomplir ceci pour un rectangle, au lieu d'un point. La seule solution que je puisse envisager serait de faire des boucles de boîtes de plus en plus grandes, mais je suis sûr qu'il doit y avoir une solution O (1) à laquelle je ne peux pas penser.

---

Exemples:

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) 

---

Mise en œuvre:

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

Considérons la version unidimensionnelle de ce premier. Au lieu d'un rectangle, nous avons un décalage et une longueur. La 'magnitude' de votre rectangle de délimitation indique le nombre de bits à ignorer.

Supposons offset = 1234 et length = 56. Nous voulons ignorer suffisamment de bits pour que 'offset' (1234) et 'offset + length-1' (1289) correspondent au même nombre. De toute évidence, nous devons ignorer tous sauf les 2 premiers bits ici (ignorer 9 bits).

Nous pouvons trouver ce programme avec 1234 XOR 1289 (qui est 475)

1234 = 10011010010 
1289 = 10100001001 
475 = 00111011011 

puis trouver le bit le plus significatif de 475. La plupart des processeurs ont cette instruction (sous Windows, il est _BitScanReverse). Maintenant, pour votre cas 2D, nous devons obtenir le XOR pour l'axe des X et l'axe des Y. Maintenant, pour votre cas 2D, nous devons obtenir le XOR pour l'axe des X et l'axe des Y. Ensuite, nous OU ces deux résultats ensemble. Enfin, trouvez le bit set le plus significatif.

Ainsi, en pseudo-code:

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

Pour obtenir le rectangle réel, il suffit d'utiliser la fonction dans votre post. Passer au nouveau point (X, Y).