给定顶点多边形及内部起点，求可嵌入的最大中心正方形

嘿，这个问题挺典型的，属于计算几何里的嵌入优化问题，我给你梳理下可行的解法思路，分两种场景来聊：

因为正方形的中心已经固定是给定的起点，所以问题本质上就是找到最大的边长s，使得以该起点为中心的正方形（不管是否轴对齐）完全落在多边形内部。我们可以先从简单的轴对齐情况入手，再拓展到任意旋转的情况。

1. 轴对齐正方形的最大嵌入解法 #

这是最直接的场景，先搞定这个：

• 首先明确，以起点(x0, y0)为中心的轴对齐正方形，四个顶点坐标是(x0±s/2, y0±s/2)
• 我们可以用二分查找法来高效找到最大的s：
  • 确定s的上下界：下界设为0，初始上界可以取从起点到多边形各边的最小距离的2倍（因为s/2不能超过起点到多边形边界的最小距离，否则正方形会穿出），或者直接设为多边形的直径（最长顶点间距），后续再逐步缩小。
  • 对每个候选s，构造正方形并检查它是否完全在多边形内：
    • 检查方法分两步：
      1. 用射线法判断正方形的四个顶点是否都在多边形内部（包括边界）：从每个点向右引一条水平射线，统计它与多边形边的交点数，奇数则在内部，偶数则在外部；注意处理点恰好落在多边形边上的情况，此时算作内部。
      2. 检查正方形的四条边是否与多边形的边存在非顶点的相交（如果有，说明正方形穿出了多边形）。
  • 不断调整二分的区间，直到s的精度满足需求（比如两次迭代的s差值小于1e-8）。

2. 支持任意旋转的最大正方形解法 #

如果允许正方形旋转以适配多边形的形状，能得到更大的嵌入正方形，这时候需要同时优化边长s和旋转角度θ（θ的范围是0 ≤ θ < π/2，因为旋转π/2后和原正方形完全一致）：

• 对于给定的旋转角度θ，正方形的四个顶点坐标可以用以下公式计算：

  x = x0 ± (s/2)*cosθ ∓ (s/2)*sinθ
  y = y0 ± (s/2)*sinθ ± (s/2)*cosθ
  

  （四个顶点对应四种符号组合：(+,+)、(+,-)、(-,-)、(-,+)）
• 同样用二分查找法，对每个θ计算能嵌入的最大s。但遍历所有θ显然不现实，我们只需要关注关键角度：
  • 关键角度是多边形各边的法线方向（也就是正方形的边与多边形某条边平行的角度），因为最大的s必然出现在正方形的某条边与多边形的边相切的情况（极值点在约束边界上）。另外还要加上0、π/4这类特殊角度。
• 收集所有关键角度，对每个角度计算对应的最大s，最后取所有s中的最大值，就是我们要的结果。

3. 实现时的注意事项 #

• 浮点数精度问题：计算时要设置一个极小的epsilon（比如1e-8），用来判断点是否在边上、线段是否相交等，避免因浮点误差导致错误判断。
• 多边形顶点顺序：确保多边形的顶点是按顺时针或逆时针顺序排列的，这样射线法的点-in-多边形判断才能正确工作。
• 边界处理：题目允许正方形完全嵌入，所以正方形的边或顶点接触多边形边界是被允许的，判断时要将这种情况视为合法。

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