java - 将凸多边形拟合到给定的矩形中

Question

我想取一个凸多边形并通过旋转和缩放将其放入给定的矩形中。

我的方法是小步转动多边形(如 1°)并始终测量分数(最大水平距离/最大垂直距离)，取最接近分数(矩形宽度/矩形高度)的那个并缩放它适合矩形。

我想知道是否有一种“不那么原始”的方法。此外，“最适合”的定义可能比仅测量最大水平和垂直距离更好。当我将多边形存储为图像文件或将其打印在页面上时，我的真正目标是使多边形“看起来不错”。

Answer 1

您可以使用类似rotating calipers 的方法.

虽然旋转卡尺算法找到具有两条平行线的对映顶点对，但您需要四条垂直线 - 边界矩形。

选择第一个顶点，找到它的对映顶点——它是第一个卡尺对。
构建与第一对垂直的第二对卡尺。
一起旋转两个卡尺对，直到找到下一个对映体对(在第一个卡尺之间，或在第二个卡尺之间)——您确定下一个极值角点。
继续旋转卡尺。

边界矩形的宽度和高度将在极值点之间连续变化。宽度/高度比例也会连续。所以如果你发现在第i个极值点W/H < P和第(i+1)个极值点W/H > P，其中P是需要的比例，那么区间i..i+1包含需要的P值(Bolzano's theorem)。

当您找到带解的区间(如果存在)时，只需计算该角度区间(三角方程)的卡尺宽度比例，并获得精确的角度值。三角方程看起来像

Sin(A) / Sin(A + Pi/2) = F   
or
Sin(A) / Cos(A) = Tan(A) = F