Как работает QuadTree для неквадратных областей?

Question

Я понимаю, как работают четырехугольные деревья на квадратных изображениях (разбивая изображение до тех пор, пока сечение не будет одного цвета, которое сохраняется в листовом узле).

Что произойдет, если изображение будет на одно измерение длиннее другого, в результате вы можете получить область размером 2x1 пикселя в качестве наименьшего субэлемента, что затруднит использование методов деления на четыре дерева для сохранения одного цвета. Как бы вы решили эту проблему?

Answer 1

Вы можете дополнить изображение, пока оно не станет равным и не станет равным степени двух размеров.Хотя это может добавить некоторые дополнительные требования к памяти, увеличение не должно быть таким большим.

Пример 2x1 будет дополнен стандартным 2x2 и сохранит реальный размер или будет использовать специальное значение для дополненных узлов, чтобы вы могли восстановить исходный размер.

Я знаю, что это старый вопрос, но я надеюсь, что все равно помог.

Answer 2

Квадрат - это особый прямоугольник, деревья квадра работают и с прямоугольниками.Вам просто нужен метод разделения, который дает 4 прямоугольника для данного.

В случае, если самая верхняя корневая четырехугольная ячейка является прямоугольником, просто разделите ширину и высоту на 2.

пикселей имеет смысл, только если высота виджета корневой ячейки равна степени 2.

Так что, если корневая ячейка = 2048 * 1024, разделение просто делит ширину и высоту на 2.

Answer 3

Почему вы не допускаете пустых листьев на своем дереве? Редактировать: Может быть, я не понимаю вопроса ^^. Ваша проблема в том, что у вас получаются не квадратные изображения, такие как 2x1, и вы хотите представить их в виде квадранода?

Когда у вас есть квадрат 2x2, как

1 2
3 4

вы бы создали Quadnode с чем-то вроде "new QuadNode (1,2,3,4)"

Я бы предложил разделить квадрат 2х1, как

1 2

с чем-то вроде "new QuadNode (1,2, null, null)" Если у вас больше недостающих фигур, вы можете использовать ту же систему. Когда у вас есть изображение 4x2, как

1 2 3 4
5 6 7 8

вы получите «новый QuadNode (новый QuadNode (1,2,3,4), ноль, новый QuadNode (5,6,7,8), ноль)»

Это также должно работать с элементами одинакового цвета вместо пикселей.

Я понял вашу проблему и прояснил ситуацию?