javascriptpolygoncollisionkinematics

After a bounce, compute the next time of impact between an inflating ball and a line of a polygon (and where it will hit)


Imagine a scenario with a ball that is inside of a closed polygon (made up of individual lines). The polygon is not necessarily convex.

Ball starting off from centroid in random direction

The ball starts off at the centroid of the polygon with a random velocity. The magnitude of this velocity is constant, but it starts out at a random angle.

The ball continues until it hits one of the sides and then bounces off.

The ball's radius increases at a constant rate (say 1 unit per second) - i.e. the ball inflates at a constant rate.

I am able to make this simulation and it works fine (the ball bounces around inside the polygon while it inflates) - but ideally I'd like to speed up the simulation and one way to do that is: When the ball hits a line and bounces off, I want to ask the question (and get an answer!):

Which line of the polygon will the ball hit next and how long until it hits it. Also, where exactly on the line will it hit?

Ball inflated a bit after a few bounces

I have tried to solve this is a bunch of different ways - none have been wholly successful. I will detail one of my attempts as follows:

d(t) = |(x_2 - x_1)(y_1 - (c_2 + v_yt)) - (x_1 - (c_1 + v_xt))(y_2 - y_1)| / L Ball hits when:

d(t) <= r_i + r_v*t

Rearrange:

|(x_2 - x_1)(y_1 - (c_2 + v_yt)) - (x_1 - (c_1 + v_xt))(y_2 - y_1)| <= (r_i + r_v*t)*L

Let C = (x_2 - x_1)(y_1 - c_2) - (x_1 - c_1)(y_2 - y_1) D = (x_2 - x_1)*v_y - (y_2 - y_1)v_xt

Then:

| C - tD| <= (r_i + r_vt)*L

Case 1:

C - tD >= 0 C - tD <= (r_i + r_v*t)*L

leads to: t >= (C - r_iL) / (D + r_vL)

Case 2:

C - t*D < 0

-(C - tD) <= (r_i + r_vt)*L

This leads to same thing:

t >= (C - r_iL) / (D + r_vL)

So we try:

// Let p1 be (x_1, y_1), p2 = (x_2, y_2) ball center = (c1_, c_2), ball velocity = (v_x, v_y). r_v be the ball inflation velocity.
// Compute constants C, D, and L
const C = (x_2 - x_1) * (y_1 - c_2) - (x_1 - c_1) * (y_2 - y_1);
const D = (x_2 - x_1) * v_y - (y_2 - y_1) * v_x;
const L = Math.sqrt((x_2 - x_1) ** 2 + (y_2 - y_1) ** 2);

// Compute time to impact
const denominator = D + r_v * L;
if (denominator !== 0) {
    const t1 = (C - r_i * L) / denominator;
    const t2 = (-C + r_i * L) / denominator;

    // Find the minimum valid time
    if (t1 > 0 && t1 < shortestTimeTillImpact) {
        shortestTimeTillImpact = t1;
        impactedLine = [p1, p2];
        impactedLineIndex = i + 1;
    }
    if (t2 > 0 && t2 < shortestTimeTillImpact) {
        shortestTimeTillImpact = t2;
        impactedLine = [p1, p2];
        impactedLineIndex = i + 1;
    }
  }

This will find the correct line of impact, but not from the start of the bounce. Also the time till impact will not be 0 when it hits.

I also tried a parametric solution but I don't think this is the right approach because a parametrization of the line segments is a point traveling from p1 to p2 and for a circle it's a point traveling around a circle - the intersection of which is not really what I am looking for.

Here is the base setup of the ball bouncing around the polygon:

