Cómo calcular el vértice de una parábola dados tres puntos

Question

Tengo tres puntos X/Y que forman una parábola. Simplemente necesito calcular cuál es el vértice de la parábola que atraviesa estos tres puntos. ¡Preferiblemente de una manera rápida ya que tengo que hacer MUCHOS de estos cálculos!

El "Pregunta A Scientist" sitio web proporciona this answer:

La forma general de una parábola es dada por la ecuación: A * x^2 + B * x + C = Y en la que A, B, y C son constantes reales arbitrarias. Tienes tres pares de puntos que son (x, y) pares ordenados. Sustituye los valores x e y de cada punto en la ecuación para una parábola. Obtendrás tres ecuaciones LINEALES en tres incógnitas, las tres constantes. A continuación, puede resolver fácilmente este sistema de tres ecuaciones para los valores de A, B y C, y tendrá la ecuación de la parábola que cruza sus 3 puntos. El vértice es donde la primera derivada es 0, una pequeña álgebra da: (-B/2A, C - B^2/4A) para el vértice.

Sería bueno ver el código real que hace este cálculo en C# o C++. ¿Nadie?

Answer 1

Esto es realmente solo un problema de álgebra lineal simple, por lo que puede hacer el cálculo de forma simbólica. Cuando sustituyes los valores x e y de tus tres puntos, obtendrás tres ecuaciones lineales en tres incógnitas.

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

La forma más sencilla de resolver esto es para invertir la matriz

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

y se multiplica por el vector

y1 
y2 
y3 

El resultado de esto es ... bueno, no exactamente todo eso simple ;-) Lo hice en Mathematica, y aquí están las fórmulas en pseudocódigo:

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 

Alternativamente, si quisiera hacer la matriz matemática numéricamente, normalmente recurriría a un sistema de álgebra lineal (como ATLAS, aunque no estoy seguro si tiene enlaces C#/C++).

Answer 2

Esto huele a tarea. "Ask a Scientist" está en lo cierto. Digamos que sus 3 puntos son (x1, y1), (x2, y2) y (x3, y3). Entonces, se obtiene tres ecuaciones lineales:

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

Dónde M = x , M = x , M = 1, Z = y , y de manera similar para las otras dos filas que usan (x2, y2) y (x3, y3) en lugar de (x1, y1).

Resolviendo este sistema de ecuaciones 3 le dará una solución para A, B, y C.

Answer 3

se obtienen los siguientes tres ecuaciones por sustitución directa:

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

puede resolver este observando que esto es equivalente a la matriz producto:

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

para que pueda obtener a, B, y C invirtiendo la matriz y multiplicando el inverso con el vector de la derecha.

Veo que mientras he estado publicando esto, John Rasch ha vinculado un tutorial que profundiza en la resolución de la ecuación matricial, por lo que puede seguir esas instrucciones para obtener la respuesta. Invertir una matriz de 3x3 es bastante fácil, así que esto no debería ser demasiado difícil.

Answer 4

Gracias David, que convierte el pseudocódigo para el siguiente código C#:

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); 
} 

Esto es lo que quería. Un simple cálculo del vértice de la parábola. Manejaré el desbordamiento de enteros más tarde.

Answer 5

Aquí es un código en Fortran que implementa @ David-Z y @ solución de AZDean:

subroutine parabola_vertex(x1, y1, x2, y2, x3, y3, xv, yv) 
real(dp), intent(in) :: x1, y1, x2, y2, x3, y3 
real(dp), intent(out) :: xv, yv 
real(dp) :: denom, A, B, C 
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 
xv = -B/(2*A) 
yv = C - B**2/(4*A) 
end subroutine 

Answer 6

def vertex(x1,x2,x3,y1,y2,y3): 
    '''Given three pairs of (x,y) points return the vertex of the 
     parabola passing through the points. Vectorized and common expression reduced.''' 
    #Define a sequence of sub expressions to reduce redundant flops 
    x0 = 1/x2 
    x4 = x1 - x2 
    x5 = 1/x4 
    x6 = x1**2 
    x7 = 1/x6 
    x8 = x2**2 
    x9 = -x7*x8 + 1 
    x10 = x0*x1*x5*x9 
    x11 = 1/x1 
    x12 = x3**2 
    x13 = x11*x12 
    x14 = 1/(x0*x13 - x0*x3 - x11*x3 + 1) 
    x15 = x14*y3 
    x16 = x10*x15 
    x17 = x0*x5 
    x18 = -x13 + x3 
    x19 = y2*(x1*x17 + x14*x18*x6*x9/(x4**2*x8)) 
    x20 = x2*x5 
    x21 = x11*x20 
    x22 = x14*(-x12*x7 + x18*x21) 
    x23 = y1*(-x10*x22 - x21) 
    x24 = x16/2 - x19/2 - x23/2 
    x25 = -x17*x9 + x7 
    x26 = x0*x1*x14*x18*x5 
    x27 = 1/(-x15*x25 + y1*(x20*x7 - x22*x25 + x7) + y2*(-x17 + x25*x26)) 
    x28 = x24*x27 
    return x28,x15 + x22*y1 + x24**2*x27 - x26*y2 + x28*(-x16 + x19 + x23) 

Answer 7

Si hace una suposición de que x1 == 0, x2 == 1, x3 == 2, por ejemplo, cuando el ajuste de una curva de forma local en cierta manera uniforme muestreado señal, entonces el código @AZDean 's simlifies a:

d1 = y1 - y2 
d2 = y1 - y3 

a = -d1 + 0.5 * d2 
b = 2 * d1 - 0.5 * d2 
c = -y1 

xVertex = -0.5  * b/a 
yVertex = c - 0.25 * b * b/a 

Answer 8

que he hecho algo similar a la respuesta de @ piSHOCK, también basado en el código de @ AZDean. Si necesita ejecutarlo en exceso (o usarlo en Matlab como yo), este podría ser el más rápido.

Mi hipótesis es que x1 == -1, x2 == 0, x3 == 1.

a = y2 - (y1 + y3)/2 % opposite signal compared to the original definition of A 
b = (y3 - y1)/4   % half of the originally defined B 

xExtr = b/a 
yExtr = y2 + b * yExtr % which is equal to y2 + b*b/a