c++ - 围绕点拟合矩形

Question

我正在尝试围绕一组 8 个 2D 点拟合一个矩形，同时尝试最小化覆盖区域。

例子:

矩形可以缩放和旋转。但是它需要保持一个矩形。

我的第一种方法是暴力破解每个可能的旋转，使矩形尽可能接近，并计算覆盖面积。最佳拟合是面积最小的旋转。

但是，这听起来并不是最好的解决方案。

有没有更好的方法来做到这一点？

Answer 1

我不知道您所说的“尝试所有可能的旋转”是什么意思，因为它们有无数个，但这个基本想法实际上产生了一个非常有效的解决方案:

第一步是计算凸包。这实际上节省了多少取决于您的数据分布，但是 for points picked uniformly from a unit disk, the number of points on the hull is expected to be O(n^1/3) .有一个number of ways to do that :

• 如果点已经按它们的坐标之一排序，则格雷厄姆扫描算法会在 O(n) 中完成。对于给定顺序中的每个点，将其连接到船体中的前两个点，然后移除新船体上的每个凹点(唯一的候选点是与新点相邻的点)。
• 如果点未排序，则礼品包装算法是一个简单的算法，运行时间为 O(n*h)。对于从输入的最左侧点开始的船体上的每个点，检查每个点以查看它是否是船体上的下一个点。 h 是船体上的点数。
• Chen's algorithm promise O(n log h) 的性能，但我还没有完全探索它是如何工作的。
• _{另一个简单的想法是按方位角对点进行排序，然后删除凹点。但是，这乍一看似乎只是 O(n+sort)，但恐怕实际上并非如此。}

在这一点上，检查到目前为止收集的每个角度就足够了(正如我和 Oliver Charlesworth 所推测的那样，Evgeny Kluev offered a gist of a proof 也是如此)。最后，让我引用一下Lior Kogan's answer中的相关引用。 .

对于每个方向，边界框由该区间中每个角度的相同四个(不一定不同)点定义。对于候选方向，您至少可以做出一个任意选择。找到这些点可能看起来像一个 O(h^2) 任务，直到您意识到轴对齐边界框的极值与您开始合并的极值相同，并且连续间隔的极值点相同或连续.让我们按顺时针顺序将极值点称为A,B,C,D，并将界定边界框的相应线设为a,b,c,d。

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