线性四叉树是存储网格划分数据的最有效方法吗
Are Linear Quadtrees the most efficient way to store grid division data
假设您有一个 32x32 的网格，可以使用以下任何块大小随机细分：
32x32、16x16、8x8、4x4
网格被细分多少次以及细分发生的方式是随机确定的。
视觉上看起来像这样：
此类数据可以用 quad tree 表示。
我的问题是：
如果我尝试使用尽可能少的字节来表示上图，线性四叉树是否是最有效的方法？
我能想到的唯一其他选择是制作图形的所有可能组合，并使用单个数字表示每个组合。
所以对于图形有 4 个级别的分支（32x32、16x16、8x8、4x4）这会给我们 4^0 + 4^1 + 4^2 + 4^3 可能的组合，等于 85组合。
因此，我能想到的存储图形的最小方法是使用 7 位（1010101 是二进制数字 85）来表示可能的组合。
在存储效率方面 Linear Quadtrees 会等于这个，还是会占用更多或更少 space？
我一般不回答我自己的问题，但看到这个问题仍然有意见没有回应我会给出我的答案。
经过将近 2 天的研究，我现在对什么是线性四叉树有了更好的理解。
线性四叉树只是按特定遍历顺序编写的四叉树的数组表示。
基本上只需选择您要读取四叉树的特定 "order" 并按该顺序保存它的值。
因此，例如，在问题中使用的图表中，有 4 层堆栈，因为有 4 种块大小（32、16、8、4）。
每一叠都可以按顺序阅读。
所以假设整个图都填充了一个 32x32 的块，树的 "root"（我们读取的第一个节点）将填充一个“1”来表示我们需要那个块，而所有根的子节点将为“0”，因为不再需要块，因为图已满。
所以线性四叉树在二进制中看起来像这样“10000000000000....（84 个 0）”
这显然比我在问题中提到的 7 位要多，但那是因为没有对这个线性四叉树应用压缩。
我真的问错了。你需要线性四叉树来表示四叉树，所以我真的应该被问到 "What is the best way to compress a linear quad tree"，我在问题中给出的想法是最好的方法。
创建一个包含所有不同四叉树组合的查找 table，并使用一个数字来表示每个组合。
假设您有一个 32x32 的网格，可以使用以下任何块大小随机细分：
32x32、16x16、8x8、4x4
网格被细分多少次以及细分发生的方式是随机确定的。
视觉上看起来像这样：
此类数据可以用 quad tree 表示。
我的问题是：
如果我尝试使用尽可能少的字节来表示上图，线性四叉树是否是最有效的方法？
我能想到的唯一其他选择是制作图形的所有可能组合，并使用单个数字表示每个组合。
所以对于图形有 4 个级别的分支（32x32、16x16、8x8、4x4）这会给我们 4^0 + 4^1 + 4^2 + 4^3 可能的组合，等于 85组合。
因此，我能想到的存储图形的最小方法是使用 7 位（1010101 是二进制数字 85）来表示可能的组合。
在存储效率方面 Linear Quadtrees 会等于这个，还是会占用更多或更少 space？
我一般不回答我自己的问题，但看到这个问题仍然有意见没有回应我会给出我的答案。
经过将近 2 天的研究，我现在对什么是线性四叉树有了更好的理解。
线性四叉树只是按特定遍历顺序编写的四叉树的数组表示。
基本上只需选择您要读取四叉树的特定 "order" 并按该顺序保存它的值。
因此，例如，在问题中使用的图表中，有 4 层堆栈，因为有 4 种块大小（32、16、8、4）。
每一叠都可以按顺序阅读。
所以假设整个图都填充了一个 32x32 的块，树的 "root"（我们读取的第一个节点）将填充一个“1”来表示我们需要那个块，而所有根的子节点将为“0”，因为不再需要块，因为图已满。
所以线性四叉树在二进制中看起来像这样“10000000000000....（84 个 0）”
这显然比我在问题中提到的 7 位要多，但那是因为没有对这个线性四叉树应用压缩。
我真的问错了。你需要线性四叉树来表示四叉树，所以我真的应该被问到 "What is the best way to compress a linear quad tree"，我在问题中给出的想法是最好的方法。
创建一个包含所有不同四叉树组合的查找 table，并使用一个数字来表示每个组合。