适应点周围的矩形

Question

我正在尝试在一组8个2D点周围放置一个矩形，同时试图最小化覆盖面积。

示例：

该矩形可以缩放和旋转。但是它必须仍然保持为矩形。

我的第一种方法是暴力枚举每个可能的旋转，尽可能贴近拟合矩形，并计算覆盖面积。最佳拟合将是具有最低区域的旋转。

然而，这并不像最佳解决方案。

是否有更好的方法来解决这个问题？

- tobspr

---

我希望能找到一个更好的解决方案，而不是一种蛮力方法。 - tobspr

在帧之间缓存凸包不就足够了吗？ - John Dvorak

我的直觉告诉我相反的情况会发生；凸包的一条边将成为最小矩形的一部分。不过我还无法证明它…… - Oliver Charlesworth

@MrSmith42 我建议你尝试将边界框与顶部两个点对齐。 - John Dvorak

计算凸包；对于凸包方向模90度之间的每个角度范围，矩形由相同的四个点限定。找到相应面积函数的最小值（其形式事先已知），取最低的最小值。 - John Dvorak

Answer 1

我不知道你所说的“尝试每种可能的旋转”是什么意思，因为它们有无限多个，但这个基本想法实际上可以产生非常高效的解决方案：

第一步是计算凸包。这实际上节省了多少取决于数据的分布，但是对于从单位圆中均匀选择的点，期望凸包上的点数为O(n^1/3)。有许多方法可以完成这项任务：

• 如果点已经按照其中一个坐标排序，Graham扫描算法可以在O(n)时间内完成。对于给定顺序中的每个点，将其连接到凸壳中的前两个点，然后删除新凸壳上的每个凹点（唯一的候选者是相邻的新点）。
• 如果点没有排序，则gift-wrapping算法是一个简单的算法，运行时间为O(n*h)。从输入的最左边的点开始，对凸包上的每个点，检查每个点以查看它是否是下一个凸包上的点。h是凸包上的点数。
• Chen's algorithm承诺O(n log h)的性能，但我还没有完全探索它的工作原理。
• _{另一个简单的想法是按方位角对点进行排序，然后删除凹点。然而，这似乎只是O(n+sort)，但我担心实际上并不是这样。}

此时，检查迄今收集的每个角度应该足够（由我和Oliver Charlesworth共同推测，并由Evgeny Kluev提供了一个证明要点链接1）。最后，让我参考Lior Kogan的答案中相关的参考资料。

对于每个方向，边界框由该区间内每个角度的相同四个（不一定不同）点定义。对于候选方向，您将至少有一个任意选择。找到这些点可能看起来像是O(h ^ 2)的任务，直到你意识到轴对齐边界框的极限与您开始合并的极限相同，并且连续的区间具有其极端点相同或连续。让我们按顺时针顺序称极端点为A、B、C、D，称限制边界框的相应线条为a、b、c、d。

那么，让我们做数学运算。边界框面积由|a，c| * |b，d|给出。但是|a，c|只是投影到矩形方向上的向量(AC)。让u成为平行于a和c的向量，v成为垂直向量。让它们在范围内平稳变化。在向量用语中，区域变为((AC).v) / |v| * ((BD).u) / |u| = {((AC).v)((BD).u)} / {|u||v|}。让我们还选择u = (1，y)。然后v = (y,-1)。如果u是垂直的，则这会带来一个涉及极限和无限的小问题，因此在那种情况下，让u水平。为了数值稳定性，让我们每隔一个u旋转90°，其在(1,-1)..(1,1)之外。如果需要，将该区域转换为笛卡尔形式留给读者作为练习。

- John Dvorak

Answer 2

已经证明，一组点的最小区域矩形与该集合的凸包多边形的一条边共线。{{link1: ["确定任意封闭曲线的最小区域矩形"]}[Freeman, Shapira 1975]}

这个问题的O(nlogn)解法发表在{{link2:"关于计算最小外接矩形和集合直径"}[Allison, Noga, 1981]}中。

当输入为凸包时（构建凸包的复杂度等于对输入点进行排序的复杂度），"A Linear time algorithm for the minimum area rectangle enclosing a convex polygon" [Arnon, Gieselmann 1983] 发布了一种简单而优雅的O(n)解决方案。该解决方案基于 Shamos, 1978 中描述的 Rotating calipers 方法。在线演示可在 此处 查看。

- Lior Kogan

Answer 3

当我看到这个问题时，首先想到的是使用主成分分析。我猜测最小的矩形应该满足两个条件：边缘与主轴平行，并且至少有四个点位于边缘上（被限制的点）。这个方法应该可以扩展到n维。

- polarise

---

啥？边缘与主轴平行？那为什么拟合的矩形还倾斜了呢？难道是我的显示器歪了？ - candied_orange

主轴不与您的显示器边缘平行，而是由点决定。 - polarise

啊，所以你定义边的方向...一点也不。:P - candied_orange

请参阅《3D游戏编程和计算机图形学数学基础》第8.1.1节（第212页及以后）。 - polarise