多边形与圆算法：移动初始圆到碰撞位置的距离计算方法

核心逻辑是把圆和多边形的碰撞问题，等价转换为圆心射线与多边形等距偏移边界的求交问题：圆与多边形发生碰撞的充要条件是圆心到多边形的最短距离等于圆半径r，我们只需要求从初始圆心出发、沿移动方向的射线，和距离多边形为r的外侧等距轮廓的第一个交点，交点对应的射线长度就是两位置的距离。

具体计算步骤 #

• 预处理基础参数
  提取初始圆圆心坐标O0、半径r，移动方向向量D，计算方向的模长len_D = sqrt(D.x² + D.y²)，归一化得到单位方向向量D_unit = D / len_D，后续用单位向量计算得到的射线参数t直接对应移动距离。提取多边形P的所有顶点列表V = [v0, v1, ..., vn-1]，多边形为闭合结构，最后一条边为vn-1连接v0。
• 遍历所有边，计算边碰撞的候选距离
  对每条由端点va、vb构成的边：
  1. 计算边的方向向量e = vb - va，取边的外侧单位法向量n = (-e.y, e.x)归一化后的结果，可通过多边形内点（如所有顶点坐标的平均值）校验法向量朝向：法向量和内点到边的向量点积为负则朝向正确，否则取反。
  2. 圆碰撞到该边时，圆心到边所在直线的距离恰好为r，对应方程为(O(t) - va) · n = r，代入射线参数方程O(t) = O0 + t*D_unit解得t_edge = (r - (O0 - va)·n) / (D_unit · n)。
  3. 若分母D_unit · n >= -1e-8，说明移动方向朝向远离边外侧的方向，不可能碰撞该边，直接跳过。
  4. 若解出的t_edge为正，计算此时圆心在边所在直线上的投影点，判断投影点是否落在线段va-vb的范围内，符合条件则将t_edge记为候选碰撞距离。
• 遍历所有顶点，计算顶点碰撞的候选距离
  对每个顶点v：
  1. 圆碰撞到该顶点时，圆心到v的距离恰好为r，对应方程为|O(t) - v|² = r²，展开为关于t的一元二次方程：t² + 2*t*((O0 - v)·D_unit) + |O0 - v|² - r² = 0。
  2. 计算判别式delta = (2*((O0 - v)·D_unit))² - 4*(|O0 - v|² - r²)，若delta < -1e-8说明射线和顶点对应的圆角无交点，直接跳过。
  3. 取两个根中更小的正根t_vertex，校验此时从v指向碰撞圆心的向量，是否在顶点相邻两条边的外侧张角范围内，避免和边碰撞的结果重复计数，符合条件则将t_vertex记为候选碰撞距离。
• 确定最终碰撞距离
  所有合法候选值中最小的数值，就是C_init到C_target的距离。如果不存在正的候选值，说明沿该方向移动圆永远不会和多边形发生碰撞。

边界处理提示：如果初始状态下圆心到多边形的最短距离已经小于等于r，说明初始位置已经碰撞，距离为0；如果移动方向平行于某条边，不要漏判边端点对应的圆角碰撞情况。

实现注意事项 #

• 所有浮点数比较都要加入极小容差（推荐取1e-8量级），抵消浮点计算的精度误差，避免漏判、错判。
• 若场景是圆在多边形内部移动、检测与内边界的碰撞，只需要把边法向量朝向改为内侧，顶点张角校验取内侧范围即可，整体逻辑完全一致。

内容的提问来源于stack exchange，提问作者李江南