我已经为这个看似简单的问题苦苦挣扎了很长一段时间。我得到了一组点（我已将其进一步简化为凸包），我的任务是找到一个包含所有点的矩形（不一定与轴对齐），周围没有额外的空间（所以它是紧贴在点周围）并具有最大可能的周长。找到最小的对我来说并不困难，但事实证明这是一个更难破解的坚果。在搜索最小边界矩形时，我可以假设矩形的一侧总是与船体的一侧对齐，但在这里我看不到任何这种情况。我错过了一些非常明显的东西吗？到目前为止，我能想到的唯一方法是测试对映点对是否可以投影到矩形的侧面并使用一些三角函数来最大化函数，但我只是在计算中迷失了自己。
提前致谢！
首先，计算点集的凸包。
现在，考虑旋转多边形并计算最小的封闭轴对齐矩形。请注意，顶部点、左侧点、右侧点和底部点将围绕凸包顺时针从一个顶点到下一个顶点。
你不能明确地尝试所有可能的角度。但是，您可以使用扫线技巧。但是，给定一个角度，您可以在将多边形旋转该角度后计算顶部、左侧、底部和右侧点以及顶部、左侧、底部和右侧点中的第一个点，以在您继续旋转多边形时更改身份多边形。所以你得到了一个角度范围，你当前选择的上、左、下和右是正确的；此外，您知道上、左、下和右的下一个正确选择是什么。
对于顶部、左侧、底部和右侧的每个合法选择，您最终必须在某个 theta 范围内计算固定 a 和 b 的 a*sin(theta) + b*cos(theta) 的最大值。回想一下三角函数 a*sin(theta) + b*cos(theta) = sqrt(a^2+b^2) cos(theta - arctan(b/a))。您在区间边界处评估函数，并且导数为零（在 arctan(b/a) 加上任何整数倍 pi 处）并且您是黄金。