Come calcolare il vertice di una parabola dato tre punti

Question

Ho tre punti X/Y che formano una parabola. Ho semplicemente bisogno di calcolare quale sia il vertice della parabola che attraversa questi tre punti. Preferibilmente un modo veloce in quanto devo fare un sacco di questi calcoli!

Il sito "Posta A Scientist" prevede this answer:

La forma generale di una parabola è data dall'equazione: A * x^2 + B * x + C = y dove A, B, e C sono costanti reali arbitrarie. Hai tre coppie di punti che sono (x, y) coppie ordinate. Sostituisci i valori xey di ciascun punto nell'equazione per una parabola. Otterrai tre equazioni LINEAR in tre incognite, le tre costanti. Puoi quindi facilmente risolvere questo sistema di tre equazioni per i valori di A, B e C, e avrai l'equazione della parabola che interseca i tuoi 3 punti. Il vertice è dove la prima derivata è 0, una piccola algebra dà: (-B/2A, C - B^2/4A) per il vertice.

Sarebbe bello vedere il codice effettivo che esegue questo calcolo in C# o C++. Chiunque?

Answer 1

Questo è davvero solo un semplice problema di algebra lineare, quindi è possibile eseguire il calcolo simbolicamente. Quando sostituisci i valori xey dei tuoi tre punti, otterrai tre equazioni lineari in tre incognite.

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

Il modo semplice per risolvere questo è di invertire la matrice

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

e moltiplicarlo per il vettore

y1 
y2 
y3 

Il risultato di questo è ... ok, non esattamente tutto questo semplice ;-) L'ho fatto in Mathematica, e qui ci sono le formule in pseudocodice:

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 

In alternativa, se si desidera eseguire numericamente la matrice matematica, di solito si passa a un sistema di algebra lineare (come ATLAS, anche se non sono sicuro che abbia i collegamenti C#/C++).

Answer 2

Questo odora di compiti a casa. "Chiedi a uno scienziato" è giusto. Dì che i tuoi 3 punti sono (x1, y1), (x2, y2) e (x3, y3). Poi, si ottengono tre equazioni lineari:

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

Dove M = x , M = x , M = 1, Z = y e analogamente per le altre due righe che utilizzano (x2, y2) e (x3, y3) al posto di (x1, y1).

Risolvendo questo sistema di 3 equazioni vi darà una soluzione per A, B, e C.

Answer 3

È possibile ottenere i seguenti tre equazioni di sostituzione diretta:

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

si può risolvere questo notando che questo è equivalente al prodotto di matrice:

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

modo da poter ottenere a, B, e C invertendo la matrice e moltiplicando l'inverso con il vettore sulla destra.

Vedo che mentre ho postato questo John Rasch si è collegato a un tutorial che approfondisce la risoluzione dell'equazione della matrice, in modo da poter seguire quelle istruzioni per ottenere la risposta. Invertire una matrice 3x3 è abbastanza facile, quindi non dovrebbe essere troppo difficile.

Answer 4

Grazie David, ho convertito il vostro pseudocodice al seguente codice 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); 
} 

Questo è quello che volevo. Un semplice calcolo del vertice della parabola. Gestirò l'overflow di interi in seguito.

Answer 5

Qui è un codice in Fortran che implementa @ David-Z e @ soluzione 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

Se si effettua un presupposto che x1 == 0, x2 == 1, x3 == 2, ad esempio quando si monta una curva a livello locale per alcuni uniformemente campionata segnale, quindi il codice @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

che ho fatto qualcosa di simile a @ risposta di piSHOCK, anche sulla base di @ AZDean codice. Se è necessario eseguirlo pesantemente (o usarlo in Matlab come me), questo potrebbe essere il più veloce.

La mia ipotesi è che 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