问星多边形圆环碰撞-解决速度方向上的交点&确定碰撞侧

EN

C = [ C[0], C[1] ]
V = [ V[0], V[1] ]
P[i-1] = [ P[i-1][0],  P[i-1][1] ]
P[i] = [ P[i][0],  P[i][1] ]

Normal = [ P[i-1][1] - P[i][1], P[i][0] - P[i-1][0] ];
Normal = Normal / sqrt((P[i-1][1] - P[i][1])^2 + ( P[i][0] - P[i-1][0] )^2); 
// you may have calculated these already

Q_0[0] = P[i-1][0] + r*Normal[0];
Q_0[1] = P[i-1][1] + r*Normal[1];

Q_1[0] = P[i][0]+ r*Normal[0]; 
Q_1[1] = P[i][1]+ r*Normal[1]; 

Q_0[0] + s*(Q_1[0] - Q_0[0]) = C[0] - t*V[0];
Q_0[1] + s*(Q_1[1] - Q_0[1]) = C[1] - t*V[1];

R[0] = C[0] - t*V[0];
R[1] = C[1] - t*V[1];

norm(P[i] - C + t*V )^2 = r^2

(V[0]^2 + V[1]^2) * t^2 + 2 * ( (P[i][0] - C[0])*V[0] + (P[i][1] - C[1])*V[1] )*t + ( P[i][0] - C[0])^2 + (P[i][1] - C[1])^2 )  - r^2 = 0

a = V[0]^2 + V[1]^2;
b = (P[i][0] - C[0])*V[0] + (P[i][1] - C[1])*V[1];
c = (P[i][0] - C[0])^2 + (P[i][1] - C[1])^2 - r^2;
D = b^2 - a*c;

if D < 0 there is no collision with the vertex 
i.e. no intersection between the line X = C - t*V 
and the circle of radius r centered at P[i]

else
D = sqrt(D);
t1 = ( - b - D) / a;
t2 = ( - b + D) / a;  
where t2 >= t1 

R[0] = C[0] - t2*V[0];
R[1] = C[1] - t2*V[1];

// What we need :

Vector startPos; // Last position of the circle before the collision
Vector currentPos; // Current, unwanted position
Vector dir; // Direction (a unit vector) of the circle's velocity
float distance = compute_distance(startPos, currentPos); // The distance from startPos to currentPos.
Polygon polygon; // The polygon
Circle circle; // The circle.
unsigned int iterations_count = 10; // The number of iterations that will be done. The higher this number, the more precise the resolution.

// The algorithm :

float currentDistance = distance / 2.f; // We start at the half of the distance.
Circle temp_copy; // A copy of the real circle to "play" with.
for (int i = 0; i < iterations_count; ++i) {
    temp_copy.pos = startPos + currentDistance * dir;
    if (checkForCollision(temp_copy, polygon)) {
        currentDistance -= currentDistance / 2.f; // We go towards startPos by the half of the current distance.
    }
    else {
        currentDistance += currentDistance / 2.f; // We go towards currentPos by the half of the current distance.
    }
}
    
// currentDistance now contains the distance between startPos and the intersection point
// And this is where you should place your circle :
Vector intersectionPoint = startPos + currentDistance * dir;

Math.EPSILON = 1e-6;
Math.isSmall = val => Math.abs(val) < Math.EPSILON;
Math.isUnit = u => !(u < 0 || u > 1);
Math.TAU = Math.PI * 2;


