适合点的矩形
我试图围绕一组8个2D点拟合一个矩形，同时尽量减less覆盖面积 。
例：
矩形可以被缩放和旋转。 但是，它需要保持一个矩形。
我的第一个方法是强制每一个可能的旋转，尽可能接近矩形，并计算覆盖面积。 那么最适合的将是最小面积的旋转。
但是，这听起来不是最好的解决scheme。
有没有更好的方法来做到这一点？
我不知道你的意思是“尝试每一个可能的轮换”，因为其中有无数的轮转，但这个基本的想法实际上产生了一个非常有效的解决scheme：
第一步是计算凸包。 这实际上节省多less取决于你的数据分布，但是从单位磁盘上统一拾取的点，船体上的点数预计为O（n ^ 1/3） 。 有很多方法可以做到这一点 ：
- 如果点已经按其坐标之一sorting，Graham扫描algorithm在O（n）中执行。 对于给定顺序中的每一点，将其连接到船体中的前两个点，然后移除新船体上的每个凹点（唯一的候选点是那些与新点相邻的点）。
- 如果点没有sorting，礼物包装algorithm是一个简单的algorithm，运行在O（n * h）。 对于从input的最左边开始的船体上的每个点，检查每个点以查看它是否是船体上的下一个点。
h是船体上的点数。 - 陈的algorithm承诺O（N日志）性能，但我还没有完全探索它是如何工作的。
- 另一个微笑的想法是将他们的方位点sorting，然后删除凹面。 不过，起初这似乎只是O（n +sorting），但恐怕事实上并非如此。
在这一点上，检查到目前为止所收集到的每一个angular度都应该足够了（我和奥利弗·查尔斯沃思（Oliver Charlesworth）都赞同，而叶夫根尼·克鲁夫（Evgeny Kluev）为此提供了证据 。 最后，让我参考Lior Kogan的回答中的相关参考。
对于每个方向，边界框由该间隔中的每个angular度相同的四个（不一定是不同的）点定义。 对于候选人的方向，你至less有一个任意的select。 find这些点可能看起来像一个O（h ^ 2）任务，直到您意识到轴alignment边界框的极值与您开始合并的极端相同，且连续区间的极值点相同或连续。 让我们按照顺时针顺序将极值点A,B,C,D称为边界框a,b,c,d并将边界框的边界划分为a,b,c,d 。
所以，我们来做math。 边界框区域由|a,c| * |b,d| |a,c| * |b,d| 。 但|a,c| 只是投影到矩形方向上的vector(AC) 。 设u是平行于a和c的向量，令v是垂直向量。 让他们在整个范围内顺利变化。 在vector说法中，区域变成((AC).v) / |v| * ((BD).u) / |u| ((AC).v) / |v| * ((BD).u) / |u| = {((AC).v) ((BD).u)} / {|u| |v|} {((AC).v) ((BD).u)} / {|u| |v|} 。 让我们也selectu = (1,y) 。 那么v = (y, -1) 。 如果u是垂直的，这就构成了一个涉及极限和无限的轻微问题，所以让我们在这种情况下selectu是水平的。 为了数值的稳定性，让我们每旋转90° (1,-1)..(1,1) 。 如果需要，将该区域翻译为笛卡尔forms，作为读者的练习。
已经certificate，一组点的最小面积矩形与集合的凸包多边形的一个边缘共线[“确定任意闭合曲线的最小面积包围矩形” [Freeman，Shapira 1975]
这个问题的O（nlogn）解决scheme发表在“关于最小包围矩形和设置直径的计算” [Allison，Noga，1981]
当input是凸包（ 构造凸包的复杂度是相等的）时，一个简单而优雅的O（n）解被发表在“包含凸多边形的最小面积矩形的线性时间algorithm” [Arnon，Gieselmann 1983]到sortinginput点的复杂性）。 该解决scheme基于Shamos，1978中描述的旋转卡尺方法。 在线演示可在这里find 。
当我看到这个问题时，他们首先想到的就是使用主成分分析。 我猜想最小的矩形是满足两个条件的那个：边与主轴平行，并且至less四个点位于边（有界点）上。 应该有一个n维的扩展。
