Calculate the time when a moving ball collides with a moving line / polygon (2D)

Question

I have a polygon inside which there is a moving ball. The ball must be returned if it hits the border.

My current “solution”: I break the polygon into lines and figure out when the ball hits a moving line

all variables:

a = length of a b = length of b c = length of c ax = x position of A ay = y position of A bx = x position of B by = y position of B cx = x position of C cy = y position of C vax = speed of A on the x-axis vay = speed of A on the y-axis vbx = speed of B on the x-axis vby = speed of B on the y-axis vcx = speed of C on the x-axis vcy = speed of C on the y-axis h = height (equals r, because it collides when h is r) r = radius t = time (one time unit equals 1 frame. not relevant) axc = x positon of A at the collision ayc = y positon of A at the collision bxc = x positon of B at the collision byc = y positon of B at the collision cxc = x positon of C at the collision cyc = y positon of C at the collision 

• Calculate the collision position of all points:

  axc:=ax+vax*t ayc:=ay+vay*t

  bxc:=bx+vbx*t byc:=by+vby*t

  cyc:=cy+vcy*t cxc:=cx+vcx*t

• Calculate the length of all vertices

  a:=√((axc-cxc)^(2)+(ayc-cyc)^(2))

  b:=√((bxc-cxc)^(2)+(byc-cyc)^(2))

  c:=√((axc-bxc)^(2)+(ayc-byc)^(2))

• Calculate h

  h=((√(2*(a^(2)*b^(2)+b^(2)*a^(2)+c^(2)*a^(2))-(a^(4)+b^(4)+c^(4))))/(2*c))

• Decide for t

  solve(h=((√(2*(a^(2)*b^(2)+b^(2)*a^(2)+c^(2)*a^(2))-(a^(4)+b^(4)+c^(4))))/(2*c)), t)

BUUUUUT: My calculator (Ti-Nspire CX CAS) is dropping. And Microsoft Mathematics takes waaay too long (I'm counting right now ... for 1 hour and nothing else ...)

So ... HELP!

(Do not question my drawing skills)

Answer 1

If your polygon is convex and all speeds remain constant all the time, you can use these series of tricks I just came up with (so there is probably a better way):

1) Replace each line with an infinitely long line, just expanding it.

You can only do this if the polygon is convex. Consider the following image:

Red lines are the original polygon, green is infinite expansion. Can a circle ever hit the green line before it hits the red line? Not. Now we can focus on the ball, striking infinitely long lines, which (at least for me) are an easier task.

2) Calculate the collision time with each line separately, then select the minimum

If we want to know if and when a perfectly round ball falls into a line, we can easily decide if a point falls into a line instead, consider the following image:

Usually the circle falls into the line when the center enters the area around this line, where the area is all points that do not exceed the radius of the line, where radius is the radius of the circle.

So, we can go and simply replace the circle with one point in the center and move the line to the newly created point with a radius.

3) Calculate when a moving point hits a moving line

If the line is defined by two moving points a and b with speeds va and vb , and the point is at point c with speed vc , we can make point a stationary (not moving) and in position (0,0) by replacing other locations and speeds of two points on ba , vb-va and ca , vc-va .

Now, let us denote the new coordinates and velocities of b and c as follows: [bx, by] , (vbx, vby) and [cx, cy] , (vcx, vcy) . Now we can find out the collision time by solving this formula:

 cx+t * vcx = s*bx + s*t*vbx cy+t * vcy = s*by + s*t*vby 

However, be careful: this leads to a quadratic equation, and you should ignore possible negative solutions, which may mean that the point is moving away from the line or that the collision is happening right now, so make sure that the ball isn’t already colliding before starting that anything to do.

Also (I hope there is no need to talk about it) after replacing t and s , you will not get the end point of the collision, you need to cancel all the easements that you have done (add a for example)

If you need this for non-convex polygons, I have a workaround, so write in the comments.