python - 用圆圈覆盖不规则区域

Question

我有以下图像(掩模)，

我想用这样的圆形区域填充，

在这个特定的示例中，我使用 X 和 Y 方向的步骤手动创建了圆圈，并且仅当 95% 落在白色区域时才保留圆圈。但是我想最大化 map 的覆盖范围。我认为这可以通过随机生成圆心来实现，并旨在最大化覆盖范围。如果我可以进一步最大化使用面积，我不介意这些区域是否有一点重叠

对于如何解决这个问题有什么建议，或者是否有任何算法可以为我做到这一点？

Answer 1

这被称为 circle packing问题而且是出了名的困难。

如果您不关心确切的边界并希望最大化覆盖范围，则应该使用 hexagonal tiling这将为您提供约 90.69% 的覆盖率。

你可以这样做:

import numpy as np
from scipy import misc
import matplotlib.pyplot as plt

image = misc.imread('xZoI6.png')

ys, xs, _ = image.shape

x, y = np.meshgrid(np.arange(xs), np.arange(ys), sparse=True)

radius = 20.0

for i in range(int(-0.5 * ys / radius), int(xs / radius)):
    for j in range(int(ys / radius)):
        x0 = 2 * radius * (i + 0.5 * j)
        y0 = 2 * radius * np.sqrt(3)/2 * j

        r = np.sqrt((x - x0) ** 2 + (y - y0) ** 2)

        indicator = r < radius

        if np.any(image[indicator, 0] != 0):
            image[r < radius] = [255, 0, 0, 255]

plt.imshow(image)

给出: