Являются ли Linear Quadtree наиболее эффективным способом хранения данных деления сетки

Question

Допустим, у вас есть сетка 32x32, которая может быть случайным образом разделена с использованием любого из следующих размеров блоков:

32x32, 16x16, 8x8, 4x4

Сколько раз сетка делится икаким образом происходит разделение, определяется случайным образом.

Визуально это может выглядеть примерно так:

Этот тип данных может быть представлен с помощью четырехугольного дерева .

Мой вопрос:

Если бы я пытался использовать наименьшее количество байтов для представления приведенного выше графика, было бы наиболее эффективным линейное квад-деревоспособ сделать это?

Единственная другая альтернатива, о которой я мог подумать, это составить все возможные комбинации графа и использовать одно число для представления каждой комбинации.

Так что дляВ графе существует 4 уровня ветвления (32x32, 16x16, 8x8, 4x4), что даст нам 4 ^ 0 + 4 ^ 1 + 4 ^ 2 + 4 ^ 3 возможных комбинаций, что равно 85 комбинациям.

Поэтому самый маленький способ сохранить график - использовать 7 бит (1010101 - это двоичное число 85) для представления возможных комбинаций.

Будет ЛинейныйQuadtree равно этому с точки зрения эффективности хранения, или они занимают больше или меньше места?

Answer 1

Обычно я не отвечаю на свои вопросы, но, видя, что этот вопрос все еще получает мнения без ответов, я дам свой ответ.

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

Линейное квадродерево - это просто представление массива четырехугольного дерева, записанного в определенном порядке обхода.

По сути, просто выберите определенный «порядок», в котором вы хотите прочитать четырехугольное дерево, и сохраните его значения в этом порядке.

Так, например, на графике, используемом в вопросе, есть 4 уровня стеков, потому что есть 4 размера блоков (32, 16, 8, 4).

Каждый стек может быть прочитанс целью.

Таким образом, предполагая, что весь граф был заполнен блоком 32x32, «корень» дерева (первый читаемый нами узел) будет заполнен «1», чтобы показать, что нам нужен этот блок, в то время как все дочерние элементыкорня будет "0", так как больше нет необходимости в блоках, потому что график полон.

Таким образом, линейное квадродерево будет выглядеть так в двоичном виде "10000000000000 .... (84 0)" "

Это, очевидно, больше, чем 7 бит, которые я упомянул в своем вопросе, но это потому, что сжатие к этому линейному четырехугольному дереву не применяется.

Я действительно задал не тот вопрос.Вам нужны линейные четырехугольные деревья для представления четырехугольного дерева, поэтому мне действительно следовало бы спросить «Каков наилучший способ сжатия линейного четырехугольного дерева», и идея, которую я высказал в своем вопросе, является наилучшим способом.

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