如何在受限矩形内平移凸多边形最大化与其他多边形的最小距离（可假设为旋转矩形）

你遇到的是计算几何领域典型的带约束最大最小放置问题：

• 待放置凸多边形只有两个自由度：X方向平移量tx、Y方向平移量ty
• 硬约束：平移后的多边形必须完全落入给定的轴对齐有界区域内部
• 优化目标：找到一组(tx, ty)，让待放置多边形和所有障碍多边形的边框最小距离取最大值，这个距离的最小值越大，放置效果越优。
  你已经实现的GJK距离算法，刚好是解决这类问题的核心基础能力，不需要更换底层计算逻辑。

整个方案的逻辑基于凸形状的距离特性，实现复杂度很低，不需要复杂的优化框架。

第一步：先划定平移的合法可行域 #

对任意凸形状的待放置多边形，先算出tx、ty的允许取值范围：

• 先统计待放置多边形自身的顶点在局部坐标系下的X范围[minPx, maxPx]、Y范围[minPy, maxPy]
• 平移后的绝对X范围为[tx + minPx, tx + maxPx]，要求完全落在有界区域[bounds.x, bounds.x + bounds.width]内，因此tx的合法区间为[bounds.x - minPx, bounds.x + bounds.width - maxPx]
• 同理可得ty的合法区间为[bounds.y - minPy, bounds.y + bounds.height - maxPy]
  只要tx、ty落在这个区间里，凸形状就一定完全在有界区域内，不需要逐点校验边界。

注意：不管障碍多边形有没有超出有界区域，都不需要提前做裁剪——GJK算法计算两个凸形状的最小距离时，自动会取两个形状上离得最近的点，和形状在哪个区域无关，只要待放多边形不越界就行。

第二步：用二分搜索架构建整个优化流程 #

这个目标函数有一个非常好用的数学性质：

如果能找到一组(tx, ty)，让待放多边形和所有障碍的距离都不小于r，那r值就可以进一步往上提；如果找不到，就把r值往下调。
基于这个性质，完全可以用二分搜索快速逼近最优解，不需要暴力遍历所有平移位置：

• 先给r定一个合理的上下界：下界取0，上界取有界区域的对角线长度（这个长度是可能的最大距离的理论上限）
• 取当前区间的中间值midR，检测：在tx、ty的合法区间内，是否存在一组平移量，让待放多边形和每个障碍的GJK距离都>=midR？
• 如果检测到存在这样的平移位置，说明当前midR还可以更大，就把搜索区间的下界移到midR；如果不存在，就把搜索区间的上界移到midR
• 重复迭代30~50次，精度就可以满足工程要求（误差小于1e-3量级）

第三步：旋转矩形场景的快速优化 #

如果所有形状都是旋转矩形，整个流程可以再提速，因为凸多边形的距离函数是分段线性的，最优解一定落在有限个候选点上，不需要大范围搜索：

• 候选点来源主要分三类：
  • 待放矩形的角点，刚好碰到有界区域边界的平移位置
  • 待放矩形的边，刚好和某个障碍矩形的边平行、距离为当前r的平移位置
  • 待放矩形的角点，刚好碰到某个障碍矩形的角点的平移位置
• 这些候选点的总数和障碍数量成正比，O(n)级别，每次检测只需要对每个候选点调用一次GJK算距离，计算量极低。
  这里不需要真的把每个障碍向外膨胀midR生成圆角区域——GJK本身就是基于两个形状的闵可夫斯基差实现的，直接计算待放多边形和障碍的距离，和预先膨胀后的检测结果完全等价，省掉了形状生成的开销。

下面的代码结构可以直接基于你已经实现的GJK距离函数改写：

/**
 * 已有实现：计算两个凸多边形的最小边框距离
 * @param {Array<[number, number]>} polyA 形状A的顶点数组
 * @param {Array<[number, number]>} polyB 形状B的顶点数组
 * @returns {number} 两个形状的最小距离
 */
function gjkDistance(polyA, polyB) {
  // 你已有的GJK实现
}

/**
 * 给定目标距离值r，检测是否存在合法放置位置
 * @param {number} r 目标最小距离
 * @param {Array<[number, number]>} placeablePoly 待放置多边形的局部顶点
 * @param {Array<Array<[number, number]>>} obstacles 所有障碍多边形的顶点
 * @param {{x:number, y:number, width:number, height:number}} bounds 有界区域参数
 * @returns {null | {tx:number, ty:number}} 找到的合法位置，找不到返回null
 */
function checkFeasible(r, placeablePoly, obstacles, bounds) {
  // 第一步：计算平移可行域的范围
  const pxList = placeablePoly.map(p => p[0]);
  const pyList = placeablePoly.map(p => p[1]);
  const minPx = Math.min(...pxList), maxPx = Math.max(...pxList);
  const minPy = Math.min(...pyList), maxPy = Math.max(...pyList);
  const txRange = [bounds.x - minPx, bounds.x + bounds.width - maxPx];
  const tyRange = [bounds.y - minPy, bounds.y + bounds.height - maxPy];

  // 粗定位：在可行域内用步长10做网格扫一遍，收集初步候选点
  const step = 10;
  for(let tx = txRange[0]; tx <= txRange[1]; tx += step) {
    for(let ty = tyRange[0]; ty <= tyRange[1]; ty += step) {
      const movedPoly = placeablePoly.map(([px, py]) => [px + tx, py + ty]);
      let meetReq = true;
      for(const obs of obstacles) {
        const d = gjkDistance(movedPoly, obs);
        if(d < r) {
          meetReq = false;
          break;
        }
      }
      if(meetReq) return {tx, ty};
    }
  }
  return null;
}

/**
 * 主流程：搜索最优放置位置
 * @param {Array<[number, number]>} placeablePoly 待放置多边形
 * @param {Array<Array<[number, number]>>} obstacles 所有障碍多边形
 * @param {{x:number, y:number, width:number, height:number}} bounds 有界区域
 * @returns {{maxDistance:number, position: {tx:number, ty:number}}}
 */
function findOptimalPlacement(placeablePoly, obstacles, bounds) {
  let low = 0;
  let high = Math.hypot(bounds.width, bounds.height);
  let bestR = 0;
  let bestPos = null;

  // 迭代50次，精度足够
  for(let i = 0; i < 50; i++) {
    const midR = (low + high) / 2;
    const pos = checkFeasible(midR, placeablePoly, obstacles, bounds);
    if(pos) {
      bestR = midR;
      bestPos = pos;
      low = midR;
    } else {
      high = midR;
    }
  }
  return {maxDistance: bestR, position: bestPos};
}

• 不要用梯度上升类的优化方法直接搜全局最优点，凸形状的距离函数是分段凸的，很容易卡在局部最优，二分搜索的方法没有局部最优的问题。
• 粗扫的步长可以根据场景的尺度调整，最后找到粗略位置之后，再在这个点周围做小范围细扫，精度会更高。
• 如果待放置多边形是带旋转自由度的（也就是不仅能平移，还能转角度），只要把第三个自由度（旋转角度）也加入二分搜索的维度就行，整体框架不需要变。

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