固定最大宽度下旋转多边形以获取最小高度的求解问询

针对你提出的「固定宽度约束下旋转多边形以最小化高度」的问题，以下是基于计算几何优化的可行调整方案，覆盖凸多边形及一般简单多边形场景：

一、核心思路转换 #

放弃暴力枚举旋转角度的低效方式，转而通过临界角度划分+带约束的光滑函数优化解决问题：

• 多边形的宽度w(θ)和高度h(θ)随旋转角度θ的变化是分段光滑的，分段点对应多边形各边的法向量方向（此时投影极值对应的顶点会发生切换）。
• 将问题转化为：在w(θ) ≤ W的约束下，求解h(θ)的最小值，每个分段区间内可通过求导或解析方法找到极值点。

二、凸多边形场景的具体实现 #

1. 预处理临界角度
   计算多边形所有边的法向量方向（θ_k = arctan2(dy, dx)，其中dx = x_{i+1}-x_i，dy = y_{i+1}-y_i），将这些角度排序后划分[0, π)区间（旋转π与旋转0等价，无需重复计算）。

2. 逐区间分析可行域
   对每个区间[θ_start, θ_end]：

   • 确定该区间内，投影到θ方向的极值顶点p（max）和q（min），此时宽度可表示为：

     w(θ) = (x_p - x_q)cosθ + (y_p - y_q)sinθ = L·cos(θ - α)
     

     其中L = √((x_p-x_q)² + (y_p-y_q)²)，α = arctan2(y_p-y_q, x_p-x_q)。
   • 判断区间内的可行子区间：
     • 若区间内w(θ)的最大值≤W：整个区间可行，直接在区间内求h(θ)的最小值。
     • 若区间内w(θ)的最小值≤W<最大值：解方程L·cos(θ - α) = W，得到可行子区间[θ_a, θ_b]，仅在该子区间内优化h(θ)。
     • 若区间内w(θ)的最小值>W：直接跳过该区间。

3. 在可行区间内最小化高度
   高度h(θ)是投影到θ+90°方向的长度，在当前区间内可表示为：

   h(θ) = (x_s - x_r)sinθ + (y_r - y_s)cosθ = M·cos(θ - β)
   

   其中r、s是该区间内投影到θ+90°方向的极值顶点，M、β为对应参数。

   • 对h(θ)求导得h’(θ) = -M·sin(θ - β)，令导数为0，得临界点θ=β或θ=β+π。
   • 检查临界点是否在可行区间内，比较临界点、区间端点的h(θ)值，取最小值。

三、一般简单多边形（含凹多边形）的适配 #

凹多边形的投影极值仍由顶点决定（边的投影是线性的，极值在端点），因此核心流程与凸多边形一致，仅需调整极值顶点的跟踪逻辑：

• 采用旋转卡壳算法，在遍历角度区间时动态维护投影方向的极值顶点，避免重复计算所有顶点的投影，提升效率。
• 需额外验证每个区间内极值顶点的稳定性，确保w(θ)和h(θ)的表达式在区间内保持不变。

四、精度与效率优化 #

• 角度计算使用弧度制，处理周期性时仅需考虑[0, π)范围，减少冗余计算。
• 浮点计算引入极小阈值（如1e-8），避免因精度误差导致的可行域判断错误。
• 每个区间的优化仅需常数次计算，整体时间复杂度为O(n log n)（主要来自临界角度排序），远优于暴力枚举。

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