Как вычислить вершину параболы с учетом трех точек

У меня есть три точки X/Y, которые образуют параболу. Мне просто нужно вычислить, какая вершина параболы проходит через эти три точки. Желательно быстро, так как я должен выполнить много этих вычислений!

Веб-сайт "Ask A Scientist" предоставляет этот ответ:

Общий вид параболы задается уравнением: A * x ^ 2 + B * x + C = y, где A, B и C - произвольные вещественные постоянные. У вас есть три пары точек, которые являются (x, y) упорядоченными парами. Подставляя значения x и y каждой точки в уравнение для параболы. Вы получите три уравнения ЛИНЕЙНА с тремя неизвестными, тремя константами. Затем вы можете легко решить эту систему из трех уравнений для значений A, B и C, и вы получите уравнение параболы, которая пересечет ваши 3 точки. Вершина равна где первая производная равна 0, а небольшая алгебра дает: (-B/2A, C - B ^ 2/4A) для вершины.

Было бы неплохо увидеть фактический код, который выполняет этот расчет на С# или С++. Кто-нибудь?

Ответ 1

Это действительно простая проблема линейной алгебры, поэтому вы можете сделать вычисление символически. Когда вы подставляете значения x и y трех точек, вы получите три линейных уравнения с тремя неизвестными.

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

Прямым способом решить эту задачу является инвертирование матрицы

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

и умножьте его на вектор

y1
y2
y3

Результат этого... хорошо, не совсем все, что просто;-) Я сделал это в Mathematica, и вот формулы в псевдокоде:

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

В качестве альтернативы, если вы хотите сделать математическую математическую модель численно, вы обычно обращаетесь к системе линейной алгебры (например, ATLAS, хотя я не уверен, что у него есть привязки С#/С++).

Ответ 2

Спасибо Дэвиду, я преобразовал ваш псевдокод в следующий код С#:

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

Это то, что я хотел. Простой расчет вершины параболы. Я позже обработаю переполнение целых чисел.

Ответ 3

Вы получаете следующие три уравнения путем прямой подстановки:

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

Вы можете решить это, отметив, что это эквивалентно матричному продукту:

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

Таким образом, вы можете получить A, B и C, инвертируя матрицу и умножая обратный на вектор справа.

Я вижу, что, пока я публиковал это, Джон Раш связался с учебным пособием, в котором более подробно рассматривается решение матрицы, поэтому вы можете следовать этим инструкциям, чтобы получить ответ. Инвертирование матрицы 3x3 довольно просто, поэтому это не должно быть слишком жестким.

Ответ 4

Вот код в Fortran, который реализует решение @david-z и @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

Ответ 5

Это пахнет домашней работой. "Спросите ученого". Скажем, что ваши 3 точки (x1, y1), (x2, y2) и (x3, y3). Затем вы получаете три линейных уравнения:

| M₁₁ M₁₂ M₁₃ |   | A |   | Z₁ |
| M₂₁ M₂₂ M₂₃ | * | B | = | Z₂ |
| M₃₁ M₃₂ M₃₃ |   | C |   | Z₃ |

Где M ₁₁= x ₁² M ₁₂= x ₁, M ₁₃= 1, Z ₁= y ₁, и аналогично для двух других строк с использованием (x2, y2) и (x3, y3) вместо (x1, y1).

Решение этой системы из трех уравнений даст вам решение для A, B и C.

Ответ 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)

Ответ 7

Если вы сделаете предположение, что x1 == 0, x2 == 1, x3 == 2, например, при подгонке кривой локально к некоторому равномерно дискретизированному сигналу, тогда код @AZDean упрощает:

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