June 27th, 2001


for any math majors out there (or anyone interested)

Given: One plane.

Two circles on the plane. Each with:
A starting position.
A velocity.
A radius.

Construct an algorithm to determine if and when the circles first touch.

False starts:

"just see if the circles are closer than the sum of their radiuses!"

Fails rather dramatically, because how often do you test? Once per time unit? Start a circle at the origin, with radius 1. Start another circle three units along positive X, with radius 1. The first circle doesn't move. The second circle moves towards negative X at a speed of five billion physical-units per time-unit. Goes right past.

"Brute-force it - just check as many times as you need to to be certain."

Fails rather dramatically too - this is meant for a real-time simulation. Ouch. No.

"Make an equation to solve the distance between the circles based on time!" Here's the equation I came up with:

sqrt( ( ( XS1 + T * XV1 ) - ( XS2 + T * XV2 ) ) ^ 2 + ( ( YS1 + T * YV1 ) - ( YS2 + T * YV2 ) ) ^ 2 ) = R1 + R2

Solve for T.

Um, no >_<

Various other attempts have included coming up with the area they *might* intersect in and testing there - unfortunately, out of the two variations I've managed of this, one of them had a serious flaw that could keep it from detecting a collision altogether, and one of them ended up being little better than the brute-force method.

Something that might be useful for people better at math than I am: Consider it a three-dimensional space (with time in the 2d world being, in effect, the third dimension here). Now you've just got a pair of skewed cylinders - see if they intersect.

So. Any ideas? Tira, could you point GD at this entry? Since now I remember why "just make an equation" fails so miserably :) And maybe Sam if she's interested in tackling it . . . your call. Or, hey, anyone else. Note that I've asked my linear algebra prof at Oberlin, and he came up with about all those things I've got up there and gave up :) In fact, if *anyone* knows a math prodigy . . . I've sure never managed to solve this one, but it looks so easy! does anyone know if it's unsolvable for some reason?

Note to people trying to solve it - make sure it covers *all* possibilities. Consider circles scraping by at odd angles, both barely touching and barely missing. Even if you've got something not-quite-perfect, tho, I'm interested . . .

I've got another problem later on, if people want to try it :P Be warned, I think it's tougher :)

On other news . . . I'm gonna send a message to my ex. And it might be angry, and she'll probably never want to talk to me again. So it goes. I gotta wrap up these loose ends so maybe I'll be able to move on . . . if I'm lucky :/

being lonely sucks, and I want it to stop.
  • Current Mood
    determined determined