用矩形填充多边形

Question

我有一个相当平滑的多边形，比如一个椭圆形，凸起和凹痕转换为多边形直线。我想用尽可能少的矩形填充这个多边形，但是尽可能多地保持多边形中小角部的精度。矩形可以是任何大小，任何数量。

这样做的原因是在多边形上的网页上进行命中测试。唯一可行的方法是用div填充它，并对所有div进行打击测试。

当然，对于任何矩形都会有一个最小的方形尺寸，以免我们不仅仅逼近多边形并用像素尺寸矩形重新创建它。

Answer 1

在一般情况下，如果要确切地说表示具有矩形的数字形状，则至少需要与轮廓成形拐角上的像素一样多的矩形。如果您想到45°的数字直边，那意味着每个像素一个矩形。这是一个严重的限制。 （并且甚至不考虑非数字形状）。

这就是说，您接受近似具有某种错误的形状，并且我建议您首先将形状缩小一个常数因子，直到您：你将在形状上叠加一个网格，决定每个瓦片是否属于该形状。做到这一点，你可以用“大像素”将你的形状变成二进制图像，现在的挑战是将这个图像分解成矩形（正是这一次）。

我建议一个简单的贪婪策略，以便您尝试找到完全适合的大矩形，然后重复剩下的部分。

如果您对较大和较大的矩形结构元素应用morphological erosion操作，则会找到适合形状图像的最大矩形。理论上，你应该尝试所有宽度和高度的组合，并保持最大面积或周长;这是一项大量的工作。我会建议先尝试使用正方形，并且当你找到最大的正方形继续朝着允许的方向继续时。

找到大矩形后，将其从形状图像中清除并重新开始，直至完全擦除。