Linear Quadtree是否是存储32×32随机细分网格的最高效方式？

Let's break down the storage tradeoffs between these two approaches for representing a randomly subdivided 32×32 grid:

First, Let's Clarify Both Schemes #

7-bit Enumerated Scheme #

The 85 possible combinations come from summing all distinct block sizes and their unique positions in the 32×32 grid:

• 1 single 32×32 block
• 4 distinct 16×16 blocks
• 16 distinct 8×8 blocks
• 64 distinct 4×4 blocks

Since 85 is less than 2⁷ (128), each final leaf block can be uniquely identified with a 7-bit integer. This uses a fixed-size encoding per leaf block.

Linear Quadtree #

Linear Quadtrees store leaf blocks in a sequential order (like Morton/Z-order) with metadata to define each block's position and size. For our 32×32 grid, we can use variable-length encoding to optimize space:

• A 32×32 block only needs a 2-bit level identifier (since we have 4 possible block sizes)
• A 16×16 block needs 2 bits (level) + 2 bits (position, to pick from 4 total blocks) = 4 bits
• An 8×8 block needs 2 bits (level) + 4 bits (position, to pick from 16 total blocks) = 6 bits
• A 4×4 block needs 2 bits (level) + 6 bits (position, to pick from 64 total blocks) = 8 bits

Alternatively, we could use a fixed 8-bit size per block for simpler storage, but that wastes bits on larger blocks.

Storage Efficiency Comparison #

Let's compare across common scenarios:

1. Best-Case Scenario (Entire Grid as One 32×32 Block) #

• 7-bit Scheme: 7 bits (rounded up to 1 byte in practice)
• Linear Quadtree: 2 bits (rounded up to 1 byte)
  Both use the same amount of space in real-world storage, though the Linear Quadtree uses fewer raw bits.

2. Worst-Case Scenario (Full Subdivision to 4×4 Blocks) #

• 7-bit Scheme: 64 blocks × 7 bits = 448 bits = 56 bytes
• Linear Quadtree: 64 blocks × 8 bits = 512 bits = 64 bytes (even with variable-length encoding, no savings here)
  The 7-bit scheme is clearly more efficient for heavily subdivided grids.

3. Mid-Tier Subdivisions #

• All 16×16 blocks:
  • 7-bit Scheme: 4 blocks ×7 bits = 28 bits (~4 bytes)
  • Linear Quadtree: 4 blocks ×4 bits =16 bits (~2 bytes)
    Linear Quadtree has a clear edge here.
• All 8×8 blocks:
  -7-bit Scheme:16×7=112 bits (~14 bytes)
  -Linear Quadtree:16×6=96 bits (~12 bytes)
  Linear Quadtree still uses less space.

4. Random Subdivision (Average Case) #

Assuming a 50% chance of subdividing any block (a balanced random scenario):

• Expected number of leaf blocks: ~11.5
• 7-bit Scheme: 11.5×7=80.5 bits (~11 bytes)
• Linear Quadtree: Using variable-length encoding, expected total bits are ~81 bits (~11 bytes)
  The two schemes are nearly identical in average storage usage.

Key Takeaways #

• Linear Quadtree is more efficient when the grid has larger, fewer leaf blocks (variable-length encoding saves bits for bigger blocks).
• The 7-bit enumerated scheme wins when the grid is heavily subdivided into small 4×4 blocks (fixed 7 bits per block is shorter than the 8 bits needed for 4×4 blocks in a Linear Quadtree).
• For random subdivisions with balanced odds of splitting, their storage efficiency is almost identical.

内容的提问来源于stack exchange，提问作者YAHsaves