同一种地形占据大片区域时,可以用一个方块记录它,不必逐格重复。四叉分块会把混合区域继续分成四个相同大小的正方形,直到每个叶子块内部完全一致。
先固定规则和输入
地图为八乘八,只含零和一。先检查整图,若颜色混合就按左上、右上、左下、右下顺序分成四块;同色块停止细分,最小块是一格。每个叶子记录左上坐标、边长与值。
原图八行 10000000 00100000 00000000 10000011 11000011 00110011 00111011 00000000 全部叶子[左,上,边长,值] [[0, 0, 1, 1], [1, 0, 1, 0], [0, 1, 1, 0], [1, 1, 1, 0], [2, 0, 1, 0], [3, 0, 1, 0], [2, 1, 1, 1], [3, 1, 1, 0], [0, 2, 1, 0], [1, 2, 1, 0], [0, 3, 1, 1], [1, 3, 1, 0], [2, 2, 2, 0], [4, 0, 2, 0], [6, 0, 2, 0], [4, 2, 2, 0], [6, 2, 1, 0], [7, 2, 1, 0], [6, 3, 1, 1], [7, 3, 1, 1], [0, 4, 1, 1], [1, 4, 1, 1], [0, 5, 1, 0], [1, 5, 1, 0], [2, 4, 1, 0], [3, 4, 1, 0], [2, 5, 1, 1], [3, 5, 1, 1], [0, 6, 2, 0], [2, 6, 1, 1], [3, 6, 1, 1], [2, 7, 1, 0], [3, 7, 1, 0], [4, 4, 2, 0], [6, 4, 2, 1], [4, 6, 1, 1], [5, 6, 1, 0], [4, 7, 1, 0], [5, 7, 1, 0], [6, 6, 1, 1], [7, 6, 1, 1], [6, 7, 1, 0], [7, 7, 1, 0]]
把结果按步骤记下来
查询1点[5, 2],命中叶子[左,上,边长,值][4, 2, 2, 0],读回0;这个块覆盖4个同色格,坐标比较使用右下边界不包含的规则。
查询2点[2, 1],命中叶子[左,上,边长,值][2, 1, 1, 1],读回1;这个块覆盖1个同色格,坐标比较使用右下边界不包含的规则。
查询3点[1, 0],命中叶子[左,上,边长,值][1, 0, 1, 0],读回0;这个块覆盖1个同色格,坐标比较使用右下边界不包含的规则。
查询4点[0, 2],命中叶子[左,上,边长,值][0, 2, 1, 0],读回0;这个块覆盖1个同色格,坐标比较使用右下边界不包含的规则。
查询5点[3, 5],命中叶子[左,上,边长,值][3, 5, 1, 1],读回1;这个块覆盖1个同色格,坐标比较使用右下边界不包含的规则。
查询6点[5, 7],命中叶子[左,上,边长,值][5, 7, 1, 0],读回0;这个块覆盖1个同色格,坐标比较使用右下边界不包含的规则。
查询7点[0, 3],命中叶子[左,上,边长,值][0, 3, 1, 1],读回1;这个块覆盖1个同色格,坐标比较使用右下边界不包含的规则。
查询8点[5, 3],命中叶子[左,上,边长,值][4, 2, 2, 0],读回0;这个块覆盖4个同色格,坐标比较使用右下边界不包含的规则。
总计43个叶子,面积相加64格。记录数下降多少只是结构观察,实际字节数还取决于保存方式。
自己复核的办法
还原所有叶子后,每格应该恰好被覆盖一次,而且颜色与原图完全相同。四个同色兄弟若可以合成父块却仍被拆开,就不是本例要求的最简分块。
建议先遮住结果,用本例原始输入独立完成一遍,再逐项对照。若出现差异,先找最早不一致的位置,检查索引从零还是从一开始、边界是否包含,以及比较或更新发生的先后。只比较最后一个数,往往无法分辨规则理解与计算步骤分别出了什么问题。
使用这个练习的边界
叶子少并不自动意味着实际文件更小,每块还要存坐标、尺寸或树结构。本文只比较叶子记录数量与六十四格的数量,不声称某种编码能节省固定比例的字节。
