Проблема Quadtree - хранение избыточной информации

Question

У меня есть изображение, которое не является квадратом (размер m x n). Кроме того, его размеры не относятся к основанию 2 (т.е. не = 2 ^ k & n не = 2 ^ k). Я справился с этим, поместив изображение в больший квадрат (следующая степень двух), используя следующее:

int width = (int)Math.ceil(Math.pow(2, Math.log(img.width)/Math.log(2)));
int height = (int)Math.ceil(Math.pow(2, Math.log(img.height)/Math.log(2)));

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

if (img.width > img.height) {
    // draw width * width square
}

if (img.height > img.width) {
    // draw height * height square
}

Проблема:

Теперь дерево quadtree выглядит совершенно иначе, поскольку в нем хранятся все узлы без изображений в дереве. Это, очевидно, влияет на предполагаемые данные изображения (то есть минимальную / максимальную глубины) и саму форму дерева. У меня вопрос, эффективно ли я делаю это, и если да, то как мне не хранить данные, которые не принадлежат изображению? Если это не лучший способ нарисовать неквадратное изображение, может ли кто-нибудь указать мне правильное направление? Кажется, что все статьи в Google слишком глубоки для моих целей.

Answer 1

Возможно, вместо того, чтобы ваше дерево оканчивалось (условными) отдельными пикселями, оно могло бы хранить небольшие блоки p пикселей на o пикселей для некоторого p x o, что сделало бы количество блоков на стороне степенью двойки. Это заставило бы ваше дерево вести себя хорошо, за счет введения в структуру другого понятия.

Answer 2

Хорошая вещь о quadtree - они будут хранить большие куски идентичных данных. Ваши дополнительные пустые данные изображения должны лишь немного добавить к вашему общему размеру хранилища. Я предлагаю, чтобы вы добавили дополнительную информацию в вашу структуру данных, которая хранит фактические исходные размеры изображения. При десериализации вашего квадродерева вы можете «отрезать» лишнюю деталь на основе фактических размеров, чтобы получить оригинал.