• Advertisement
Sign in to follow this  

Intersection test between two moving circles

This topic is 4612 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I want to do an intersection test between two moving circles. Not too hard but, one of them is moving in a circular motion. :) Other solutions are welcomed! This picture might clearify it a bit. (A is actually at the origin of the big circle but the constants are not that important.) # == plus sign So i have this: The two moving objects. C1 = A # Bt C2 = C # Dt r1 and r2 is the radius for the moving circles. Where: A = (A.x, A.y) Bt = (r * cos(a # bt), r * sin(a # bt)) (r is the distance from the center of the big circle to the circumference) C = (C.x, C.y) Dt = (D.x * t, D.y * t) deltaX = (C.x # D.x * t) - (A.x # r * cos(a # bt)) deltaY = (C.y # D.y * t) - (A.y # r * sin(a # bt)) Now I want to know if there is a t that satisfies this statement: sqrt(deltaX ^ 2 # deltaY ^ 2) == (r1 # r2) (the distance between the centers of the circles is equal to the sum of the radius and the objects are touching eachother) I've tried to solved this thing but I can't seem to get it right. Just by the definition of the problem, I can see that there should be a really simple solution to this problem. The problem should have at least two t values that are correct if a solution exists. I'm only interested in the first positive solution.

Share this post


Link to post
Share on other sites
Advertisement
wll...ive seen this problem before....youre algorithm is correct...is the distance between the two centerpoints less than or equal to the sum of the radii, however

