views:

4396

answers:

6

I have three X/Y points that form a parabola. I simply need to calculate what the vertex of the parabola is that goes through these three points. Preferably a quick way as I have to do a LOT of these calculations!

The "Ask A Scientist" website provides this answer:

The general form of a parabola is given by the equation: A * x^2 + B * x + C = y where A, B, and C are arbitrary Real constants. You have three pairs of points that are (x,y) ordered pairs. Substitute the x and y values of each point into the equation for a parabola. You will get three LINEAR equations in three unknowns, the three constants. You can then easily solve this system of three equations for the values of A, B, and C, and you'll have the equation of the parabola that intersects your 3 points. The vertex is where the first derivative is 0, a little algebra gives: ( -B/2A , C - B^2/4A ) for the vertex.

It would be nice to see actual code that does this calculation in C# or C++. Anybody?

+2  A: 

Here is an example using matrices (scroll about half-way down):

http://www.codeproject.com/KB/cs/LinearEquationsSystemSoln.aspx

John Rasch
This was helpful too. It is so much easier to work with actual code.
AZDean
A: 

This smells like homework. "Ask a Scientist" is right on. Say your 3 points are (x1, y1), (x2, y2), and (x3, y3). Then, you get three linear equations:

| M11 M12 M13 |   | A |   | Z1 |
| M21 M22 M23 | * | B | = | Z2 |
| M31 M32 M33 |   | C |   | Z3 |

Where M11 = x12, M12 = x1, M13 = 1, Z1 = y1, and similarly for the other two rows using (x2, y2) and (x3, y3) in place of (x1, y1).

Solving this system of 3 equations will give you a solution for A, B, and C.

Adam Rosenfield
+1  A: 

You get the following three equations by direct substitution:

A*x1^2+B*x1+C=y1
A*x2^2+B*x2+C=y2
A*x3^2+B*x3+C=y3

You can solve this by noting that this is equivalent to the matrix product:

[x1^2 x1 1] [A]   [y1]
|x2^2 x2 1|*|B| = |y2|
[x3^2 x3 1] [C]   [y3]

So you can get A,B, and C by inverting the matrix and multiplying the inverse with the vector on the right.

I see that while I've been posting this John Rasch has linked to tutorial that goes into more depth on actually solving the matrix equation, so you can follow those instructions to get the answer. Inverting a 3x3 matrix is quite easy, so this shouldn't be too tough.

kvb
+2  A: 

This is really just a simple linear algebra problem, so you can do the calculation symbolically. When you substitute in the x and y values of your three points, you'll get three linear equations in three unknowns.

A x1^2 + B x1 + C = y1
A x2^2 + B x2 + C = y2
A x3^2 + B x3 + C = y3

The straightforward way to solve this is to invert the matrix

x1^2  x1  1
x2^2  x2  1
x3^2  x2  1

and multiply it by the vector

y1
y2
y3

The result of this is... okay, not exactly all that simple ;-) I did it in Mathematica, and here are the formulas in pseudocode:

denom = (x1 - x2)(x1 - x3)(x2 - x3)
A = (x3 * (y2 - y1) + x2 * (y1 - y3) + x1 * (y3 - y2)) / denom
B = (x3^2 * (y1 - y2) + x2^2 * (y3 - y1) + x1^2 * (y2 - y3)) / denom
C = (x2 * x3 * (x2 - x3) * y1 + x3 * x1 * (x3 - x1) * y2 + x1 * x2 * (x1 - x2) * y3) / denom

Alternatively, if you wanted to do the matrix math numerically, you'd typically turn to a linear algebra system (like ATLAS, though I'm not sure if it has C#/C++ bindings).

David Zaslavsky
A: 

Thanks David, I converted your pseudocode to the following C# code:

public static void CalcParabolaVertex(int x1, int y1, int x2, int y2, int x3, int y3, out double xv, out double yv)
{
 double denom = (x1 - x2) * (x1 - x3) * (x2 - x3);
 double A     = (x3 * (y2 - y1) + x2 * (y1 - y3) + x1 * (y3 - y2)) / denom;
 double B     = (x3*x3 * (y1 - y2) + x2*x2 * (y3 - y1) + x1*x1 * (y2 - y3)) / denom;
 double C     = (x2 * x3 * (x2 - x3) * y1 + x3 * x1 * (x3 - x1) * y2 + x1 * x2 * (x1 - x2) * y3) / denom;

 xv = -B / (2*A);
 yv = C - B*B / (4*A);
}

This is what I wanted. A simple calculation of the parabola's vertex. I'll handle integer overflow later.

AZDean
A: 

This answer shows how Wolfram Alpha can invert that matrix for you symbolically.

duffymo