addEventListener("DOMContentLoaded", (event) => {
  // const curvePoints = getCurvePoints(points.flatMap(pair => pair), 0.5, 25, true);
  const canvas = document.getElementById('myCanvas');
  const ctx = canvas.getContext('2d');

  // Set canvas dimensions
  canvas.width = 800;
  canvas.height = 600;
  // Polygon vertices
  const polygonVertices = ensureClosed(regularPolygonVertices(12, 100, { x: 100, y: 100 }));
  const centroid = calculateCentroid(polygonVertices);

  const vAngle = Math.random() * 2 * Math.PI;
  const vMag = 30;
  const maxVelComp = 30;
  let previousTime;
  let msSinceLastInflation = 0;
  let impactedLineIndex = -1;
  const ball = {
    // Start ball at the centroid of the polyline.
    x: centroid.x,
    y: centroid.y,
    radius: 5,
    vx: vMag * Math.cos(vAngle),
    vy: vMag * Math.sin(vAngle),
    lastLineCollidedWith: -1,
    vRadius: 1,
  };

  function draw() {
    ctx.clearRect(0, 0, canvas.width, canvas.height);

    // Draw the polygon (will become the circle trace)
    for (let i = 1; i < polygonVertices.length; i++) {
      ctx.beginPath();
      ctx.moveTo(polygonVertices[i - 1].x, polygonVertices[i - 1].y);
      ctx.lineTo(polygonVertices[i].x, polygonVertices[i].y);
      ctx.closePath();
      if (impactedLineIndex != -1 && impactedLineIndex === i) {
        ctx.strokeStyle = 'green';
      } else {
        ctx.strokeStyle = 'black';
      }
      ctx.lineWidth = 2;
      ctx.stroke();
    }


    // Draw the ball
    ctx.fillStyle = 'red';
    ctx.beginPath();
    ctx.arc(ball.x, ball.y, ball.radius, 0, 2 * Math.PI);
    ctx.closePath();
    ctx.fill();
  }

  function handleCollisions() {
    const intersection = circlePolylineIntersection(ball, polygonVertices);
    // console.log(performance.measure('collision', 'start-collision', 'end-collision').duration);
    if (intersection != null && intersection.lineIndex != ball.lastLineCollidedWith) {
      const normal = { x: intersection.line.end.y - intersection.line.start.y, y: intersection.line.start.x - intersection.line.end.x };
      const normalMagnitude = Math.sqrt(normal.x * normal.x + normal.y * normal.y);
      const normalizedNormal = {
        x: normal.x / normalMagnitude,
        y: normal.y / normalMagnitude
      };

      const relativeVelocity = ball.vx * normalizedNormal.x + ball.vy * normalizedNormal.y;

      ball.lastLineCollidedWith = intersection.lineIndex;
      ball.vx = ball.vx - (2 * relativeVelocity * normalizedNormal.x);
      ball.vy = ball.vy - (2 * relativeVelocity * normalizedNormal.y);
      ball.vx = Math.max(-maxVelComp, Math.min(maxVelComp, ball.vx));
      ball.vy = Math.max(-maxVelComp, Math.min(maxVelComp, ball.vy));
    }
  }

  function animate(currentTime) {
    if (previousTime === undefined) {
      previousTime = currentTime;
    } else {
      const timePerFrame = currentTime - previousTime;
      msSinceLastInflation += timePerFrame;

      // We can ask the question given the current position and velocity of the ball which line of the polyline will it hit next (where and when).
      let shortestTimeTillImpact = 999999;
      let impactedLine = null;
      for (let i = 0; i < polygonVertices.length - 1; i++) {
        // Let (x_1, y_1) and (x_2, y_2) be the start and end points of the current line.
        // Let (c_1, c_2) be the center of the circle, r_i the initial radius and r_v the "radius velocity" (that is the increase in the circle's radius per second).
        // Let (v_x, v_y) be the x and y velocity of the circle.

        // Parametric line equations:
        // x = x_1 + t * (x_2 - x_1)
        // y = y_1 + t * (y_2 - y_1)

        // Parametric equation of the circle at time t:
        // (x - (c_1 + v_x*t))² + (y - (c_2 + v_y*t))² = (r_i + r_v*t)²

        // Substituting line equation into circle equation yields:
        // (x_1 + t * (x_2 - x_1) - (c_1 + v_x*t))² + (y_1 + t * (y_2 - y_1) - (c_2 + v_y*t))² = (r_i+r_v*t)²

        // This reduces to a quadratic equation (though the terms are very long):
        // t = (-sqrt((-2 c_1 v_x - 2 c_2 v_y - 2 c_1 x_1 + 2 c_1 x_2 - 2 c_2 y_1 + 2 c_2 y_2 + 2 r_v r_i + 2 v_x x_1 + 2 v_y y_1 + 2 x_1^2 - 2 x_2 x_1 + 2 y_1^2 - 2 y_1 y_2)^2 - 4 (2 c_1 x_1 + 2 c_2 y_1 - c_1^2 - c_2^2 + r_i^2 - x_1^2 - y_1^2) (r_v^2 - v_x^2 - 2 v_x x_1 + 2 v_x x_2 - v_y^2 - 2 v_y y_1 + 2 v_y y_2 - x_1^2 + 2 x_2 x_1 - x_2^2 - y_1^2 - y_2^2 + 2 y_1 y_2)) + 2 c_1 v_x + 2 c_2 v_y + 2 c_1 x_1 - 2 c_1 x_2 + 2 c_2 y_1 - 2 c_2 y_2 - 2 r_v r_i - 2 v_x x_1 - 2 v_y y_1 - 2 x_1^2 + 2 x_2 x_1 - 2 y_1^2 + 2 y_1 y_2)/(2 (r_v^2 - v_x^2 - 2 v_x x_1 + 2 v_x x_2 - v_y^2 - 2 v_y y_1 + 2 v_y y_2 - x_1^2 + 2 x_2 x_1 - x_2^2 - y_1^2 - y_2^2 + 2 y_1 y_2))
        // t = ( sqrt((-2 c_1 v_x - 2 c_2 v_y - 2 c_1 x_1 + 2 c_1 x_2 - 2 c_2 y_1 + 2 c_2 y_2 + 2 r_v r_i + 2 v_x x_1 + 2 v_y y_1 + 2 x_1^2 - 2 x_2 x_1 + 2 y_1^2 - 2 y_1 y_2)^2 - 4 (2 c_1 x_1 + 2 c_2 y_1 - c_1^2 - c_2^2 + r_i^2 - x_1^2 - y_1^2) (r_v^2 - v_x^2 - 2 v_x x_1 + 2 v_x x_2 - v_y^2 - 2 v_y y_1 + 2 v_y y_2 - x_1^2 + 2 x_2 x_1 - x_2^2 - y_1^2 - y_2^2 + 2 y_1 y_2)) + 2 c_1 v_x + 2 c_2 v_y + 2 c_1 x_1 - 2 c_1 x_2 + 2 c_2 y_1 - 2 c_2 y_2 - 2 r_v r_i - 2 v_x x_1 - 2 v_y y_1 - 2 x_1^2 + 2 x_2 x_1 - 2 y_1^2 + 2 y_1 y_2)/(2 (r_v^2 - v_x^2 - 2 v_x x_1 + 2 v_x x_2 - v_y^2 - 2 v_y y_1 + 2 v_y y_2 - x_1^2 + 2 x_2 x_1 - x_2^2 - y_1^2 - y_2^2 + 2 y_1 y_2))

        // Without increasing radius:
        // t = (-sqrt((-2 c_1 v_x - 2 c_2 v_y - 2 c_1 x_1 + 2 c_1 x_2 - 2 c_2 y_1 + 2 c_2 y_2 + 2 v_x x_1 + 2 v_y y_1 + 2 x_1^2 - 2 x_2 x_1 + 2 y_1^2 - 2 y_1 y_2)^2 - 4 (2 c_1 x_1 + 2 c_2 y_1 - c_1^2 - c_2^2 + r^2 - x_1^2 - y_1^2) (-v_x^2 - 2 v_x x_1 + 2 v_x x_2 - v_y^2 - 2 v_y y_1 + 2 v_y y_2 - x_1^2 + 2 x_2 x_1 - x_2^2 - y_1^2 - y_2^2 + 2 y_1 y_2)) + 2 c_1 v_x + 2 c_2 v_y + 2 c_1 x_1 - 2 c_1 x_2 + 2 c_2 y_1 - 2 c_2 y_2 - 2 v_x x_1 - 2 v_y y_1 - 2 x_1^2 + 2 x_2 x_1 - 2 y_1^2 + 2 y_1 y_2)/(2 (-v_x^2 - 2 v_x x_1 + 2 v_x x_2 - v_y^2 - 2 v_y y_1 + 2 v_y y_2 - x_1^2 + 2 x_2 x_1 - x_2^2 - y_1^2 - y_2^2 + 2 y_1 y_2))
        // t =  (sqrt((-2 c_1 v_x - 2 c_2 v_y - 2 c_1 x_1 + 2 c_1 x_2 - 2 c_2 y_1 + 2 c_2 y_2 + 2 v_x x_1 + 2 v_y y_1 + 2 x_1^2 - 2 x_2 x_1 + 2 y_1^2 - 2 y_1 y_2)^2 - 4 (2 c_1 x_1 + 2 c_2 y_1 - c_1^2 - c_2^2 + r^2 - x_1^2 - y_1^2) (-v_x^2 - 2 v_x x_1 + 2 v_x x_2 - v_y^2 - 2 v_y y_1 + 2 v_y y_2 - x_1^2 + 2 x_2 x_1 - x_2^2 - y_1^2 - y_2^2 + 2 y_1 y_2)) + 2 c_1 v_x + 2 c_2 v_y + 2 c_1 x_1 - 2 c_1 x_2 + 2 c_2 y_1 - 2 c_2 y_2 - 2 v_x x_1 - 2 v_y y_1 - 2 x_1^2 + 2 x_2 x_1 - 2 y_1^2 + 2 y_1 y_2)/(2 (-v_x^2 - 2 v_x x_1 + 2 v_x x_2 - v_y^2 - 2 v_y y_1 + 2 v_y y_2 - x_1^2 + 2 x_2 x_1 - x_2^2 - y_1^2 - y_2^2 + 2 y_1 y_2))

        const p1 = polygonVertices[i];
        const p2 = polygonVertices[i + 1];
        const x_1 = p1.x;
        const y_1 = p1.y;
        const x_2 = p2.x;
        const y_2 = p2.y;
        const c_1 = ball.x;
        const c_2 = ball.y;
        const r_i = ball.radius;
        const r_v = ball.vRadius;
        const v_x = ball.vx;
        const v_y = ball.vy;


        // Compute constants C, D, and L
        const C = (x_2 - x_1) * (y_1 - c_2) - (x_1 - c_1) * (y_2 - y_1);
        const D = (x_2 - x_1) * v_y - (y_2 - y_1) * v_x;
        const L = Math.sqrt((x_2 - x_1) ** 2 + (y_2 - y_1) ** 2);

        // Compute time to impact
        const denominator = D + r_v * L;
        if (denominator !== 0) {
          const t1 = (C - r_i * L) / denominator;
          const t2 = (-C + r_i * L) / denominator;

          // Find the minimum valid time
          if (t1 > 0 && t1 < shortestTimeTillImpact) {
            shortestTimeTillImpact = t1;
            impactedLine = [p1, p2];
            impactedLineIndex = i + 1;
          }
          if (t2 > 0 && t2 < shortestTimeTillImpact) {
            shortestTimeTillImpact = t2;
            impactedLine = [p1, p2];
            impactedLineIndex = i + 1;
          }
        }

        if (impactedLine != null) {
          console.log("WILL HIT LINE [(" + impactedLine[0].x + ", " + impactedLine[0].y + "), (" + impactedLine[1].x + ", " + impactedLine[1].y + ")] IN TIME: " + shortestTimeTillImpact + "!");
        }
        ball.radius += ball.vRadius * (timePerFrame / 1000);

        handleCollisions();
        ball.x += ball.vx * (timePerFrame / 1000);
        ball.y += ball.vy * (timePerFrame / 1000);

      }
      previousTime = currentTime;

      draw();
      requestAnimationFrame(animate);
    }

    animate();
  }
});

