python - 如何在 python 中用相等的非重叠正方形近似覆盖一个(不一定是凸的)多边形？

Question

我无法为我想要的东西提出一个明确定义的优化目标，但希望我可以通过一些例子来传递我对我想要的东西的主观感受。

方 block 的大小始终相同(例如 1000x1000)。多边形可能具有不同的大小。有时多边形可能大到足以容纳一个或多个正方形，有时多边形可能足够小以至于可以容纳在正方形内。在后一种情况下，一个正方形应以多边形的质心为中心。在前一种情况下，一个或多个不重叠的正方形应该或多或少地覆盖多边形。不覆盖多边形的整个区域是可以的。例如，如果您需要在边界附近放置一个正方形以覆盖剩余的一小块未覆盖区域，那么您不应该这样做，因为正方形的大部分都在多边形之外，您将花费一个正方形来小幅增加覆盖面积。

具有或多或少预期解决方案的示例:

小多边形:

大多边形:

请注意，在小多边形的情况下，可以浪费大量正方形的区域，因为我们至少需要一个正方形。但是在大多边形的情况下，大量的正方形区域被浪费是不好的。

我知道我的规范定义不明确，但我希望有人能猜出我想要什么，也许可以更好地定义目标。

如果有人可以用 python 显示一些代码来解决它，那就太好了。如果你使用 shapely 会更好，但这不是必需的。

多边形由一系列点 (x,y) 定义，这些点按照它们在列表中出现的顺序连接。

谢谢!

编辑:不应旋转正方形。

Answer 1

这将生成多边形 poly 的覆盖层。

import numpy as np
from shapely.geometry import MultiPoint, MultiPolygon, Polygon

def square(x, y, s):
    return Polygon([(x, y), (x+s, y), (x+s, y+s), (x, y+s)])

poly = MultiPoint(np.random.randn(10,2)).convex_hull
grid_size = 0.5
ibounds = np.array(poly.bounds)//grid_size
ibounds[2:4] += 1
xmin, ymin, xmax, ymax = ibounds*grid_size
xrg = np.arange(xmin, xmax, grid_size)
yrg = np.arange(ymin, ymax, grid_size)
mp = MultiPolygon([square(x, y, grid_size) for x in xrg for y in yrg])
solution = MultiPolygon(list(filter(poly.intersects, mp)))