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.
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?
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):
- the ball radius
r = r0 + rr * t - the ball current center
xc,yc - the ball velocity
vx,vy - the ball center after time
t:xc + vx * t,yc + vy * t - the parametric equations for the circumference of the ball:
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
- the segment under consideration, from
(x1, y1)to(x2, y2) - its parametric equations:
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)
- ENOLOCK npm ERR! Error while running npm audit fix
- javascript onsubmit not working
- Embed image in email body nodemailer nodejs
- Detect Back Button in Navigation Guards of Vue-Router
- Error: Could not access built-in Node.js modules
- Failed to execute removeChild on Node
- Error: Cannot find module 'node:util' while running the nuxt project using npm run command
- Recharts issue with gaps between Bars
- google closure compiler - double compilation
- Which library should I use for server-side image manipulation on Node.JS?
- Stop propagation of 'click' event in Leaflet
- Creating new objects from frozen parent objects
- How to redirect to an "about:" URL
- How to convert FormData (HTML5 object) to JSON
- dynamically pass unknown number of parameters to react router
- What is the difference between a comparison operator and a logical operator?
- How to convert date to timestamp?
- Context Provider Specification
- Get previous page phonegap javascript
- Displaying date/time in user's timezone - on client side
- Google App Script to imitate File - Import csv file into a sheet using a custom menu item
- Intl.NumberFormat alter minus symbol
- Loading data server side and allow global access client side
- Set default value of Javascript object attributes
- Vue3 @update:modelValue NOT working on objects?
- Failed to resolve component: google-pay-button
- Vue.js 3 - instance without a component?
- When to use const with objects in JavaScript?
- Vue.js iterate complex object by data key
- Vuejs 3 query value in Json Object based on key