function regularPolygonVertices(sides, radius, center = { x: 0, y: 0 }) {
  const vertices = [];
  const angle = 360 / sides;

  for (let i = 0; i < sides; i++) {
    const x = radius * Math.cos(Math.PI * i * angle / 180) + center.x;
    const y = radius * Math.sin(Math.PI * i * angle / 180) + center.y;
    vertices.push({ x: x, y: y });
  }

  return vertices;
}

function circlePolylineIntersection(circle, polyline) {
  performance.mark("start-collision");
  let closestIntersection = null;
  let closestDistance = Infinity;

  for (let i = 0; i < polyline.length - 1; i++) {
    if (circle.lastLineCollidedWith == i) {
      continue;
    }
    const p1 = polyline[i];
    const p2 = polyline[i + 1];

    // Calculate distance from circle center to segment
    const distance = pointLineDistance(circle.x, circle.y, p1.x, p1.y, p2.x, p2.y);

    // Check if the distance is less than or equal to the circle's radius
    if (distance <= circle.radius && distance < closestDistance) {
      closestDistance = distance;
      closestIntersection = {
        lineIndex: i,
        line: { start: p1, end: p2 },
        point: pointOnLineClosestTo(circle.x, circle.y, p1.x, p1.y, p2.x, p2.y)
      };
    }
  }

  performance.mark("end-collision");
  return closestIntersection ? closestIntersection : null;
}

