用正方形填充不规则形状而不重叠

Question

我有不规则的形状（想想地理边界），我需要用一组不同大小的正方形填充，而不重叠。应优先考虑使用尽可能大的正方形。到目前为止，我的方法是以增量循环图像的长度/宽度，并检查 (x,y) 处的正方形是否有效。如果是这样，请将方块保存在那里并将该区域标记为无效。然后我对我拥有的每个正方形尺寸重复该过程。它做了我想要的事情，但对于实际的小增量来说太慢了。如果我尝试在每个正方形维度上使用 else/if 一次性完成此操作，则最小的正方形将占主导地位。我也不能保证正方形大小的最优性。

nim[mask] = .5
nim[~mask] = 0
cim = nim.copy()

inc = 500
dims = [4000, 2000, 1000, 500]

regions = []
for d in dims:
    for x in range(0, nim.shape[0], inc):
        for y in range(0, nim.shape[1], inc):
            if (np.count_nonzero(cim[x:x+d, y:y+d])/(d*d) < .0001):
                nim = rect(nim, y, x, d, d, 1)
                cim = blocc(cim, y, x, d, d, 1)
                regions.append([x,y,d])
                
plt.imshow(nim)
plt.show()

其中 rect() 和 blocc() 分别绘制区域和填充区域的边。

Answer 1

解决该问题的一种方法是：
A) 创建最大正方形的网格
B) 为网格找到合适的位置，以及
C) 细分未完全位于形状内部的正方形。

第一步是用最大的正方形网格覆盖形状。下面显示了一个示例。绿色方块完全位于形状内，黄色方块部分位于形状外部，红色方块完全位于形状外部。

第二步是找到网格的最佳位置。将最小的正方形定义为 1x1 单位，最大的正方形定义为 8x8 单位，则网格有 64 种可能的放置方式。网格的最佳放置位置可以最大化绿色方块的数量。给定两个具有相同数量绿色方块的位置，选择更好位置的标准是

• 最小化黄色方块的数量，或者
• 将绿色方块大致放在形状的中心

一旦网格布局确定，绿色方块将保持原样，红色方块将被丢弃，黄色方块将被细分为四个较小的方块。这是一个黄色正方形被细分的示例：

同样的规则适用：保留绿色，丢弃红色，细分黄色。细分正方形的过程递归地继续，直到达到最小尺寸的正方形。

最终结果如下所示：