把相邻同类格子合并成矩形,可以用更少的区域描述同一张图。但合并时不能跨过空格,也不能因为形状接近就改变原始覆盖范围。
下面是一组独立的虚构游戏输入与逐步结果。先记录单位、编号和端点是否包含,再尝试自己推算,最后对照第一处差异。所有结论都以本例规则为前提;其他作品采用不同约定时,应按它自己的说明重新计算。
二值地图的一个表示需要绘制的格子。每行先找连续的一段段一格;只把相邻行中横向起止完全相同的段向下合并。矩形左上包含、右下排除;本规则保持覆盖,不承诺矩形数量全局最少。
八列六行,1为绘制格 [1, 1, 0, 0, 1, 1, 1, 0] [0, 0, 1, 0, 1, 1, 0, 1] [1, 1, 1, 1, 0, 0, 1, 0] [1, 0, 1, 0, 0, 0, 1, 1] [1, 1, 1, 1, 1, 1, 1, 0] [0, 1, 0, 0, 1, 1, 1, 0]
第0行[1, 1, 0, 0, 1, 1, 1, 0],横段[(0, 2), (4, 7)];本行结束的矩形[],仍可向下延续的矩形[[0, 0, 2, 1], [4, 0, 7, 1]]。
第1行[0, 0, 1, 0, 1, 1, 0, 1],横段[(2, 3), (4, 6), (7, 8)];本行结束的矩形[[0, 0, 2, 1], [4, 0, 7, 1]],仍可向下延续的矩形[[2, 1, 3, 2], [4, 1, 6, 2], [7, 1, 8, 2]]。
第2行[1, 1, 1, 1, 0, 0, 1, 0],横段[(0, 4), (6, 7)];本行结束的矩形[[2, 1, 3, 2], [4, 1, 6, 2], [7, 1, 8, 2]],仍可向下延续的矩形[[0, 2, 4, 3], [6, 2, 7, 3]]。
第3行[1, 0, 1, 0, 0, 0, 1, 1],横段[(0, 1), (2, 3), (6, 8)];本行结束的矩形[[0, 2, 4, 3], [6, 2, 7, 3]],仍可向下延续的矩形[[0, 3, 1, 4], [2, 3, 3, 4], [6, 3, 8, 4]]。
第4行[1, 1, 1, 1, 1, 1, 1, 0],横段[(0, 7)];本行结束的矩形[[0, 3, 1, 4], [2, 3, 3, 4], [6, 3, 8, 4]],仍可向下延续的矩形[[0, 4, 7, 5]]。
第5行[0, 1, 0, 0, 1, 1, 1, 0],横段[(1, 2), (4, 7)];本行结束的矩形[[0, 4, 7, 5]],仍可向下延续的矩形[[1, 5, 2, 6], [4, 5, 7, 6]]。
输出13个矩形[[0, 0, 2, 1], [0, 2, 4, 3], [0, 3, 1, 4], [0, 4, 7, 5], [1, 5, 2, 6], [2, 1, 3, 2], [2, 3, 3, 4], [4, 0, 7, 1], [4, 1, 6, 2], [4, 5, 7, 6], [6, 2, 7, 3], [6, 3, 8, 4], [7, 1, 8, 2]],总覆盖29格。
将输出矩形逐格展开,计数应与原图完全一致,每个一格恰覆盖一次、零格从不覆盖。还可对每一种横向段分别找连续出现的行区间,独立得到矩形。
本例只合并相同类型且没有额外属性的格子。不同纹理、透明顺序、光照或交互边界可能要求分开绘制。矩形变少也不自动保证实际帧率提高,渲染开销还受其他因素影响;这里首先验证几何等价。
测试时先保留输入和中间状态,再只改变一个条件。空状态、正好相等、重复出现和最后一步都值得单独检查。若最终结果不符,应从第一处偏差查起,而不是在末尾随意增加补偿让数字表面一致。