Wie der Scheitelpunkt einer Parabel drei Punkte berechnen
https://stackoverflow.com/questions/717762
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe drei X / Y-Punkte, die eine Parabel bilden. Ich muss einfach berechnen, was der Scheitelpunkt der Parabel ist, dass durch diese drei Punkte geht. Vorzugsweise ist eine schnelle Art und Weise, wie ich habe eine Menge von diesen Berechnungen zu tun!
Die "Ask A Scientist" Website bietet diese Antwort :
Die allgemeine Form einer Parabel durch die folgende Gleichung gegeben ist: A * x ^ 2 + x * B + C = Y, wobei A, B, C und beliebige reelle Konstanten sind. Sie haben drei Paare von Punkten, die (x, y) geordneter Paare. Ersetzen der x- und y-Werte für jeden Punkt in die Gleichung für eine Parabel. Sie werden drei lineare Gleichungen in drei Unbekannten erhalten, die drei Konstanten. Anschließend können Sie das System von drei Gleichungen leicht lösen für die Werte von A, B und C, und Sie werden die Gleichung der Parabel, die Ihre 3 Punkte schneidet. Der Scheitelpunkt ist, wo die erste Ableitung gleich 0 ist, ein wenig Algebra ergibt:. (-B / 2 A, C - B ^ 2 / 4A) für den Scheitelpunkt
Es wäre schön tatsächlichen Code zu sehen, dass diese Berechnung in C # oder C ++ tut. Anybody?
Lösung
Das ist wirklich nur ein einfaches lineares Algebra Problem, so dass man symbolisch die Berechnung zu tun. Wenn Sie in den x- und y-Werten der drei Punkte ersetzen, werden Sie drei lineare Gleichungen in drei Unbekannten erhalten.
A x1^2 + B x1 + C = y1
A x2^2 + B x2 + C = y2
A x3^2 + B x3 + C = y3
Der einfachste Weg, dies zu lösen, ist die Matrix invertieren
x1^2 x1 1
x2^2 x2 1
x3^2 x3 1
und multiplizieren sie mit dem Vektor
y1
y2
y3
Das Ergebnis dieser ist ... okay, nicht gerade alles so einfach ;-) ich es in Mathematica tat, und hier sind die Formeln in Pseudo-Code:
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
Wenn Sie alternativ die Matrix Mathematik numerisch tun wollten, würde Sie in der Regel wendet sie an einem linearen Algebra-System (wie ATLAS , obwohl ich nicht sicher bin, ob es C # / C ++ Bindungen).
hatAndere Tipps
Danke David, ich Ihren Pseudo-Code auf den folgenden C # -Code umgewandelt:
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);
}
Das ist das, was ich wollte. Eine einfache Berechnung der Parabel-Ecke. Ich werde später Integer-Überlauf behandeln.
Sie erhalten die folgenden drei Gleichungen durch direkte Substitution:
A*x1^2+B*x1+C=y1
A*x2^2+B*x2+C=y2
A*x3^2+B*x3+C=y3
Sie können dieses Problem lösen, indem darauf hingewiesen, dass dies auf das Matrixprodukt entspricht:
[x1^2 x1 1] [A] [y1]
|x2^2 x2 1|*|B| = |y2|
[x3^2 x3 1] [C] [y3]
Sie können also A erhalten, B und C durch die Matrix invertiert und die inverse mit dem Vektor auf der rechten Seite multipliziert wird.
Ich sehe, dass, während ich dieses John Rasch das geht mehr in die Tiefe auf tatsächlich die Lösung der Matrixgleichung Tutorial verknüpft hat Posting habe, so können Sie diese Anweisungen befolgen, um die Antwort zu bekommen. eine 3x3-Matrix Invertierung ist ganz einfach, so sollte dies nicht zu hart sein.
Hier ist ein Code in Fortran, die @ implementiert david-z und @ AZDean Lösung:
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
Ich habe etwas ähnliches wie @ piSHOCK Antwort getan, auch basierend auf @ AZDean Code. Wenn Sie es brauchen schwer zu laufen (oder es in Matlab wie mich zu verwenden), könnte dies die schnellste sein.
Meine Vermutung ist, dass 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
Das riecht wie Hausaufgaben. „Fragen Sie einen Wissenschaftler“ richtig eingeschaltet ist. Sagen Sie Ihre 3 Punkte (x1, y1), (x2, y2) und (x3, y3). Dann Sie drei lineare Gleichungen erhalten:
| M11 M12 M13 | | A | | Z1 | | M21 M22 M23 | * | B | = | Z2 | | M31 M32 M33 | | C | | Z3 |
Dabei gilt M 11 = x 1 2 , M 12 = x 1 M 13 = 1, z 1 = y 1 , und in ähnlicher Weise für die anderen beiden Reihen unter Verwendung von (x2, y2) und (x3 , y3) anstelle von (x1, y1).
Die Lösung dieses Systems von 3 Gleichungen geben Sie eine Lösung für A, B und C.
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)
Beim Laufen unter https://ideone.com/y0SxKU
#include <iostream>
using namespace std;
// calculate the vertex of a parabola given three points
// https://stackoverflow.com/q/717762/16582
// @AZDean implementation with given x values
void CalcParabolaVertex(int x1, int y1, int x2, int y2, int x3, int y3, double& xv, 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);
}
// @piSHOCK immplementation assuming regular x values ( wrong!!! )
void CalcParabolaVertex2( int y1, int y2, int y3, double& xv, double& yv)
{
double d1 = y1 - y2;
double d2 = y1 - y3;
double a = -d1 + 0.5 * d2;
double b = 2 * d1 - 0.5 * d2;
double c = -y1;
xv = -0.5 * b / a;
yv = c - 0.25 * b * b / a;
}
// corrected immplementation assuming regular x values
void CalcParabolaVertex3( int y1, int y2, int y3, double& xv, double& yv)
{
double d1 = y1 - y2;
double d2 = y1 - y3;
double a = d1 - 0.5 * d2;
double b = -2 * d1 + 0.5 * d2;
double c = y1;
xv = -0.5 * b / a;
yv = c - 0.25 * b * b / a;
}
int main() {
double xv, yv;
CalcParabolaVertex( 0, 100, 1, 500, 2, 200, xv, yv );
cout << xv <<" "<< yv << "\n";
CalcParabolaVertex2( 100, 500, 200, xv, yv );
cout << xv <<" "<< yv << "\n";
CalcParabolaVertex3( 100, 500, 200, xv, yv );
cout << xv <<" "<< yv << "\n";
return 0;
}
Ich habe ein paar Unit-Tests für negativ gerichteten Spitzen hinzugefügt: Laufen bei https://ideone.com/WGK90S
Wenn Sie eine Annahme machen, dass zum Beispiel x1 == 0, x2 == 1, x3 == 2, wenn eine Kurve lokal zu einem gewissen gleichmäßig abgetasteten Signal passend, dann @AZDean ‚s Code simlifies an:
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
