如何计算任意凸多边形内固定宽高比的最大对齐矩形的宽高

不同凸多边形内符合要求的矩形样例如下：

首先默认对齐矩形指边与坐标轴对齐的矩形，你可以根据实际需求调整坐标系适配旋转对齐的场景。
我们先把固定宽高比的约束转化为单变量问题：设要求的宽高比为r = 目标宽度 / 目标高度，那么所有符合宽高比要求的矩形都可以统一表示为(x, y, s*r, s)，其中s是缩放系数，x、y是矩形左下角坐标，我们的核心目标就是找到最大的s，使得整个矩形完全落在给定的凸多边形内部。

利用凸多边形的特性可以大幅简化判断逻辑：

• 一个图形完全落在凸多边形内部的充要条件是，图形的所有点都满足凸多边形每条边对应的半平面约束（法向量指向多边形内侧的半平面）
• 对于任意给定的s，我们可以快速推导x和y的合法取值范围：将矩形的四个顶点代入每条边的半平面不等式，整理后可以得到x的上下界、y的上下界，所有边给出的约束取交集，如果交集非空，说明当前s是可行的。
• 由于s的可行域是连续的左闭区间（只要s₁可行，所有小于s₁的s都必然可行），所以可以直接用二分查找来快速定位最大的可行s，整体时间复杂度为O(n log(max_s))，n为凸多边形的顶点数，计算效率远高于通用的最大内接矩形求解算法。

1. 预处理凸多边形的所有边，生成每条边对应的半平面约束表达式
2. 确定二分查找的初始上下界：下界设为0，上界可以取凸多边形外接矩形的短边长度，保证不会超出多边形范围
3. 执行二分查找：每次取中间值s_mid，计算对应的x和y的可行域，如果可行域非空则向上收缩下界，否则向下收缩上界
4. 当二分的上下界差值小于你要求的精度阈值（比如1e-6）时终止迭代，此时的s就是最大缩放系数
5. 计算最终宽高：宽度w = s * r，高度h = s

如果你的对齐要求是矩形边和凸多边形的某条边对齐而非坐标轴对齐，只需要先把整个凸多边形做坐标系旋转变换，让对齐边和新坐标系的坐标轴平行，按上述方法计算完成后再旋转回去即可，逻辑完全通用。

内容的提问来源于stack exchange，提问作者grom