Joh*_*rak 37
我不知道你的意思是"尝试每一个可能的轮换",因为它们中有无数的,但这个基本思想实际上产生了一个非常有效的解决方案:
第一步是计算凸包.实际节省多少取决于数据的分布,但对于从单位磁盘统一选取的点,船体上的点数预计为O(n ^ 1/3).有很多方法可以做到这一点:
- 如果点已经按其坐标之一进行排序,则Graham扫描算法在O(n)中进行.对于给定顺序中的每个点,将其连接到船体中的前两个点,然后移除新船体上的每个凹点(唯一的候选者是与新点相邻的那些).
- 如果点未被排序,则礼品包装算法是在O(n*h)处运行的简单算法.对于从输入的最左侧点开始的船体上的每个点,检查每个点以查看它是否是船体上的下一个点.
h是船体上的点数. - Chen的算法承诺O(n log h)性能,但我还没有完全探究它是如何工作的.
- 另一个类似的想法是通过方位角对点进行排序,然后去除凹点.然而,这一开始只看起来像O(n + sort),但我恐怕实际上并非如此.
在这一点上,检查到目前为止收集的每个角度都应该足够了(由我和Oliver Charlesworth共同完成,并且Evgeny Kluev为此提供了证据的要点).最后,让我参考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).如果需要,将该区域翻译成笛卡尔形式,留给读者练习.
Lio*_*gan 28
已经证明,一组点的最小面积矩形与集合的凸包多边形的一个边缘共线["确定任意闭合曲线的最小面积包含矩形" [Freeman,Shapira 1975]
这个问题的O(nlogn)解决方案发表在"关于计算最小包围矩形和设置直径" [Allison,Noga,1981]
一个简单而优雅的O(n)解决方案发表在"包含凸多边形的最小面积矩形的线性时间算法" [Arnon,Gieselmann 1983]中,当输入是凸包时(构造凸包的复杂性相等)对输入点进行排序的复杂性).该解决方案基于Shamos,1978中描述的旋转卡尺方法.这里有在线演示.