Минимизировать расстояние от набора точек до параболы

[oliver]

Задача:

Задано параболу $ax^2+bx+c$ и набор $k$ точек ${p_i=(x_i, y_i)}$.
Минимизыровать сумму квадратов расстояний от точек до параболы,
то есть найти такое смещение параболы ${(x_0, y_0)}$, чтобы сумма $\sum\limits_{i=1}^k d(p_i)^2$ была минимальной ($d(p)$ - расстояние от точки $p$ до сдвинутой параболы).
Для упрощения можно считать, что расстояние до параболы считается как разница $y$ (как в регрессионной модели), но хотелось бы использовать реальное расстояние.

При аналитическом решении получаются кубические уравнения (можно решыть через ф-лы Кардано). Поскольку задачу надо решыть на С++ (реальный проект, не учебный), возможно имеет смысл использовать какой либо алгоритм оптимизации (парабола уже является упрощением, в общем случае кривая задана как набор точек, поэтому не сильно хочется завязываться на параболу).

Буду очень благодарен за любую помощь.

[TOTAL]

oliver в сообщении #726194 писал(а):

Задача:

Задано параболу $ax^2+bx+c$ и набор $k$ точек ${p_i=(x_i, y_i)}$.
Минимизыровать сумму квадратов расстояний от точек до параболы,
то есть найти такое смещение параболы ${(x_0, y_0)}$, чтобы сумма $\sum\limits_{i=1}^k d(p_i)^2$ была минимальной

Запишитие здесь величину (зависящую от параметров), которую надо минимизировать за счет подбора этих параметров.

[ИСН]

Если расстояние до параболы считается как разница $y$, то перед нами классический линейный МНК. Там не то что кубическим, там и квадратичным уравнениям неоткуда быть.
Если расстояние реальное, то всё плохо, плохо...

[TOTAL]

(Оффтоп)

ИСН в сообщении #726210 писал(а):

Если расстояние реальное, то всё плохо, плохо...

$\text{то плохо}^{\text{плохо}^\text{...}}$

[oliver]

TOTAL в сообщении #726205 писал(а):

oliver в сообщении #726194 писал(а):

Задача:

Задано параболу $ax^2+bx+c$ и набор $k$ точек ${p_i=(x_i, y_i)}$.
Минимизыровать сумму квадратов расстояний от точек до параболы,
то есть найти такое смещение параболы ${(x_0, y_0)}$, чтобы сумма $\sum\limits_{i=1}^k d(p_i)^2$ была минимальной

Запишитие здесь величину (зависящую от параметров), которую надо минимизировать за счет подбора этих параметров.

Пусть смещение параболы равно $((x_0,y_0))$
Тогда новая парабола будет иметь вид: $y^* =ax^*^2+bx^*+(c-y_0)= a(x-x_0)^2+b(x-x_0)+(c-y_0)$
1. Пусть $d((x_i,y_i))=y^*-y_i=(a(x-x_0)^2+b(x-x_0)+(c-y_0))\ -\ y_i$
Минимизировать $\sum\limits_{i=1}^k d(p_i)^2$

2. (Усожненный вариант - расстояние на плоскости) Пусть $d((x_i,y_i))=\sqrt{(x^*-x_i)^2+(y^*-y_i)^2}
Тогда: $d((x_i,y_i))=\sqrt{(x-x_0-x_i)^2+((a(x-x_0)^2+b(x-x_0)+(c-y_0))-y_i)^2}$
Минимизировать $\sum\limits_{i=1}^k d(p_i)^2$

-- 20.05.2013, 12:54 --

ИСН в сообщении #726210 писал(а):

Если расстояние до параболы считается как разница $y$, то перед нами классический линейный МНК. Там не то что кубическим, там и квадратичным уравнениям неоткуда быть.

$\sigma=\frac12\sum\limits_{i=1}^k (y_i-(a(x_i-x_0)^2+b(x_i-x_0)+(c-y_0))^2$

При дифференциировании по $x_0$ появляются степеня.

Если у меня ошибка - укажите, пожалуйста.

[ИСН]

Зачем Вы дифф... а, нет, понял.
Не надо искать никакое смещение. Смещения нет (0). Ищите саму параболу. Тупо: a, b, c. По ним же и дифференцируйте в процессе.

[TOTAL]

ИСН в сообщении #726218 писал(а):

Тупо: a, b, c. По ним же и дифференцируйте в процессе.

Если $a$ фиксировано, то тупо по b, c.

[oliver]

TOTAL в сообщении #726219 писал(а):

ИСН в сообщении #726218 писал(а):

Тупо: a, b, c. По ним же и дифференцируйте в процессе.

Если $a$ фиксировано, то тупо по b, c.

А, понял.
a - фиксирует форму кривой, b, c - задают смещение.

[ИСН]

Можно сказать и так, да.

[oliver]

Надо было сразу написать, что форма кривой - фиксирована.

[ewert]

Там фиксирована не только форма, но и направление параболы (строго вверх). В этой ситуации совершенно непонятно, какую пользу может принести сельскому хозяйству минимизация расстояний именно по нормалям, а не по вертикали. Впрочем, фиксация формы ещё более непонятно зачем.

[oliver]

ewert в сообщении #726235 писал(а):

Там фиксирована не только форма, но и направление параболы (строго вверх). В этой ситуации совершенно непонятно, какую пользу может принести сельскому хозяйству минимизация расстояний именно по нормалям, а не по вертикали. Впрочем, фиксация формы ещё более непонятно зачем.

Представте себе, что точки на плоскости - места на зубах куда будут крепится брекеты, а парабола - это заранее подготовленная проволочка, к которой они будут прикреплены

[ИСН]

В такой формулировке имеется ещё одна степень свободы - можно всю параболу как целое наклонить набок. Или Вы это и собираетесь делать в дальнейшем?

[oliver]

Да, такой поворот возможен , но он будет осуществлятся только по указаниям пользователя с помощью манипуляторов в 3D.

Для вычисления первоначального положения арки(параболы) все контрольные точки проэктируются на плоскость (которую тот же пользователь определяет заранее) и арка размещается параллельно этой плоскости. После этого можно внести корективы.

[ИСН]

Не очень понял (размещение параболы параллельно заданной плоскости всё-таки оставляет нам свободу её наклонять в этой самой плоскости), ну да неважно. Значит, находите первоначальное положение по МНК, а потом численно подгоняйте по реальным расстояниям.