function pointLineDistance(px, py, x1, y1, x2, y2) {
  // Check if the point lies on the line segment
  if (isPointOnLineSegment(px, py, x1, y1, x2, y2)) {
    return 0;
  }

  // Calculate the perpendicular distance
  const dx = x2 - x1;
  const dy = y2 - y1;
  const u = ((px - x1) * dx + (py - y1) * dy) / (dx * dx + dy * dy);

  if (u < 0 || u > 1) {
    // The closest point is one of the endpoints
    const d1 = Math.sqrt((px - x1) * (px - x1) + (py - y1) * (py - y1));
    const d2 = Math.sqrt((px - x2) * (px - x2) + (py - y2) * (py - y2));
    return Math.min(d1, d2);
  }

  const ix = x1 + u * dx;
  const iy = y1 + u * dy;
  return Math.sqrt((px - ix) * (px - ix) + (py - iy) * (py - iy));
}

function pointOnLineClosestTo(px, py, x1, y1, x2, y2) {
  const dx = x2 - x1;
  const dy = y2 - y1;
  const u = ((px - x1) * dx + (py - y1) * dy) / (dx * dx + dy * dy);

  if (u < 0) {
    return { x: x1, y: y1 };
  } else if (u > 1) {
    return { x: x2, y: y2 };
  } else {
    return { x: x1 + u * dx, y: y1 + u * dy };
  }
}

function isPointOnLineSegment(px, py, x1, y1, x2, y2) {
  const v1x = px - x1;
  const v1y = py - y1;
  const v2x = x2 - x1;
  const v2y = y2 - y1;

  const cross = v1x * v2y - v1y * v2x;
  if (cross !== 0) {
    return false; // Point is not on the line
  }

  const dot = v1x * v2x + v1y * v2y;
  return dot >= 0 && dot <= v2x * v2x + v2y * v2y;
}

function calculateCentroid(polygon) {
  let signedArea = 0;
  let cx = 0;
  let cy = 0;

  for (let i = 0; i < polygon.length - 1; i++) {
    const xi = polygon[i].x;
    const yi = polygon[i].y;
    const xi1 = polygon[i + 1].x;
    const yi1 = polygon[i + 1].y;

    const factor = xi * yi1 - xi1 * yi;
    signedArea += factor;
    cx += (xi + xi1) * factor;
    cy += (yi + yi1) * factor;
  }

  signedArea *= 0.5;
  cx /= (6 * signedArea);
  cy /= (6 * signedArea);

  return { x: cx, y: cy };
}

function ensureClosed(polygon) {
  const clonedPolygon = [...polygon]; // Create a copy of the polygon
  // Ensure polygon is a closed polygon
  if (polygon[0] !== polygon[polygon.length - 1]) {
    clonedPolygon.push(polygon[0]);
  }

  return clonedPolygon;
}

