寻找凸多边形的最小面积矩形
Finding a minimum area rectangle of a convex polygon
我正在寻找一种找到凸多边形的最小面积矩形的有效方法。
运行 时间应该是 O(n)，其中 n 是顶点数。
找到一般多边形的边界框有一个复杂的算法，但对于凸多边形应该有一个更简单的算法。
一个凸多边形如何轻松完成？
谢谢。
旋转卡尺是您最好的朋友。
最紧密的边界矩形是它的一条边与多边形的一条边重合。所以，
从任意边开始，旋转多边形，使该边水平，在底部；
分别求出使Y、-X、X最大化的三个顶点（图中4、6、3）。这样，您将获得一个边界框；
然后顺时针移动到下边，调整旋转；
通过更新maxima找到接下来的三个顶点（按照轮廓在Y减小之前停止；同-X和X；图中4->5,6->6和3->3);
对于每个位置，计算面积并保留最好的。转一圈后停下来。
重要的是要认识到您不会将旋转应用到所有顶点，而是仅在需要时应用。要获得初始边界框，您需要处理 O(N) 个顶点，但 N-1 次更新仅需要 O(N) 次额外工作（摊销），并且您不必计算两个坐标。
我正在寻找一种找到凸多边形的最小面积矩形的有效方法。
运行 时间应该是 O(n)，其中 n 是顶点数。
找到一般多边形的边界框有一个复杂的算法，但对于凸多边形应该有一个更简单的算法。
一个凸多边形如何轻松完成？
谢谢。
旋转卡尺是您最好的朋友。
最紧密的边界矩形是它的一条边与多边形的一条边重合。所以，
从任意边开始，旋转多边形，使该边水平，在底部；
分别求出使Y、-X、X最大化的三个顶点（图中4、6、3）。这样，您将获得一个边界框；
然后顺时针移动到下边，调整旋转；
通过更新maxima找到接下来的三个顶点（按照轮廓在Y减小之前停止；同-X和X；图中4->5,6->6和3->3);
对于每个位置，计算面积并保留最好的。转一圈后停下来。
重要的是要认识到您不会将旋转应用到所有顶点，而是仅在需要时应用。要获得初始边界框，您需要处理 O(N) 个顶点，但 N-1 次更新仅需要 O(N) 次额外工作（摊销），并且您不必计算两个坐标。