我正在寻找一个形状问题,我正在寻找一个比我能想出的更聪明的解决方案.
这是问题所在:
我有一组在笛卡尔网格上形成封闭形状的点,例如A(-1,0),B(1,0)和C(0,4),它们形成一个锐角三角形.
我以一种稍微不那么令人困惑的方式重写了这一点.采取上面的形状,想象你可以自由旋转它.我期待发现旋转,我们只考虑x轴,西部最东部和最东部点之间的距离最小.
当考虑到该距离以上的形状将是A和B之间的距离.虽然对于更有趣的形状,点之间的距离可能更短,我相信没有办法旋转上面的形状,使得西部和东部最多点小于A和B之间的距离.
到目前为止,我唯一的解决方案是绘制点,旋转1度,存储旋转键控的最大距离.冲洗重复并取最小的一个.这似乎有点笨拙,我知道必须有一个更加数学上合理的方法来解决这个问题.
有任何想法吗？
进行主成分分析并将主成分与y轴对齐.这将优化从每个点到y轴的"平均"平方距离(即x轴上的宽度).根据您的标准,这也许是最佳的或接近最优的.
请参阅:http://en.wikipedia.org/wiki/Principal_component_analysis
替代解决方案(最优解):
首先计算点的凸包.请注意,具有最大x宽度的两个点始终位于凸包中.
现在,对于凸包中的每个线段,找到最远的顶点并记下距离.找到最小距离的(线段,最远的顶点)对.最佳旋转是在垂直方向上对齐该线段的旋转.
复杂性:O(nlogn)对于凸壳部分和O(m^2)第二部分,其中m是凸壳上的点数.