我想取一个凸多边形并通过转动和缩放将其放入给定的矩形中。
我的方法是以小步长（如 1°）转动多边形并始终测量分数（最大水平距离/最大垂直距离），取最接近分数的那个（矩形宽度/矩形高度）并将其缩放以适应进入矩形。
我想知道是否有一种“不那么原始”的方法。此外，“最佳拟合”的定义可能比仅测量最大水平和垂直距离更好。我的真正目标是让多边形“看起来不错”，当我将它存储为图像文件或将其打印在页面上时。
问问题
449 次
1 回答
3
您可以使用旋转卡尺等方法。
虽然旋转卡尺算法找到具有两条平行线的对映顶点对，但您需要四条垂直线 - 边界矩形。
选择第一个顶点，为它找到对映顶点——它是第一个卡尺对。
建立垂直于第一个卡尺对的第二对卡尺。
一起旋转两个卡尺对，直到找到下一个对映对（在第一个卡尺之间，或在第二个卡尺之间） - 您确定下一个极值角点。
继续旋转卡尺。
边界矩形的宽度和高度将在极值点之间连续变化。并且宽度/高度比例也会连续。因此，如果你发现在第 i 个极值点 W/H < P 和第 (i+1) 个极值点 W/H > P，其中 P 是需要的比例，那么区间 i..i+1 包含需要的 P值（博尔扎诺定理）。
当您找到解的区间（如果存在）时，只需计算此角度区间（三角方程）处的卡尺宽度比例并获得准确的角度值。三角方程看起来像
Sin(A) / Sin(A + Pi/2) = F
or
Sin(A) / Cos(A) = Tan(A) = F
于 2016-06-25T12:00:39.737 回答