Алгоритм распознания прямого участка замкнутой кривой

[Excalibur921]

подскажите плз алгоритм
вот такая задача:

источник данных
есть механизм 4-x звенник на плоскости



точка описывает всегда замкнутую кривую
меняяя кординаты точек меняются кривые описываемые точкой
( можно менять количество шагов которые рисуют графики и саму траэкторию т.е может быть более угловатая см (РИСУНОК ScreenShot00084.gif ScreenShot00085.gif



) если это нужно, можно уменьшить шаг если гдето надо или увеличить если поможет анализу)

задача:
написать алгоритм или найти метод какойто чтобы найти на этой траэктории близкий к прямой участок (РИСУНОК где ровная и кривая траэтория участки AB на фотоках ScreenShot00086.gif ScreenShot00087.gif ScreenShot00088.gif







) и указать как далек он от идеальной прямой ( ввести наверно переменную от 0 - до 100? или другой вариант? от 0 до 10?)


и как близка ( ввести пеерменную от 0 до 100? т.е к примеру 5 очень далека, 47 почти прямая , 97 почти идеальная прямая )к постоянной скорости скорость точки E на этом близким к ровному участке

Итого задачи : -найти участок с близкой к равномерной скоростью
и как далека эта скорость от равномерной

-найти участок траэктории близкий к прямой
и как далек этот участок от прямой

нужно найти такой участок траэктории где скорость приблежается к постоянной и траектория приблежается к прямой

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

даже незнаю как подступится траэкторий возможно сотни тысяч или больше
нужен простой и быстрый алгоритм

[Neos]

Один из подходов, аналог метода "наименьших квадратов".
Выбираете две точки, ограничивающие участок кривой. Между ними выбираете
$n$ точек, и по ним строите усредненный участок прямой.
Суммируете квадраты разностей $n$ точек Вашей кривой
до усредненной прямой. Величина этой суммы и будет мерой отклонения
кривой от прямой. Для прямой этот параметр равен $0$

[Excalibur921]

Neos в сообщении #774276 писал(а):

Один из подходов, аналог метода "наименьших квадратов".
Выбираете две точки, ограничивающие участок кривой. Между ними выбираете
$n$ точек, и по ним строите усредненный участок прямой.
Суммируете квадраты разностей $n$ точек Вашей кривой
до усредненной прямой. Величина этой суммы и будет мерой отклонения
кривой от прямой. Для прямой этот параметр равен $0$

я в математике 0...
обясните плз на яблоках
траэктория 30 точек узловых

{Выбираете две точки}
на каком критерии выбор?

{Между ними выбираете $n$ точек,}
n это сколько 5 ? 10 ? 21?

{по ним строите усредненный участок прямой.}
это как? и зачем?
я гений

[Neos]

Вспомните, как строится прямая на графике, если известен ряд
экспериментальных точек, не лежащих на одной прямой. Обычно
предполагается какой-то "разумный" разброс.

[Excalibur921]

Neos в сообщении #774390 писал(а):

Вспомните, как строится прямая на графике, если известен ряд
экспериментальных точек, не лежащих на одной прямой. Обычно
предполагается какой-то "разумный" разброс.

где яблоки

[Dan B-Yallay]

На яблоках хотите? Очень грубо и на самом деле неправильно(но для пояснения идеи) я бы делал так:
У вас есть 30 узловых точек. Берем участок кривой с 3-мя точками: $(x_1,y_1), (x_2,y_2), (x_3,y_3)$ проводим прямую через крайние две. Затем считаем квадрат расстояния от средней точки до этой прямой и делим на длину участка (или на расстояние между крайними точками) - получаем некую меру средней искривленности выбранного участка. Сдвигаемся на одну точку и берем $(x_2,y_2), (x_3,y_3),(x_4,y_4)$. Повторяем, сравниваем искривленности, выбираем меньшее и запоминаем. Повторяем, пока не пройдем по кругу ваши 30 узловых точек до конца: $(x_{30},y_{30}),(x_1,y_1),(x_2,y_2)$. Таким образом находим триплет с наименьшим отклонением от прямой. Это были тройки точек.

Далее, берем четверки и повторяем предыдущые процедуры, но теперь срединных точек две. Поэтому берем сумму квадратов их расстояний до прямой и делим на 2(среднее) и еще на длину участка. Идем также по кругу. Находим 4-ку с наименьшим "средним" отклонением.
Далее пятерки, шестерки и т.д.

Выбираем наименьшее.

-- Вс ноя 03, 2013 22:44:22 --

Excalibur921 в сообщении #774374 писал(а):

я в математике 0...

То, что у меня написано - это повторение уже сказанного вам другими участниками. Причем, повторюсь, алгоритм не самый оптимальный и потому может дать неверный (хоть и близкий к верному) результат. Зато он дает вам идею о методе "наименьших квадратов" который неплохо подходит к этой задаче. Но чтобы смочь применить его, Вам надо сдвинуться c этого "математического нуля"

[Excalibur921]

Тема решена на другом форуме: НЕ РЕКЛАМА .. долгий труд..
Необходимо было продифференцировать а затем проинтегрировать ...
Вдруг кому пригодится: Алгоритм-распознания-прямого-участка-замкнутой-кривой

[bin]

Преобразование Хафа может оказаться эффективнее, см.: http://en.wikipedia.org/wiki/Hough_transform