algorithm - 有人可以向我解释旋转卡尺吗？

Question

我正在努力计算一组点的最小封闭矩形（任意对齐）。

我能够使用格雷厄姆算法计算凸包。

我被困的地方是下一步。我考虑过使用旋转卡尺方法，但我似乎无法找到对该算法的充分解释。

Answer 1

如果你有凸包，那么一个基本的算法很容易。您只需通过凸包的每个边缘并旋转您的点，使边缘沿着主轴，比如说 X 轴。然后你会找到这些点的轴对齐边界框。选择最小的边界框。

通过获取每个维度的最小值和最大值，可以找到一个轴对齐的边界框。

如果您将边界框旋转相反的量，它将包围您的原始点。

为了提高效率，请注意唯一可以影响边界框的点位于凸包上。

为了使其真正有效，请注意，在任何时候，凸包周围只有四个点与边界框接触（严格来说这不是真的，但暂时忽略它）。如果您将点旋转到刚好足以使下一条边与边界框对齐，则其中三个点是相同的，其中一个点将替换为凸包周围的下一个点。这使您可以创建一个算法，该算法在凸包上的点数上是线性的。

现在有两条边平行或垂直的特殊情况。这将导致超过四个点在任何时候接触边界框，但实际上并不重要。如果您可以选择接下来使用两条平行边中的哪一条，您可以任意选择一条。