充气小球多边形内弹跳后下一次碰撞的预测求解

核心需求 #

提升闭合非凸多边形内部充气小球的仿真速度，准确预测每次反弹后下一次碰撞的多边形边、碰撞时间及精确位置：

• 小球从多边形质心出发，以恒定速率随机方向运动，碰撞边后反弹
• 小球半径以恒定速率（如1单位/秒）持续膨胀

现有方法的问题 #

基于距离公式推导的方案存在明显缺陷：

• 无法从反弹时刻正确起始计算，碰撞时刻的时间结果不为0
• 未考虑边的线段属性（仅按无限直线计算），导致无效碰撞判定
• 未处理非凸多边形的遮挡问题，可能预测错误的碰撞边

正确求解思路 #

1. 数学建模 #

将问题转化为小球中心运动轨迹与多边形边的距离约束问题：

• 每条多边形边用直线方程 ax + by + c = 0 表示，法向量 (a,b) 指向多边形内部（保证距离计算符号正确）
• 小球中心的运动轨迹：p(t) = p₀ + v·t，其中 p₀ 是反弹后的初始位置，v 是速度向量
• 小球半径随时间变化：r(t) = r₀ + rv·t，其中 r₀ 是反弹后的初始半径，rv 是膨胀速率

碰撞发生时，中心到边的距离等于当前半径，满足方程：

a·(x₀ + vₓ·t) + b·(y₀ + vᵧ·t) + c = r₀ + rv·t

整理为线性方程求解：

(a·vₓ + b·vᵧ - rv)·t + (a·x₀ + b·y₀ + c - r₀) = 0

2. 筛选有效碰撞时间 #

对每条边求解得到的时间t，需通过以下校验：

• t > 0：排除过去时刻或反弹初始时刻的无效解
• 中心投影在边的线段范围内：计算中心到边端点的向量点积，确保投影落在边的两个端点之间
• 轨迹中途无遮挡（非凸多边形必做）：在[0,t]时间段内抽样验证，确保小球中心到所有边的距离始终大于等于对应时刻的半径

3. 确定最优碰撞结果 #

从所有有效解中选择最小的t，对应的边即为下一次碰撞边，再通过中心位置沿法向量反方向移动r(t)距离得到精确碰撞位置。

JavaScript实现示例 #

// 定义多边形边结构：包含直线方程参数、两个端点
class PolygonEdge {
    constructor(p1, p2) {
        this.p1 = p1;
        this.p2 = p2;
        // 计算直线方程ax + by + c = 0，法向量(a,b)指向多边形内部（假设顶点为逆时针顺序）
        const dx = p2.x - p1.x;
        const dy = p2.y - p1.y;
        this.a = dy;
        this.b = -dx;
        this.c = dx * p1.y - dy * p1.x;
        // 归一化法向量，确保距离计算准确
        const len = Math.sqrt(this.a**2 + this.b**2);
        this.a /= len;
        this.b /= len;
        this.c /= len;
    }
}

// 预测下一次碰撞的核心函数
function predictNextCollision(startPos, velocity, initialRadius, expandRate, polygonEdges) {
    let minCollisionTime = Infinity;
    let targetEdge = null;
    let collisionPosition = null;

    for (const edge of polygonEdges) {
        const { a, b, c, p1, p2 } = edge;
        // 计算线性方程的系数
        const tCoeff = a * velocity.x + b * velocity.y - expandRate;
        const constantTerm = a * startPos.x + b * startPos.y + c - initialRadius;

        // 处理平行或已碰撞的情况
        if (Math.abs(tCoeff) < 1e-9) {
            if (Math.abs(constantTerm) < 1e-9) continue; // 已处于碰撞状态，跳过
            continue; // 边与运动方向平行，无碰撞
        }

        // 求解碰撞时间t
        const collisionTime = -constantTerm / tCoeff;
        if (collisionTime <= 1e-9) continue; // 无效的过去时刻

        // 计算碰撞时的中心位置
        const centerAtCollision = {
            x: startPos.x + velocity.x * collisionTime,
            y: startPos.y + velocity.y * collisionTime
        };

        // 验证中心投影是否在边的线段范围内
        const edgeVec = { x: p2.x - p1.x, y: p2.y - p1.y };
        const centerToP1 = { x: centerAtCollision.x - p1.x, y: centerAtCollision.y - p1.y };
        const dotProduct = centerToP1.x * edgeVec.x + centerToP1.y * edgeVec.y;
        const edgeLengthSq = edgeVec.x**2 + edgeVec.y**2;
        if (dotProduct < -1e-9 || dotProduct > edgeLengthSq + 1e-9) continue;

        // 验证轨迹中途是否被其他边遮挡（非凸多边形校验）
        let isCollisionValid = true;
        const sampleSteps = 4; // 抽样步数，可根据精度调整
        for (let i = 1; i < sampleSteps; i++) {
            const tSample = collisionTime * i / sampleSteps;
            const sampleCenter = {
                x: startPos.x + velocity.x * tSample,
                y: startPos.y + velocity.y * tSample
            };
            const sampleRadius = initialRadius + expandRate * tSample;

            for (const otherEdge of polygonEdges) {
                const distance = Math.abs(otherEdge.a * sampleCenter.x + otherEdge.b * sampleCenter.y + otherEdge.c);
                if (distance < sampleRadius - 1e-9) {
                    isCollisionValid = false;
                    break;
                }
            }
            if (!isCollisionValid) break;
        }

        // 更新最优碰撞结果
        if (isCollisionValid && collisionTime < minCollisionTime) {
            minCollisionTime = collisionTime;
            targetEdge = edge;
            // 计算精确碰撞位置：中心沿法向量反方向移动最终半径距离
            const finalRadius = initialRadius + expandRate * collisionTime;
            collisionPosition = {
                x: centerAtCollision.x - a * finalRadius,
                y: centerAtCollision.y - b * finalRadius
            };
        }
    }

    return {
        time: minCollisionTime,
        edge: targetEdge,
        position: collisionPosition
    };
}

关键注意事项 #

• 多边形顶点需按逆时针顺序输入，确保法向量指向内部；若为顺时针，需调整法向量符号
• 数值计算中加入1e-9的误差容忍，避免浮点精度问题导致的错误判定
• 非凸多边形的遮挡校验抽样步数可根据仿真精度和性能需求调整

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