Solution

  • The full solution is quite complicated and computationally demanding; I'm not so sure if it would be a more efficient alternative to your actual code, especially on the final stages of the radius expansion, when the collisions are very frequent and the motion between them very short.

    Here's the mathematical formulation I used; I made some of the computations in Mathematica, so I had to not use underscores in the variable names. The bulk of the computation was made after all with sympy, I attached the code at the end of the post.

    I used the following notations (t is the time):

    x = xc + vx * t + (r0 + rr * t) * cos(phi),   (1)
    y = yc + vy * t + (r0 + rr * t) * sin(phi)    (2)
    t > 0; -pi < phi < pi
    
    x = x1 + (x2 - x1) * s,  (3)
    y = y1 + (y2 - y1) * s,  (4)
    0 <= s <= 1
    

    From eqs (1-4), for the position where the ball will become tangent to the segment, x and y, are the same and we get a system of two equations with params s, t and phi. Solve this system for s and t, keeping phi a free parameter (we get s(phi) and t(phi)). In the javascript below the mathematical functions s(phi) and t(phi) are implemented as getS and getT

    We need to symbolically solve the equations s(phi) = 0 and s(phi) = 1 that will be needed to find the phi for the ends of a segment (for the case the polygon is not convex)

    We also need to find the formulae for the values of phi for the extremes (minimum or maximum) of t(phi). The minimum of t gives us the moment when the contact happens. (If we were to ignore the contact and continue to draw the ball going in the same direction, the contact will continue while the ball traverses the segment; those contacts will also obey our equations. However, we are only interested in the first moment of the contact which is defined by min t(phi)). Once we have phi for the contact, we can compute s(phi) and use it to determine the exact point of the contact.

    Fortunately, the two extreme phi can be computed in closed form, so there is no need for computing it numerically; nevertheless, the expressions are not very simple. The inference of these expressions can be seen in the python code at the end of this post.

    The case when the polygon is convex is simpler, because the impact point can never be exactly a corner (polygon point). This is the only case where the full code can be shown here (the other case is in a hidden snippet)

    let xComputedCollision = null, yComputedCollision = null;
    function computeNextImpact(){
       xComputedCollision = null; yComputedCollision = null;
       let shortestTimeTillImpact = 1/0;
       let nextImpactedLineIndex = -1;
       const r0 = ball.radius;
       const rr = ball.vRadius;
       const vx = ball.vx;
       const vy = ball.vy;
       for (let i = 1; i < polygonVertices.length; i++) {
          if(i === impactedLineIndex){ // exclude current line
             continue;
          }
          const p1 = polygonVertices[i - 1];
          const p2 = polygonVertices[i];
          const x1 = p1.x;
          const y1 = p1.y;
          const x2 = p2.x;
          const y2 = p2.y;
          const xc = ball.x;
          const yc = ball.y;
    
          const x1c = x1 - xc, y1c = y1 - yc,
             /*x2c = x2 - xc,*/ y2c = y2 - yc,
             x12 = x1 - x2, y12 = y1 - y2;
    
          const sA = vy * x1c - vx * y1c,
             sB = - r0 * vy - rr * y1c,
             sC = r0 * vx + rr * x1c,
             sD = vy * x12 - vx * y12,
             sE = - rr * y12,
             sF = rr * x12;
    
          const getS = phi => {
             const cos_phi = Math.cos(phi),
                sin_phi = Math.sin(phi);
             return (sA + sB * cos_phi + sC * sin_phi) / (sD + sE * cos_phi + sF * sin_phi);
          }
    
          const tA = x1 * y2c - x2 * y1c  + xc * y12,
             tB = r0 * y12,
             tC = - r0 * x12,
             tD = vy * x12 - vx * y12,
             tE = -rr * y12,
             tF = rr * x12;
    
          const getT = phi => {
             const cos_phi = Math.cos(phi),
                sin_phi = Math.sin(phi);
             return (tA + tB * cos_phi + tC * sin_phi) / (tD + tE * cos_phi + tF * sin_phi);
          }
    
          // find the minimum of getT(phi)
          const phi_t1 = -2 * Math.atan((-y12 + Math.sqrt(x12**2 + y12**2))/x12),
             phi_t2 = 2 * Math.atan((y12 + Math.sqrt(x12**2 + y12**2))/x12),
             t1 = getT(phi_t1),
             t2 = getT(phi_t2);
          let tMin12 = Math.min(...[t1, t2].filter(t => t > 0));
          if(tMin12 < shortestTimeTillImpact){
             const phi4Min = (tMin12 === t1) ? phi_t1 : phi_t2;
             let s4Min = getS(phi4Min);
             if(s4Min >= 0 && s4Min <= 1){
                shortestTimeTillImpact = tMin12;
                xComputedCollision = x1 + (x2 - x1) * s4Min;
                yComputedCollision = y1 + (y2 - y1) * s4Min;
                nextImpactedLineIndex = i;
             }
          }
       }
    
       impactedLineIndex = nextImpactedLineIndex;
       //console.log('next impactedLineIndex =', impactedLineIndex);
    }
    

    Here's the modified snippet that demonstrates it:

    addEventListener("DOMContentLoaded", (event) => {
        let paused = false;
        const butPause = document.querySelector('#pause');
        butPause.onclick = function(){
            paused = !paused;
            butPause.innerText = paused ? 'Continue' : 'Pause';
            if(!paused){
                requestAnimationFrame(animate)
            }
        }
    
        // const curvePoints = getCurvePoints(points.flatMap(pair => pair), 0.5, 25, true);
        const canvas = document.getElementById('myCanvas');
        const ctx = canvas.getContext('2d');
    
        // Set canvas dimensions
        canvas.width = 240;
        canvas.height = 240;
        ctx.translate(10, 10);
    
        // Polygon vertices
        const polygonVertices = ensureClosed(regularPolygonVertices(12, 100, { x: 100, y: 100 }));
        const centroid = calculateCentroid(polygonVertices);
    
        const vAngle = Math.random() * 2 * Math.PI;
        const vMag = 30;
        const maxVelComp = 30;
        let previousTime;
        let msSinceLastInflation = 0;
    
        let ball = {
            // Start ball at the centroid of the polyline.
            x: centroid.x,
            y: centroid.y,
            radius: 5,
            vx: vMag * Math.cos(vAngle),
            vy: vMag * Math.sin(vAngle),
            lastLineCollidedWith: -1,
            vRadius: 1,
        };
        let impactedLineIndex = -1;
        let speedFactor = 1; // set speedFactor > 1 to slow animation down when debugging fast cases
    
        // // paste here from console to start debugging from a problematic position
    
        // a case where there's a pixel difference between the computed algorithm and the graphic algorithm that is not
        // registering the collision with the segment #11
        // ball = {"x":110.73846059486802,"y":83.04583390045451,"radius":77.03340000000092,"vx":12.9864269010454,"vy":27.043533725158856,"lastLineCollidedWith":10,"vRadius":1};
        // impactedLineIndex = 12;
        // speedFactor = 10
    
    
        function draw() {
            ctx.clearRect(0, 0, canvas.width, canvas.height);
    
            // Draw the polygon (will become the circle trace)
            for (let i = 1; i < polygonVertices.length; i++) {
                ctx.beginPath();
                ctx.moveTo(polygonVertices[i - 1].x, polygonVertices[i - 1].y);
                ctx.lineTo(polygonVertices[i].x, polygonVertices[i].y);
                ctx.closePath();
                if (impactedLineIndex === i){
                    ctx.strokeStyle = 'green';
                }
                else {
                    ctx.strokeStyle = 'black';
                }
                ctx.lineWidth = 2;
                ctx.stroke();
            }
    
    
            // Draw the ball
            ctx.fillStyle = 'red';
            ctx.beginPath();
            ctx.arc(ball.x, ball.y, ball.radius, 0, 2 * Math.PI);
            ctx.closePath();
            ctx.fill();
    
            if(xComputedCollision !== null && yComputedCollision !== null){
                ctx.strokeStyle = 'green';
                ctx.lineWidth = 2;
                ctx.beginPath();
                ctx.arc(xComputedCollision, yComputedCollision, 2, 0, 2 * Math.PI);
                ctx.closePath();
                ctx.stroke();
            }
        }
    
        function handleCollisions() {
            const intersection = circlePolylineIntersection(ball, polygonVertices);
            // console.log(performance.measure('collision', 'start-collision', 'end-collision').duration);
            if (intersection != null && intersection.lineIndex != ball.lastLineCollidedWith) {
                const normal = { x: intersection.line.end.y - intersection.line.start.y, y: intersection.line.start.x - intersection.line.end.x };
                const normalMagnitude = Math.sqrt(normal.x * normal.x + normal.y * normal.y);
                const normalizedNormal = {
                    x: normal.x / normalMagnitude,
                    y: normal.y / normalMagnitude
                };
    
                const relativeVelocity = ball.vx * normalizedNormal.x + ball.vy * normalizedNormal.y;
    
                ball.lastLineCollidedWith = intersection.lineIndex;
                ball.vx = ball.vx - (2 * relativeVelocity * normalizedNormal.x);
                ball.vy = ball.vy - (2 * relativeVelocity * normalizedNormal.y);
                ball.vx = Math.max(-maxVelComp, Math.min(maxVelComp, ball.vx));
                ball.vy = Math.max(-maxVelComp, Math.min(maxVelComp, ball.vy));
                return true;
            }
            return false;
        }
    
        let xComputedCollision = null, yComputedCollision = null;
        function computeNextImpact(){
            console.log(`ball = ${JSON.stringify(ball)}; impactedLineIndex = ${impactedLineIndex};`)
            // this data (and the Pause button) allows us to restart the animation from the previous
            // impact, if an erroneous computation is detected visually
    
            xComputedCollision = null; yComputedCollision = null;
            let shortestTimeTillImpact = 1/0;
            let nextImpactedLineIndex = -1;
            const r0 = ball.radius;
            const rr = ball.vRadius;
            const vx = ball.vx;
            const vy = ball.vy;
            for (let i = 1; i < polygonVertices.length; i++) {
                if(i === impactedLineIndex){ // exclude current line
                    continue;
                }
                const p1 = polygonVertices[i - 1];
                const p2 = polygonVertices[i];
                const x1 = p1.x;
                const y1 = p1.y;
                const x2 = p2.x;
                const y2 = p2.y;
                const xc = ball.x;
                const yc = ball.y;
    
                const x1c = x1 - xc, y1c = y1 - yc,
                    /*x2c = x2 - xc,*/ y2c = y2 - yc,
                    x12 = x1 - x2, y12 = y1 - y2;
    
                const sA = vy * x1c - vx * y1c,
                    sB = - r0 * vy - rr * y1c,
                    sC = r0 * vx + rr * x1c,
                    sD = vy * x12 - vx * y12,
                    sE = - rr * y12,
                    sF = rr * x12;
    
                const getS = phi => {
                    const cos_phi = Math.cos(phi),
                        sin_phi = Math.sin(phi);
                    return (sA + sB * cos_phi + sC * sin_phi) / (sD + sE * cos_phi + sF * sin_phi);
                }
    
                const tA = x1 * y2c - x2 * y1c  + xc * y12,
                    tB = r0 * y12,
                    tC = - r0 * x12,
                    tD = vy * x12 - vx * y12,
                    tE = -rr * y12,
                    tF = rr * x12;
    
                const getT = phi => {
                    const cos_phi = Math.cos(phi),
                        sin_phi = Math.sin(phi);
                    return (tA + tB * cos_phi + tC * sin_phi) / (tD + tE * cos_phi + tF * sin_phi);
                }
    
                const phi_t1 = -2 * Math.atan((-y12 + Math.sqrt(x12**2 + y12**2))/x12),
                    phi_t2 = 2 * Math.atan((y12 + Math.sqrt(x12**2 + y12**2))/x12),
                    t1 = getT(phi_t1),
                    t2 = getT(phi_t2);
                let tMin12 = Math.min(...[t1, t2].filter(t => t > 0));
                if(tMin12 < shortestTimeTillImpact){
                    const phi4Min = (tMin12 === t1) ? phi_t1 : phi_t2;
                    let s4Min = getS(phi4Min);
                    if(s4Min >= 0 && s4Min <= 1){
                        shortestTimeTillImpact = tMin12;
                        xComputedCollision = x1 + (x2 - x1) * s4Min;
                        yComputedCollision = y1 + (y2 - y1) * s4Min;
                        nextImpactedLineIndex = i;
                    }
                }
            }
    
            impactedLineIndex = nextImpactedLineIndex;
            //console.log('next impactedLineIndex =', impactedLineIndex);
        }
    
        draw();
        requestAnimationFrame(animate);
    
        let pausedTime = null;
        function animate(currentTime) {
            if(paused){
                pausedTime = currentTime;
                return;
            }
            if(pausedTime !== null){
                previousTime += currentTime - pausedTime;
                pausedTime = null;
            }
            let collision = false;
            if (previousTime === undefined){
                setTimeout(computeNextImpact);
            }
            else{
                const timePerFrame = currentTime - previousTime;
                msSinceLastInflation += timePerFrame;
    
                ball.radius += ball.vRadius * (timePerFrame / 1000 / speedFactor);
    
                collision = handleCollisions();
                ball.x += ball.vx * (timePerFrame / 1000 / speedFactor);
                ball.y += ball.vy * (timePerFrame / 1000 / speedFactor);
            }
            previousTime = currentTime;
            draw();
            if(collision){
                // next impact should only be computed after a collision
                //setTimeout(computeNextImpact) // asynchronous
                computeNextImpact();
                if(ball.radius < 100*Math.cos(Math.PI/(polygonVertices.length-1))-1){
                    requestAnimationFrame(animate);
                }
            }
            else{
                requestAnimationFrame(animate);
            }
        }
    });
    
    
    
    function regularPolygonVertices(sides, radius, center = { x: 0, y: 0 }) {
        const vertices = [];
        const angle = 360 / sides;
    
        for (let i = 0; i < sides; i++) {
            const x = radius * Math.cos(Math.PI * i * angle / 180) + center.x;
            const y = radius * Math.sin(Math.PI * i * angle / 180) + center.y;
            vertices.push({ x: x, y: y });
        }
    
        return vertices;
    }
    
    function circlePolylineIntersection(circle, polyline) {
        performance.mark("start-collision");
        let closestIntersection = null;
        let closestDistance = Infinity;
    
        for (let i = 0; i < polyline.length - 1; i++) {
            if (circle.lastLineCollidedWith == i) {
                continue;
            }
            const p1 = polyline[i];
            const p2 = polyline[i + 1];
    
            // Calculate distance from circle center to segment
            const distance = pointLineDistance(circle.x, circle.y, p1.x, p1.y, p2.x, p2.y);
    
            // Check if the distance is less than or equal to the circle's radius
            if (distance <= circle.radius && distance < closestDistance) {
                closestDistance = distance;
                closestIntersection = {
                    lineIndex: i,
                    line: { start: p1, end: p2 },
                    point: pointOnLineClosestTo(circle.x, circle.y, p1.x, p1.y, p2.x, p2.y)
                };
            }
        }
    
        performance.mark("end-collision");
        return closestIntersection ? closestIntersection : null;
    }
    
    function pointLineDistance(px, py, x1, y1, x2, y2) {
        // Check if the point lies on the line segment
        if (isPointOnLineSegment(px, py, x1, y1, x2, y2)) {
            return 0;
        }
    
        // Calculate the perpendicular distance
        const dx = x2 - x1;
        const dy = y2 - y1;
        const u = ((px - x1) * dx + (py - y1) * dy) / (dx * dx + dy * dy);
    
        if (u < 0 || u > 1) {
            // The closest point is one of the endpoints
            const d1 = Math.sqrt((px - x1) * (px - x1) + (py - y1) * (py - y1));
            const d2 = Math.sqrt((px - x2) * (px - x2) + (py - y2) * (py - y2));
            return Math.min(d1, d2);
        }
    
        const ix = x1 + u * dx;
        const iy = y1 + u * dy;
        return Math.sqrt((px - ix) * (px - ix) + (py - iy) * (py - iy));
    }
    
    function pointOnLineClosestTo(px, py, x1, y1, x2, y2) {
        const dx = x2 - x1;
        const dy = y2 - y1;
        const u = ((px - x1) * dx + (py - y1) * dy) / (dx * dx + dy * dy);
    
        if (u < 0) {
            return { x: x1, y: y1 };
        } else if (u > 1) {
            return { x: x2, y: y2 };
        } else {
            return { x: x1 + u * dx, y: y1 + u * dy };
        }
    }
    
    function isPointOnLineSegment(px, py, x1, y1, x2, y2) {
        const v1x = px - x1;
        const v1y = py - y1;
        const v2x = x2 - x1;
        const v2y = y2 - y1;
    
        const cross = v1x * v2y - v1y * v2x;
        if (cross !== 0) {
            return false; // Point is not on the line
        }
    
        const dot = v1x * v2x + v1y * v2y;
        return dot >= 0 && dot <= v2x * v2x + v2y * v2y;
    }
    
    function calculateCentroid(polygon) {
        let signedArea = 0;
        let cx = 0;
        let cy = 0;
    
        for (let i = 0; i < polygon.length - 1; i++) {
            const xi = polygon[i].x;
            const yi = polygon[i].y;
            const xi1 = polygon[i + 1].x;
            const yi1 = polygon[i + 1].y;
    
            const factor = xi * yi1 - xi1 * yi;
            signedArea += factor;
            cx += (xi + xi1) * factor;
            cy += (yi + yi1) * factor;
        }
    
        signedArea *= 0.5;
        cx /= (6 * signedArea);
        cy /= (6 * signedArea);
    
        return { x: cx, y: cy };
    }
    
    function ensureClosed(polygon) {
        const clonedPolygon = [...polygon]; // Create a copy of the polygon
        // Ensure polygon is a closed polygon
        if (polygon[0] !== polygon[polygon.length - 1]) {
            clonedPolygon.push(polygon[0]);
        }
    
        return clonedPolygon;
    }
    <div>
       <button id="pause">Pause</button><br>
       <canvas id="myCanvas"></canvas>
    </div>

    In the non-convex case, things are much more complicated. Since a point with an angle > 180 can be exactly touched by the ball, that will happen rather frequently - if the ideal contact with a segment, that is the contact for min t would happen outside the segment, if the ball progresses past that point, the actual contact will happen at one of the ends of the segment. In the convex case it would never happen because the ball is bound to make contact with another segment before touching the end points of this one, so all contacts are inside contacts corresponding to min t for the segment that is touched first.

    However, in the non-convex case, these contacts have to be computed, hence the need to solve the equations s(phi) = 0 and s(phi) = 1 - (remember, s = 0 corresponds to point x1, y1 and s = 1 with point x2, y2). Fortunately, these too, have closed form solutions, as can be seen from the python sympy code.

    The code is the next snippet; further descriptions can't help much to its comprehension. Apparently there's a 30000 character limit to a post, so it has to be in a jsFiddle.

    Although the two code versions were tested and multiple missed cases where used to correct them, it is possible that there are some situations not covered. I added a continuous state display in the log, that will allow us to reproduce and repair a case when an incorrect computation was to be made. There were also cases found when the predicted contact differs from the one that happens with the original algorithm because of the approximations, e.g., if the radius were to be updated continuously, a contact would have been detected, while with the frame delay the ball brushes past tangentially.

    Sympy code use to perform the computations. It might take a few minutes to complete.

    import sympy as sym
    
    (xc, yc, vx, vy, r0, rr, x1, y1, x2, y2, t, s) = sym.symbols("xc yc vx vy r0 rr x1 y1 x2 y2 t s")
    phi = sym.Symbol("phi", real=True)
    
    eqx1 = xc + vx * t + (r0 + rr * t) * sym.cos(phi)
    eqy1 = yc + vy * t + (r0 + rr * t) * sym.sin(phi)
    
    eqx2 = x1 + (x2 - x1) * s
    eqy2 = y1 + (y2 - y1) * s
    
    sol = sym.solve([eqx1 - eqx2, eqy1 - eqy2], [t, s])
    solS = sol[s]
    print('s(phi) =', sym.together(solS))
    solT = sol[t]
    print('t(phi) =', sym.together(solT))
    
    print(80 * '-')
    print('Solutions for s(phi) = 0 ...')
    sol_s0 = sym.solve(solS, phi)
    print(sol_s0)
    
    print('Solutions for s(phi) = 1 ...')
    sol_s1 = sym.solve(solS - 1, phi)
    print(sol_s1)
    
    print(80 * '-')
    
    print('The values of phi for the extremes of t(phi) ...')
    dt = sym.diff(solT, phi)
    sol_t = sym.solve(dt, phi)
    print(sol_t)