将非矩形图像分割成相同大小的块

Question

我正在寻找一种算法来将非矩形图像（即透明图像）分块为（例如）16x16像素大小的块。这些块可能重叠，但是目标是获得最小数量的块。

例

摘要

• 块必须大小相等
• 块可能重叠
• 目标是最小的矩形

先感谢您

Answer 1

这是套套的特例。您可以尝试整数程序求解器，但可能的块可能太多。整数程序将适合列生成/分支和价格，但这是一项先进的技术，需要一些实验才能使其正确。

我认为你可以使用一种贪婪算法做得很好，该算法重复选择覆盖尽可能多像素（包括一个边界像素）的块。