/* export {Vec2, Line2} */ // this should be a module
var temp;
function Vec2(x = 0, y = (temp = x, x === 0 ? (x = 0 , 0) : (x = x.x, temp.y))) {
    this.x = x;
    this.y = y;
}
Vec2.prototype = {
    init(x, y = (temp = x, x = x.x, temp.y)) { this.x = x; this.y = y; return this }, // assumes x is a Vec2 if y is undefined
    copy() { return new Vec2(this) },
    equal(v) { return (this.x - v.x) === 0 && (this.y - v.y) === 0 },
    isUnits() { return Math.isUnit(this.x) && Math.isUnit(this.y) },
    add(v, res = this) { res.x = this.x + v.x; res.y = this.y + v.y; return res },
    sub(v, res = this) { res.x = this.x - v.x; res.y = this.y - v.y; return res },
    scale(val, res = this) { res.x = this.x * val; res.y = this.y * val; return res },
    invScale(val, res = this) { res.x = this.x / val; res.y = this.y / val; return res },
    dot(v) { return this.x * v.x + this.y * v.y },
    uDot(v, div) { return (this.x * v.x + this.y * v.y) / div },
    cross(v) { return this.x * v.y - this.y * v.x },
    uCross(v, div) { return (this.x * v.y - this.y * v.x) / div },
    get length() { return this.lengthSqr ** 0.5 },
    set length(l) { this.scale(l / this.length) },
    get lengthSqr() { return this.x * this.x + this.y * this.y },
    rot90CW(res = this) {
        const y = this.x;
        res.x = -this.y;
        res.y = y;
        return res;
    },
};
const wV1 = new Vec2(), wV2 = new Vec2(), wV3 = new Vec2(); // pre allocated work vectors used by Line2 functions
function Line2(p1 = new Vec2(), p2 = (temp = p1, p1 = p1.p1 ? p1.p1 : p1, temp.p2 ? temp.p2 : new Vec2())) {
    this.p1 = p1;
    this.p2 = p2;
}
Line2.prototype = {
    init(p1, p2 = (temp = p1, p1 = p1.p1, temp.p2)) { this.p1.init(p1); this.p2.init(p2) },
    copy() { return new Line2(this) },
    asVec(res = new Vec2()) { return this.p2.sub(this.p1, res) },
    unitDistOn(u, res = new Vec2()) { return this.p2.sub(this.p1, res).scale(u).add(this.p1) },
    translate(vec, res = this) {
        this.p1.add(vec, res.p1);
        this.p2.add(vec, res.p2);
        return res;
    },
    translateNormal(amount, res = this) {
        this.asVec(wV1).rot90CW().length = -amount;
        this.translate(wV1, res);
        return res;
    },
    unitInterceptsLine(line, res = new Vec2()) {  // segments
        this.asVec(wV1);
        line.asVec(wV2);
        const c = wV1.cross(wV2);
        if (Math.isSmall(c)) { return }
        wV3.init(this.p1).sub(line.p1);
        res.init(wV1.uCross(wV3, c), wV2.uCross(wV3, c));
        return res;
    },
    unitInterceptsCircle(point, radius, res = new Vec2()) {
        this.asVec(wV1);
        var b = -2 * this.p1.sub(point, wV2).dot(wV1);
        const c = 2 * wV1.lengthSqr;
        const d = (b * b - 2 * c * (wV2.lengthSqr - radius * radius)) ** 0.5
        if (isNaN(d)) { return }
        return res.init((b - d) / c, (b + d) / c);
    },
};

/* END of file */ // Vec2 and Line2 module 



