私は、ノードから構築され、ダウンではない整数ベースの四分木構造を書いています。これを行うには、すべての要素を含む次に大きいノードを見つける必要があります。既存のノードを定義している場合、そのノードの境界外にアイテムを追加しようとすると、両方を包含するように、より大きなノードを作成する必要があります。私は（私が賢いと思う）単一の点の周りのバウンディングボックスを見つけるためのコードを持っています：
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;
}
[ポイント（0,0）の周りのボックスは、 すべて整数ベースであるため、場所（-.5、-。5）ではなく、場所（0,0）のサイズ（1,1）のボックスであることに注意してください]
これは常に（私が言えることから）ノードとして四分木に収まるボックスを返します。たとえば、new Rectangle(0,0,2,2)は受け入れられますがnew Rectangle(2,2,2,2)、受け入れられnew Rectangle(1,1,2,2)ません。
私の問題は、点ではなく長方形に対してこれを実現する方法がわからないことです。私が考えることができる唯一の解決策は、大きさが増すボックスをループすることですが、私が考えることができないいくつかのO（1）解決策が必要であると確信しています。
例：
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));
}