Question related to projectile motion

[Aldehyde]

Hi guys.

I have a problem, where there are 400 parabolas, each varying slightly, and a point marked on a map. I'd like to find which of these 400 parabolas has a point that gets the closest to the point I have marked.

At the moment I am running through each parabola with 0.05 time intervals between each step to find which parabola contains the closest point, it's not too slow, eating up 20ms at MAX on a Pentium 4M 2.2ghz, that's within x of 800 pixels and y of 5000 pixels.

What I was wondering, is if there is some sort of formula or 'trick' I can use to tell which of these parabolas would be the best choice without having to run through them all.

Thanks in advance.

[jim mcnamara]

Your parabolas should each have two x-intercepts, the points: where it starts, where it hits the ground. Solve each parabola for the x-intercepts (ie., y=0 or whatever y is at the impact point of the projectile). Pick the parabola that has the x-intercept closest to where you have {x,y} set on the map

http://tutorial.math.lamar.edu/AllBrowsers/1314/Parabolas.asp

[Aldehyde]

Thanks for your help, and although it would work if the target were on y=0, it's not.. so other parts of the parabola may be closer to the target. But using a similar concept (solving where the parabola intercepts the y of the target) I've managed to get the desired results.

Thanks!

[Aldehyde]

Ah, I heard it would be possible to use Euler Approximation in order to determine the parabola which would contain a point closest to the target.. Any ideas?

[VBAhack]

If you have the equation of each parabola and the x,y coordinates of the point, I believe there is an analytical way to do this. If you express the distance from the point (x1,y1) to a point p (x,y) on the parabola, you can write an expression for the distance (or distance squared), take the derivative and set = 0. The resulting equation is a cubic that should be able to be solved for the roots (i.e. x value corresponding to the minimim distance from the point to the parabola). You'd end up having to do this for all parabolas to find out which is closer, but this might be faster than the method you are using.

[VBAhack]

Expanding on my previous post, I created a function to find the miniminum distance from an arbitrary point to a parabola using a closed for solution. Depending on how many samples you take for each parabola, this could be substantially faster. I did a time trial using just 20 points for each parabola, and this method is 4x faster. Check it out.

Function MinDist(a As Double, b As Double, c As Double, x1 As Double, y1 As Double) As Double
'Find minimun square of distance (d^2) from arbitrary point (x1,y1) to a parabola
'Find min d^2 = (x-x1)^2 + (y-y1)^2, where y = ax^2 + bx + c
'Find x such that d/dx (d^2) = 0. Need to find roots of 3rd order polynomial
'Roots of cubic equation from http://mathworld.wolfram.com/CubicFormula.html
Dim a0 As Double, a1 As Double, a2 As Double, q As Double, R As Double, D As Double
Dim Theta As Double, x As Double, sol As Double, dist As Double
Dim xSave As Double, distSave As Double, pi As Double
Dim S As Double, T As Double, K As Double

pi = 4 * Atn(1)
a2 = 1.5 * b / a
a1 = (2 * a * c + b * b - 2 * a * y1 + 1) / (2 * a ^ 2)
a0 = (b * c - b * y1 - x1) / (2 * a * a)
q = (3 * a1 - a2 * a2) / 9
R = (9 * a2 * a1 - 27 * a0 - 2 * a2 * a2 * a2) / 54
D = q * q * q + R * R

If D < 0 Then
'3 real roots, need to find which results in min d^2
x = R / Sqr(-q * q * q)
Theta = Atn(-x / Sqr(-x * x + 1)) + 2 * Atn(1)

xSave = 2 * Sqr(-q) * Cos(Theta / 3) - a2 / 3
distSave = (a * xSave * xSave + b * xSave + c - y1) ^ 2 + (xSave - x1) ^ 2

sol = 2 * Sqr(-q) * Cos((Theta + 2 * pi) / 3) - a2 / 3
dist = (a * sol * sol + b * sol + c - y1) ^ 2 + (sol - x1) ^ 2

If dist < distSave Then
xSave = sol
distSave = dist
End If

sol = 2 * Sqr(-q) * Cos((Theta + 4 * pi) / 3) - a2 / 3
dist = (a * sol * sol + b * sol + c - y1) ^ 2 + (sol - x1) ^ 2

If dist < distSave Then
xSave = sol
distSave = dist
End If
Else
'one real root
K = R + Sqr(D)
If K < 0 Then
S = -(-K) ^ (1 / 3)
Else
S = K ^ (1 / 3)
End If

K = R - Sqr(D)
If K < 0 Then
T = -(-K) ^ (1 / 3)
Else
T = K ^ (1 / 3)
End If

xSave = -a2 / 3 + S + T
distSave = (a * xSave * xSave + b * xSave + c - y1) ^ 2 + (xSave - x1) ^ 2
End If

MinDist = Sqr(distSave)
End Function