2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 13:22 
Аватара пользователя
Задача:

Задано параболу $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$ (как в регрессионной модели), но хотелось бы использовать реальное расстояние.

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

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

 
 
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 13:32 
Аватара пользователя
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$ была минимальной

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

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

 
 
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 13:48 
Аватара пользователя

(Оффтоп)

ИСН в сообщении #726210 писал(а):
Если расстояние реальное, то всё плохо, плохо...
$\text{то плохо}^{\text{плохо}^\text{...}}$

 
 
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 13:48 
Аватара пользователя
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$ появляются степеня.

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

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

 
 
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 14:04 
Аватара пользователя
ИСН в сообщении #726218 писал(а):
Тупо: a, b, c. По ним же и дифференцируйте в процессе.
Если $a$ фиксировано, то тупо по b, c.

 
 
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 14:17 
Аватара пользователя
TOTAL в сообщении #726219 писал(а):
ИСН в сообщении #726218 писал(а):
Тупо: a, b, c. По ним же и дифференцируйте в процессе.
Если $a$ фиксировано, то тупо по b, c.


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

 
 
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 14:20 
Аватара пользователя
Можно сказать и так, да.

 
 
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 14:50 
Аватара пользователя
Надо было сразу написать, что форма кривой - фиксирована.

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

 
 
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 18:57 
Аватара пользователя
ewert в сообщении #726235 писал(а):
Там фиксирована не только форма, но и направление параболы (строго вверх). В этой ситуации совершенно непонятно, какую пользу может принести сельскому хозяйству минимизация расстояний именно по нормалям, а не по вертикали. Впрочем, фиксация формы ещё более непонятно зачем.


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

 
 
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 22:09 
Аватара пользователя
В такой формулировке имеется ещё одна степень свободы - можно всю параболу как целое наклонить набок. Или Вы это и собираетесь делать в дальнейшем?

 
 
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение21.05.2013, 14:29 
Аватара пользователя
Да, такой поворот возможен , но он будет осуществлятся только по указаниям пользователя с помощью манипуляторов в 3D.

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

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

 
 
 [ Сообщений: 15 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group