/* import {vec2, Line2} from "whateverfilename.jsm" */ // Should import vec2 and line2
const POLY_SCALE = 0.5;
const ball = {
    pos: new Vec2(-150,0),
    delta: new Vec2(10, 10),
    radius: 20,
    drawPath(ctx) {
        ctx.beginPath();
        ctx.arc(this.pos.x, this.pos.y, this.radius, 0, Math.TAU);
        ctx.stroke();
    },
}
const poly =  {
    bRadius: 0,
    lines: [],
    set ballRadius(radius) {
        const len = this.points.length
        this.bRadius = ball.radius;
        i = 0;
        while (i < len) {
            let line = this.lines[i];
            if (line) { line.init(this.points[i], this.points[(i + 1) % len]) }
            else { line = new Line2(new Vec2(this.points[i]), new Vec2(this.points[(i + 1) % len])) }
            this.lines[i++] = line.translateNormal(radius);
        }
        this.lines.length = i;
    },
    points: [
        new Vec2(-200, -150).scale(POLY_SCALE),
        new Vec2(200, -100).scale(POLY_SCALE),
        new Vec2(100, 0).scale(POLY_SCALE),
        new Vec2(200, 100).scale(POLY_SCALE),
        new Vec2(-200, 75).scale(POLY_SCALE),
        new Vec2(-150, -50).scale(POLY_SCALE),
    ],
    drawBallLines(ctx) {
        if (this.lines.length) {
            const r = this.bRadius;
            ctx.beginPath();
            for (const l of this.lines) { 
                ctx.moveTo(l.p1.x, l.p1.y);
                ctx.lineTo(l.p2.x, l.p2.y);
            }
            for (const p of this.points) { 
                ctx.moveTo(p.x + r, p.y);
                ctx.arc(p.x, p.y, r, 0, Math.TAU);
            }
            ctx.stroke()
        }
    },
    drawPath(ctx) {
        ctx.beginPath();
        for (const p of this.points) { ctx.lineTo(p.x, p.y) }
        ctx.closePath();
        ctx.stroke();
    },
    movingBallIntercept(ball, res = new Vec2()) {
        if (this.bRadius !== ball.radius) { this.ballRadius = ball.radius }
        var i = 0, nearest = Infinity, nearestGeom, units = new Vec2();
        const ballT = new Line2(ball.pos, ball.pos.add(ball.delta, new Vec2()));
        for (const p of this.points) {
            const res = ballT.unitInterceptsCircle(p, ball.radius, units);
            if (res && units.x < nearest && Math.isUnit(units.x)) { // assumes ball started outside poly so only need first point
                nearest = units.x;
                nearestGeom = ballT;
            }
        }
        for (const line of this.lines) {
            const res = line.unitInterceptsLine(ballT, units);
            if (res && units.x < nearest && units.isUnits()) { // first unit.x is for unit dist on line
                nearest = units.x;
                nearestGeom = ballT;
            }
        }
        if (nearestGeom) { return ballT.unitDistOn(nearest, res) }
        return;
    },
}



const ctx = canvas.getContext("2d");
var w = canvas.width, cw = w / 2;
var h = canvas.height, ch = h / 2
requestAnimationFrame(mainLoop);



// line and point for displaying mouse interaction. point holds the result if any
const line = new Line2(ball.pos, ball.pos.add(ball.delta, new Vec2())), point = new Vec2();
function mainLoop() {
    ctx.setTransform(1,0,0,1,0,0); // reset transform
    if(w !== innerWidth || h !== innerHeight){
        cw = (w = canvas.width = innerWidth) / 2;
        ch = (h = canvas.height = innerHeight) / 2;
    }else{
        ctx.clearRect(0,0,w,h);
    }
    ctx.setTransform(1,0,0,1,cw,ch);  // center to canvas
    if (mouse.button) { ball.pos.init(mouse.x - cw, mouse.y - ch) }
    line.p2.init(mouse.x - cw, mouse.y - ch);
    line.p2.sub(line.p1, ball.delta);

    ctx.lineWidth = 1;
    ctx.strokeStyle = "#000"
    poly.drawPath(ctx)
    ctx.strokeStyle = "#F804"
    poly.drawBallLines(ctx);       
    
    ctx.strokeStyle = "#F00"    
    ctx.beginPath();
    ctx.arc(ball.pos.x, ball.pos.y, ball.radius, 0, Math.TAU);
    ctx.moveTo(line.p1.x, line.p1.y);
    ctx.lineTo(line.p2.x, line.p2.y);
    ctx.stroke();

    ctx.strokeStyle = "#00f"    
    ctx.lineWidth = 2;
    ctx.beginPath();
    if (poly.movingBallIntercept(ball, point)) {
       ctx.arc(point.x, point.y, ball.radius, 0, Math.TAU);
    } else {
       ctx.arc(line.p2.x, line.p2.y, ball.radius, 0, Math.TAU);
    }
    ctx.stroke();
           
    requestAnimationFrame(mainLoop);
}


const mouse = {x:0, y:0, button: false};
function mouseEvents(e) {
      const bounds = canvas.getBoundingClientRect();
      mouse.x = e.pageX - bounds.left - scrollX;
      mouse.y = e.pageY - bounds.top - scrollY;
      mouse.button = e.type === "mousedown" ? true : e.type === "mouseup" ? false : mouse.button;
}
["mousedown","mouseup","mousemove"].forEach(name => document.addEventListener(name,mouseEvents));

#canvas {
  position: absolute;
  top: 0px;
  left: 0px;
}

<canvas id="canvas"></canvas>
Click to position ball. Move mouse to test trajectory