我正在努力计算一组点的最小外接矩形（任意对齐）。
使用 Graham 算法，我能够计算出凸包。
我卡在了下一步。我想使用旋转卡壳算法，但我似乎找不到足够详细的解释。
有人能向我解释一下旋转卡尺吗？
13
- mish
3
请查看这个解释。 - mbeckish
2你看过Toussaint的原始论文吗？第1页和第2页非常清楚地解释了算法（在我看来）。请注意，页码是反向的... - Bart Kiers
请在此处查看GIF：http://www-cgrl.cs.mcgill.ca/~godfried/research/calipers.html - Thomas Ahle
1个回答
11
如果您有凸包，则基本算法非常简单。您只需遍历凸包的每条边，并旋转您的点，使该边沿着一个主轴，比如X轴。然后，找到这些点的轴对齐边界框。选择最小的边界框。
可以通过获取每个维度的最小值和最大值来找到轴对齐的边界框。
如果您将边界框旋转相反的量，则现在它将围住原始点。
为了使其更加高效，请注意，唯一会影响边界框的点都在凸包上。
为了使其真正有效，请注意，在凸包周围只有四个点在任何时候与边界框接触（这不是严格正确的，但暂时忽略这一点）。如果您旋转点恰好足以使下一个边与边界框对齐，则其中三个点是相同的，并且其中一个点被替换为凸包周围的下一个点。这使您可以创建一个线性的算法，其数量与凸包上的点数成比例。
现在有特殊情况，两条边平行或垂直。这将导致超过四个点在任何时候都接触边界框，但实际上并不重要。如果您必须在两个平行边中选择下一个使用的边，则可以任意选择其中一个。
可以通过获取每个维度的最小值和最大值来找到轴对齐的边界框。
如果您将边界框旋转相反的量，则现在它将围住原始点。
为了使其更加高效，请注意，唯一会影响边界框的点都在凸包上。
为了使其真正有效，请注意，在凸包周围只有四个点在任何时候与边界框接触（这不是严格正确的，但暂时忽略这一点）。如果您旋转点恰好足以使下一个边与边界框对齐，则其中三个点是相同的，并且其中一个点被替换为凸包周围的下一个点。这使您可以创建一个线性的算法，其数量与凸包上的点数成比例。
现在有特殊情况，两条边平行或垂直。这将导致超过四个点在任何时候都接触边界框，但实际上并不重要。如果您必须在两个平行边中选择下一个使用的边，则可以任意选择其中一个。
- Vaughn Cato
6
这种方法唯一的问题是它的时间复杂度为O(n^2)，当凸包中有许多顶点时可能不太适用。 - mbeckish
@mbeckish: true -- 我已经加入了一些优化来扩展我的答案。也许将其视为一个带有优化的简单算法会更容易理解。 - Vaughn Cato
凸包周围只有四个点在任何时候接触边界框并不是真实的。假设凸包中不存在共线点，则边界框可以接触多达8个点。考虑凸包
(2,0), (3,0), (4,1), (4,2), (3,3), (2,3), (1,2), (1,1)，其中一个轴对齐的边界框（或者倾斜45度）接触所有点。 - Bart Kiers@BartKiers：没错。这是一种简化，使得算法更易于理解。我会尽力让它更清晰明了。 - Vaughn Cato
是的，抱歉有点追求严谨 :). 只是当我们开始简化计算几何相关算法时，如果忽略了某些边角情况，实现很可能会出现问题[当实现的算法遇到这些边角情况时]。 - Bart Kiers
3没问题，@BartKiers说：“没错，计算几何确实有很多角和边缘... :)” - Vaughn Cato
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接