algorithm - 使用最少给定的矩形覆盖多边形线，同时保持她的连续性

Question

给定形成多边形线的点列表，以及矩形的高度和宽度，我如何找到>覆盖所有点所需的所有矩形的数量和位置？

矩形应该旋转并且可以重叠，但必须遵循折线的路径(一个矩形可以包含线的多个线段，但每个矩形必须包含与前一个矩形连续的线段。)

在可能的情况下，在矩形的最小边上进行交叉，我们将不胜感激。

到目前为止我找到的所有解决方案都不干净，这是我得到的结果:

您应该看到它在近乎平坦的情况下提供了良好的渲染，但在大路缘上重叠太多。如果前一个矩形被偏移，则可以清楚地删除一个矩形。

实际上，我沿线放置了一个以 width/2 为中心的矩形，并使用 convex hull 和修改的 rotating calipers 算法旋转它，并从前一个矩形和直线的交点开始重复。

您可能会注意到，我从最小定向矩形边界框算法中获得了方向的灵感，但它不包括切割方面，也不包括固定大小。

感谢您的帮助!

Answer 1

我修改了k-means解决这个问题。它不是很快，不是最优的，也不能保证，但是(恕我直言)这是一个好的开始。有两个重要的修改:

1- 距离度量

我用了 Chebyshev-distance -inspired measure 来查看点与每个矩形的距离。为了找到点到每个矩形的距离，首先我将所有点转换到一个新的坐标系，移动到矩形的中心并旋转到它的方向:

然后我使用这些转换后的点来计算距离:

d = max(2*abs(X)/w, 2*abs(Y)/h);

它将为距矩形各边距离相同的所有点提供相等的值。对于位于矩形内部的点，结果将小于 1.0。现在我们可以将点分类到它们最近的矩形。

2-更新聚类中心的策略

每个聚类中心都是 C(矩形中心)和 a(其旋转角度)的组合。在每次迭代中，新的一组点被分配给一个集群。在这里我们必须找到 C 和 a 以便矩形覆盖尽可能多的点。我现在不知道是否有分析解决方案，但我使用了统计方法。我使用点的加权平均值更新了 C，并使用了第一个 principal component 的方向要更新 a 的点数。我使用建议距离的结果，以 500 为幂，作为加权平均中每个点的权重。它将矩形移向位于其外部的点。

如何找到 K

从 1 开始并增加它，直到从点到其对应矩形的所有距离都小于 1.0，这意味着所有点都在矩形内。

结果

更新聚类中心(矩形)的第 0、10、20、30、40 和 50 次迭代:

测试用例 1 的解决方案:

尝试 Ks:2、4、6、8、10 和 12 以实现完整覆盖:

测试用例 2 的解决方案:

P.M: 我使用了 Chalous Road 的部分内容作为数据。从 Google Maps 下载它很有趣.我使用的技术描述了 here对一组等距点进行采样。