Самый маленький ограничивающий узел дерева квадрантов - PullRequest
Новая
       5

Самый маленький ограничивающий узел дерева квадрантов

5 голосов
/ 21 июля 2010

Я пишу целочисленную структуру дерева квадрантов, которая строится из узла, а не вниз.Для этого мне нужно найти следующий по величине узел, который содержит все мои элементы.Если у меня определен ранее существующий узел, то попробуйте добавить элемент за пределы этого узла, ему нужно создать более крупный узел, чтобы охватить их обоих.У меня есть (что I считает умным) код для нахождения ограничивающего прямоугольника вокруг одной точки: 

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) является boxofразмер (1,1) в местоположении (0,0), не в местоположении (-.5, -. 5), так как все они основаны на целых числах]

Это будет всегда (из того, что я могу сказать,) вернуть поле, которое будет вписываться в квадродерево в качестве узла.Например, 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));
}

1 Ответ

3 голосов
/ 21 июля 2010

Давайте сначала рассмотрим одномерную версию этого. Вместо прямоугольника у нас есть смещение и длина.

Величина вашего ограничительного прямоугольника говорит вам, сколько битов следует игнорировать.

Скажем, смещение = 1234 и длина = 56. Мы хотим игнорировать достаточно битов, чтобы 'смещение' (1234) и 'смещение + длина-1' (1289) отображались на одно и то же число. 

1234 = 10011010010
1289 = 10100001001

Очевидно, что здесь нужно игнорировать все, кроме первых 2 бит (игнорировать 9 бит).

Мы можем найти это программно с 1234 XOR 1289 (что 475) 

1234 = 10011010010
1289 = 10100001001
 475 = 00111011011

и затем поиск старшего значащего установленного бита 475. У большинства процессоров есть эта инструкция (в Windows это _BitScanReverse).

Теперь для вашего 2D-случая нам нужно получить XOR как для оси X, так и для оси Y. Затем мы ИЛИ эти два результата вместе. Наконец, найдите самый значимый бит.

Итак, в псевдокоде: 

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

Чтобы получить реальный прямоугольник, просто используйте функцию в своем посте. Пройдите в новую точку (X, Y).

...