sqrt(deltaX ^ 2 # deltaY ^ 2) == (r1 # r2)

is wrong...the ^ operator is an Exclusive or not a power operator

try:
sqrt(pow(deltaX,2) # pow(deltaY,2))

or

sqrt( deltaX * deltaX # deltaY * deltaY)

hope this helps

Share this post


Link to post
Share on other sites
Tang of the Mountain: It's just pseudo-code so ^ equals pow.

Share this post


Link to post
Share on other sites
you should probably state that...being as the operator you used....exists as another function altogether....the code works as I and you have stated...so I dont know what you are looking for...

Share this post


Link to post
Share on other sites
Quote:
Original post by __fold
Now I want to know if there is a t that satisfies this statement:

sqrt(deltaX ^ 2 # deltaY ^ 2) == (r1 # r2)



Share this post


Link to post
Share on other sites
you should realize that the distancefunction between the two circles is a periodic function, and there are potentially infinite solutions to the problem distance=0

one way to get a good approximation is to sample the distance function at a couple of points: say 3. at the start of your timeinterval, the middle and the end, then fit a quadratic polynnmal through it, and solve for its roots.

ideally you should check for the accuracy obtained and further refine the solution if so desired, although for sane rotationspeeds, one iteration will most likely be enough.

Share this post


Link to post
Share on other sites
Couldn't you take the instantaneous tangent velocity and use that in a ray-sphere intersection test (increasing one of the sphere's radius by the others, using the other sphere centre for the ray origin and the velocity vector for the ray direction) Just a thought.

Share this post


Link to post
Share on other sites
Quote:
Original post by Eelco
you should realize that the distancefunction between the two circles is a periodic function, and there are potentially infinite solutions to the problem distance=0


Yes, I understand that but I hoped that there was a way to obtain the "first" positive solution or a solution where t is in a specified range, (0, 1] for instance.

Quote:
Original post by Eelco
one way to get a good approximation is to sample the distance function at a couple of points: say 3. at the start of your timeinterval, the middle and the end, then fit a quadratic polynnmal through it, and solve for its roots.


That is a really good idea!

Quote:
Original post by Eelco
ideally you should check for the accuracy obtained and further refine the solution if so desired, although for sane rotationspeeds, one iteration will most likely be enough.


For my purpose, I don't think I have to refine it.

Thanks alot!

Share this post


Link to post
Share on other sites
Quote:
Original post by moagstar
Couldn't you take the instantaneous tangent velocity and use that in a ray-sphere intersection test (increasing one of the sphere's radius by the others, using the other sphere centre for the ray origin and the velocity vector for the ray direction) Just a thought.


Hmm, I have to think about this. I'm not sure I understand what you mean.

Share this post


Link to post
Share on other sites
Quote:
Original post by __fold
Quote:
Original post by Eelco
you should realize that the distancefunction between the two circles is a periodic function, and there are potentially infinite solutions to the problem distance=0


Yes, I understand that but I hoped that there was a way to obtain the "first" positive solution or a solution where t is in a specified range, (0, 1] for instance.

well, no analitical solution anyway. and as with every numerical method, you should make sure the roots youve found are the roots you were actually looking for. now that isnt much of a problem when youre solving a quadratic, but this quadratic will only make sense for low rotationspeeds. if the distancefunction has three roots in the timeinterval youre examining, you can be pretty sure this quadratic approximation is utter bullshit. however, this can only happen if the rotationspeed exceeds 2Pi/update, which is insane, but regardless of that youd better do some testing on how accuracy correlates with speed, to make sure if its an issue or not.

Quote:

Thanks alot!

np.

Share this post


Link to post
Share on other sites
"however, this can only happen if the rotationspeed exceeds 2Pi/update, which is insane, but regardless of that youd better do some testing on how accuracy correlates with speed, to make sure if its an issue or not."

The rotationspeed can't exceed 1Pi/update and I don't think it will become close to it either.

Share this post


Link to post
Share on other sites
Eelco: I just realized that quadratic functions doesn't always work. If my points are (0, 1), (1, 0) and (0, -1) then there is no way that I can fit a quadratic function through those points. I can rotate the points to solve it though (in this case with Pi/2).

Share this post


Link to post
Share on other sites
Quote:
Original post by __fold
Eelco: I just realized that quadratic functions doesn't always work. If my points are (0, 1), (1, 0) and (0, -1) then there is no way that I can fit a quadratic function through those points. I can rotate the points to solve it though (in this case with Pi/2).


assuming your fist coordinate is interpreted as time: how exactly do you picture a distance at t=0 that is both 1 and -1 at the same time?

a distance function is always a continuous function, and it has only one scalar output for any given (also scalar) input.

Share this post


Link to post
Share on other sites
Quote:
Original post by Eelco
Quote:
Original post by __fold
Eelco: I just realized that quadratic functions doesn't always work. If my points are (0, 1), (1, 0) and (0, -1) then there is no way that I can fit a quadratic function through those points. I can rotate the points to solve it though (in this case with Pi/2).


assuming your fist coordinate is interpreted as time: how exactly do you picture a distance at t=0 that is both 1 and -1 at the same time?

a distance function is always a continuous function, and it has only one scalar output for any given (also scalar) input.


You are right!
My brain just disconnected there for a while... :)
Now I'm back.

Thank you!

Share this post


Link to post
Share on other sites
Well, this distance function turned out to be a big disappointment :(

I have this distance function F(t) and the range is [0, 1].

From sampling I get this:
F(0) = 1
F(0.5) = 0.71
F(1) = 1

But the true maximum value in the specified range is a bit higher than 1 and the big problem is that the minimum value is a negative number. This gives that two roots (intersections) are undetected. It will simple not work at all.

Share this post


Link to post
Share on other sites
1: are your units seconds, and if so, isnt 1 second a tad much for one intergrationstep?
2: what is your distance function?
3: what are its parameters, and are they realistic?

Share this post


Link to post
Share on other sites
Quote:
Original post by Eelco
1: are your units seconds, and if so, isnt 1 second a tad much for one intergrationstep?
2: what is your distance function?
3: what are its parameters, and are they realistic?


I'm in a bit of hurry but..

1: 1 t is 1/60s

2: It becomes a wave function where the center of the wave raises by the time.

3: Here is the problem. I have a hard time getting any values that I can use to get a nice quadratic polynom. They are not realistic but maybe I can make better samples. That would help alot. I have to think about this.

Share this post


Link to post
Share on other sites
say we have one cicle rotating around the origin, and one other moving linearly from some point x. then the distancebetween them will simply be:

dp(t) = (x + v * t - vectorfromangle(alpha + omega * t) * radius)
distance(t) = |dp(t)| - (r1 + r2)

if you plug some realistic values into this, or atleast values that dont mess with our simplifications too much (omega < 1, omega*radius + |v| !>> r1 + r2 are some good guidelines), things should work out.

Share this post


Link to post
Share on other sites
That is what I'm doing but it becomes bad.

I guess i found one of the worst cases right away.



This case is when one of circles moves along Pi * t where t is in the range [0, 1] and the other circle moves along a vector from origo to (-t, t).

Now i sampled dp(0), dp(0.5) and dp(1.0) (the red lines) and as you can see I fail to get a quadratic function that include the interesting values.

Share this post


Link to post
Share on other sites
Quote:
Original post by __fold
That is what I'm doing but it becomes bad.

I guess i found one of the worst cases right away.



This case is when one of circles moves along Pi * t where t is in the range [0, 1] and the other circle moves along a vector from origo to (-t, t).

Now i sampled dp(0), dp(0.5) and dp(1.0) (the red lines) and as you can see I fail to get a quadratic function that include the interesting values.


let me try again:

half a rotation per timestep is WAY beyond what this method can handle accuratly.

i told you so alreay, and you claimed this wasnt a problem because this would never occur. at 60fps, you realize this one cicle is spinning at 30 rotations per second, right? if thats really what you want, youll have to try a more accurate method.

as a start, i would try changing that t= [0, 1] to [0, 1/60], because thats probably what you want anyway.

Share this post


Link to post
Share on other sites
It could be done analytically. But that would be a pain. If you put the equations of motion, that should help

first circle.

rx(t) = rx + cos(w * t) * d
ry(t) = ry + sin(w * t) * d

=> R(t) = R + W(t)


px(t) = px + vx * t
py(t) = py + vy * t

=> P(t) = P + V(t)

(R(t) - P(t))^2 = r^2

([R - P] + [W(t) - V(t)])^2 - r^2 = 0

a.t^2 + b.t + c = 0

c = (R - P)^2 - r^2
b = 2 * (R - P) . (W(t) - V(t))
a = (W(t) - V(t)) . (W(t) - V(t))
[W(t) - V(t)] = Vector(cos(w . t) * d- vx.t, sin(w . t) * d - vy.t);

[W(t) - V(t)]^2 = (cos(w . t) * d - vx.t)^2 + (sin(w . t) * d - vy.t)^2

develop and you get another complicated equation, that you should be able to reduce down to an equation in t^2 and t. Using taylor series to approximate the trig functions will give you an equaiton in an even higher order.

same for calculating b. That should give you another second order trig function.

all in all, you will endup with possibly a 4th or 6th order equation, which will be a major pain in the neck.

Bottom line, I'd use an iterative solution that would sample the frame into smaller bits, and possibly recursively subdivide time until the two circles are at a threshold distance form each other. Simpler, and quite possibly cheaper, at the price of a small error (however, the speed of the calculation can be balanced against accuracy of the result, which is always nice to have).

Then all you need is a distance function, which is damn simple for two circles.

Also, this can be adapted for any kind of object trajectories.

Share this post


Link to post
Share on other sites
Quote:
Original post by Eelco
at 60fps, you realize this one cicle is spinning at 30 rotations per second, right? if thats really what you want, youll have to try a more accurate method.


Yes I do, and that's why I actually wanted to have an exact solution from the beginnng. And still, as my image show, your solution will only work if you get a sample where the circles intersect with eachother.


Quote:
Original post by oliii
It could be done analytically. But that would be a pain. If you put the equations of motion, that should help


I tried it, more for fun than for actually expecting something from it. It becomes pretty nasty.

It can be simplified to

deltaX = A + B * t + C * cos (a * t)
deltaY = D + E * t + F * cos (a * t)

(t is the only unknown variable)

And then:

deltaX ^2 + deltaY ^ 2 == R1 + R1

Iff there is a solution.


Thanks for all the help!

Share this post


Link to post
Share on other sites
Quote:
Original post by __fold
Quote:
Original post by Eelco
at 60fps, you realize this one cicle is spinning at 30 rotations per second, right? if thats really what you want, youll have to try a more accurate method.


Yes I do, and that's why I actually wanted to have an exact solution from the beginnng. And still, as my image show, your solution will only work if you get a sample where the circles intersect with eachother.


you do? not according to this:

Quote:

The rotationspeed can't exceed 1Pi/update and I don't think it will become close to it either.


so it seems youve changed your mind. a reminder: exact solutions dont exist in computers. youd have to ask yourself: what is good enough? as i mentioned earlier, you could increase the number of samples you take in the interval based on the amount of movement that takes place in this interval. (omega*radius+|velocity|)*timestep will give you an upper cap for the amount of relative movement, which linearly correlates with the amount samples youll need for a reasonable approximation.

clearly for the case youre interested in, a rotationspeed of around 30 rotations/second, youre going to need more than one sample, something around ten per update id say. note though that accuracy is usually of relatively little concern in such a situation, because you wont be able to see shit at such speeds anyway.

Share this post


Link to post
Share on other sites
Quote:
Original post by __fold
Quote:
Original post by Eelco
at 60fps, you realize this one cicle is spinning at 30 rotations per second, right? if thats really what you want, youll have to try a more accurate method.


Yes I do, and that's why I actually wanted to have an exact solution from the beginnng. And still, as my image show, your solution will only work if you get a sample where the circles intersect with eachother.


Quote:
Original post by oliii
It could be done analytically. But that would be a pain. If you put the equations of motion, that should help


I tried it, more for fun than for actually expecting something from it. It becomes pretty nasty.

It can be simplified to

deltaX = A + B * t + C * cos (a * t)
deltaY = D + E * t + F * cos (a * t)

(t is the only unknown variable)

And then:

deltaX ^2 + deltaY ^ 2 == R1 + R1

Iff there is a solution.


Thanks for all the help!


Yes there is a solution. As I said, it would be a polynomial of at least power of 6 (if decomposing sine and cosine into taylor series). Or a very complex trig function that could simplify to something meaningful, but I doubt.

If you come up with an equation for t, then good luck, first to find the correct equation, and second to solving it.

the equation, again, is

- sphere on circular path (centre (x1, y1), path radius d1, andgular velocity a1, sphere radius r1)

- sphere on linear path (centre (x2, y2), velocity (vx2, vy2), sphere radius r2)

deltaX = x1 + cos(a1 * t) * d1 - (x2 + vx2 * t);
deltaY = y1 + sin(a1 * t) * d1 - (y2 + vy2 * t);

(deltaX)^2 + (deltaY)^2 - (r1 + r2)^2 = 0;

now, for fun, you should be able to easily plot a graph f(t) = (deltaX)^2 + (deltaY)^2 - (r1 + r2)^2, for given values of x1, x2, y1, y2, ....

Everytime f(t) = 0, there is a solution. That will give you an idea for the complexity of the otherall solution.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement