正在寻找一种方法来找到填充二维矩阵占用区域所需的最小矩形数量？

Question

我正在尝试减少需要渲染的对象数量，以便“仅”填充二维矩阵的占用单元格。每个单元的占用都是二进制的，矩阵范围最多可达 512 x 512 个单元。独立渲染每个单元格是站不住脚的。 将占用的单元格分组为更易于管理的区域是我的主要目标。不需要找到矩形分组的绝对最小数量，但越少越好。

我最初认为迭代网格，然后根据相邻单元格的占用情况对相邻单元格进行分组将是解决此问题的最佳方法，但我一直在努力寻找高性能的解决方案。我试图避免 O(n^2) 类型的情况（也许这是不合理的，我不知道）。

我还考虑过迭代矩阵并从两个轴上的每个占用单元格到最近的未占用单元格“生长”一个矩形。虽然这工作得相当好，但它显然会生成超出需要的矩形。

我假设随机选择一个坐标，然后向各个方向向外“生长”一个矩形，会进一步减少所需矩形的数量，但我不知道这是否属实，而且我还没有提出一个好的测试为了它。

我一直在 Lua 中解决这个问题，但请随时以任何语言提供解决方案。

谢谢你， -SN

编辑：就上下文而言，矩阵是一个表，矩阵中的每个单元格都有自己的表，因此矩阵[x][y] = {占用= true/false}。矩阵中的每个坐标都有单元格数据，因此矩阵中不存在任何零间隙。

Answer 1

请尝试这个解决方案：

https://love2d.org/wiki/TileMerging