algorithm - 谁能给我解释一下旋转卡尺？

Question

我正在努力计算一组点的最小外接矩形(任意对齐)。

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

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

Answer 1

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

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

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

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

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

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