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

[Excalibur921]

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

источник данных
есть механизм 4-x звенник на плоскости
(см рисунок ScreenShot00082.gif)


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

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


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

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

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

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

[somewhere]

Я думаю, начинать надо с того, что нужно найти множество точек от A до В. Или нужно распознавать изображение?
Конкретизируйте, что мы имеем "на входе". То что нужно на выходе мне понятно и, в принципе, могу состряпать черновую версию алгоритма

[Excalibur921]

Я думаю, начинать надо с того, что нужно найти множество точек от A до В. Или нужно распознавать изображение?
Конкретизируйте, что мы имеем "на входе". То что нужно на выходе мне понятно и, в принципе, могу состряпать черновую версию алгоритма

" думаю, начинать надо с того, что нужно найти множество точек от A до В."

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

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



"Конкретизируйте, что мы имеем "на входе". "
на входе 30 точек X Y в декартовых кординатах - это результат расчета программы можно больше точек можно меньше уже говорил в посте.. ( как лудше для анализа так и можно зделать)

к сожелению в математике я нуль....
и скорей всего Метод Наименьших Квадратов который вы ( наверно) придложите я немогу понять... а хотел читал книги.. немогу и все уровень матеатики 3 клас школы.. хотя любой процессор выполняет также элементарные действия и о мат анализе не знает))

и еще тонкость траэктория находится в любом месте на плоскости...( т.е программа меняет кординаты точек механизма который рисует траэкторию то она начинается в 10 ; 12 то в 70;140 x y)

смотрите картинки яже старлсяделал для понимания.. просмотров 0 (((((

[somewhere]

смотрите картинки яже старлсяделал для понимания.. просмотров 0 (((((

Картинки смотрел, не знаю что там со счетчиком. Принцип я изначально понял, вопрос был об исходных данных.
Тогда жду от вас список координат точек для тестирования алгоритма. Желательно не один.
Формат - любой. Проще наверное будет в текстовом

[Excalibur921]

Картинки смотрел, не знаю что там со счетчиком. Принцип я изначально понял, вопрос был об исходных данных.
Тогда жду от вас список координат точек для тестирования алгоритма. Желательно не один.
Формат - любой. Проще наверное будет в текстовом

у меня нет прав на Send Private Message
поэтму введу кординаты точек тут с минусом нестрашно? могу переделать на только положительные

пример

кординаты идут X Y
1 траектория
-200 715
-183 715
-165 716
-148 719
-131 723
-115 730
-101 739
-89 750
-80 761
-75 773
-74 784
-78 793
-89 796
-110 791
-155 778
-227 776
-281 794
-306 803
-319 801
-324 793
-326 782
-323 771
-317 758
-308 747
-296 737
-283 729
-267 723
-251 720
-235 717
-218 716
-200 715

2 траектория длительность прямой больше
-230 719
-213 716
-195 713
-177 712
-158 712
-140 715
-124 720
-109 727
-96 736
-88 746
-83 756
-84 764
-93 767
-117 762
-169 751
-252 760
-310 789
-336 805
-348 806
-353 801
-354 791
-351 780
-345 768
-336 757
-324 748
-311 739
-296 733
-280 728
-263 725
-247 722
-230 719

3 траектория длительность прямой еще больше
-246 733
-230 729
-213 724
-196 719
-179 717
-161 716
-144 718
-129 722
-116 728
-106 735
-100 743
-99 749
-108 752
-132 748
-188 742
-273 760
-329 798
-352 818
-363 821
-367 817
-367 808
-364 797
-357 785
-348 775
-336 765
-323 756
-308 750
-293 745
-277 741
-261 737
-246 733
------------------
вроде нигде не ошибся)

[somewhere]

Вот некоторые наброски.
Меняя чувствительность к прямолинейности трекбаром получаем разной длины прямолинейные участки. Они выделяются на графике. Выбирается участок максимальной длины.
К постоянству скорости я еще не привязывался, т.к. необходимо установить приоритеты влияния двух функций (прямолинейности и скорости)
[ATTACH]1764[/ATTACH]

[Excalibur921]

Вот некоторые наброски.
Меняя чувствительность к прямолинейности трекбаром получаем разной длины прямолинейные участки. Они выделяются на графике. Выбирается участок максимальной длины.
К постоянству скорости я еще не привязывался, т.к. необходимо установить приоритеты влияния двух функций (прямолинейности и скорости)
[ATTACH]1764[/ATTACH]

"необходимо установить приоритеты влияния двух функций (прямолинейности и скорости)"

анализ должен выводить к примеру 2 параметра чем лудше прямолинейность и скорость тем выше балы ( типа оценки наверно 100 значений незнаю програ разрабатывается только..)
программа будет работать в двух режимах

первый локальная оптимизация :
много близких траекторий выбрать из них наиболее высокий бал

второй анализ статистики:
несколько тыс траэкторий будут собиратся ( я надеюсь))) в фаил и потом построю 3д график где лудше траектории...

а вообще...

я в шоке ...круто...
вы написали целую прогграмму эм... а как она работает)))
я думал вы типа алгоритм опишите приблизительно...или посоветуете..
а вы создали готовую программу 0_0
а какой язык ? я пиш на с++ Visual Studio 2005 Pro + OpenGL + GLUT

P.S вам интересна механика кинематика робототехника?

[somewhere]

анализ должен выводить к примеру 2 параметра чем лудше прямолинейность и скорость тем выше балы ( типа оценки наверно 100 значений незнаю програ разрабатывается только..)

Так об этом я и говорю.
Необходимо для начала составить критерии оценки параметров, и, как мне видется, это будет коэффициент:
E = aV + bD, где a и b - корректирующие коэффициенты, V - значения скорости в момент времени, D - коэффициент прямолинейности (чем ниже тем прямее)
Принцип измерения прямолинейности - дифференцирование угла вектора скорости. Если вектор скорости не меняется, то прямолинейность равна 0 - наивысшее значение, абсолютно прямо. В противном случае отлична от нуля тем больше, чем больше изменение.
Со скоростью, думаю, и так все понятно - это длина вектора. Имеем право так считать, т.к. измерение происходит в равные промежутки времени.

а какой язык ? я пиш на с++ Visual Studio 2005 Pro + OpenGL + GLUT

Язык не имеет значения, всегда можно скоординироваться через DLL. Лично мне нравится Delphi+Asm. Ассемблер - это как раз тот случай, когда можно расчитать 10 тысяч траекторий за доли секунды, в то время сишники "едут" в от 5 и более раз медленнее. Особенно если начинаешь применять SIMD инструкции.

второй анализ статистики:
несколько тыс траэкторий будут собиратся ( я надеюсь))) в фаил и потом построю 3д график где лудше траектории...

Это все можно и нужно объединить в одной программе - но мне будут нужны формулы расчета траекторий.

P.S вам интересна механика кинематика робототехника?

Да, когда то занимался механикой двигателя - все четыре такта работы с нагрузками, крутящими моментами, моментами инерции и пр. Но работа превыше всего, сейчас времени на энтузиазм все меньше и меньше.

[Excalibur921]

"Принцип измерения прямолинейности - дифференцирование угла вектора скорости."

яж гвоорю матиматика 0 )))
а я придумал не трогать косинусы и углы вообще а сначала строить график абсолютной процентной скорости точки
т.е расчет длинн отрезков между каждой точкой
ищем максимальтную длинну
ищем минимальную
макимальная длинна отрезка /100= 1 %
перещет всех длинн отрезков в процентах
строим 2д график
высота 100 пикселей
ширина к примеру 480 пикселей
интревал пикселей между точками по Х 480/количество точек= длинна 1 интервла по горизонтали

в итоге удобно...
задача поиск резкого всплеска скорости т.е поиск максимального угла который означает всплеск
вместо работы с углами.... если кордината по Y на графике ( т.е процентная скорость) больше или меньше чем длинна 1 интервала..то у гол больше 45 градусов- значит всплекс

анализ всех точек на количество всплесков
больше 2 ? выход с анализа ( мне нужен максиально 1 всплеск скорости - верх траектории)
меньше? находим разность высот на графике между двумя точками всплеска
делим на количество точек между ними находим приращение - коринату по Y на графике для идеальной прямой и сверяем ее каждой точкой на графике +- некая дельта

в будущем можетбыть как идея... закодируюв в ПЛИС..

"Это все можно и нужно объединить в одной программе - но мне будут нужны формулы расчета траекторий."

эм.. стыдно сказать но это банальный 4-х звенник из механики его фотка первая в посте))
как я не старался... скачал 5 книг по теормеху.. ставил формулы академиков.. ничего не считало
у всех авторов разные формулы(!!)
(( видимо они их упрощали очивидными только для математиков способами
пришлось... взять элементарные формулы по тригонометрии... теорему косинусов..
зато они просты надежны и проверены временем))

[Excalibur921]

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

ого.....
тогда мои задачи просто даже не децкий лепет по сложности ))

в общем цель для которой я хотел написать программу это поиск плоского механизма шагания
только с вращательными парами и дальнейший анализ 6 звенных механизмов на поиск наиболее лудшего решения.. конечно это задача для инженеров и професоров механики или омжетбыть для НИИ Благонравова)))... это темы нескольких грантов наверно...( кстати несколько неправильных решений есть в патентной базе США и также распиареных СМИ и интернет например не очень толковые механизмы ТеоЯнсен http://ru.wikipedia.org/wiki/Тео_Янсен и Механизм Кланна
http://ru.wikipedia.org/wiki/Механизм_Кланна
Механизм Кланна патент очень мутный...и кстати там только анализ траекторий был без учета скорости точки на траектории 0_0 вообще непонимаю зачем это ерунду было патентовать
это первые стадии синтеза механизма...
видимо человек не очень разобрался в вопросе..а его повторяют просто потомучто лудше ничего нет...
я не ставлю цель получение патента наверно))
просто думал из любопытства и тяги к механическим устройствам попробывать поискать механизм как они... или превзойти их)) но тогдабы написали бы в журналах об этом наехало ТВ CNN ))) нет этого не хотелось бы...
большинсвто из около 100 книг которые я пролистал из многих областей связаных с этим вопросом одна вода кроме 7 томов Артоболевского и еще пары книг... написал автору одной книги и единственно осташемуся профи по шагающим механизмам .. а он молчит)) это его хлеб хоть и работы его макулатура..а крутые спецы либо поумирали уже ( эхо СССР ВНИИ ТРАНСМАШ лунная программа )либо работают только на оборонку и не занимаются этим... да и не ответят они ничего.. этож секретно наверно))

да и НИИ Машиностроения не порадовал меня своим недавним патеном... какаято ерунда..я думаю там не глупые люди просто не показывают эти механизмы...
да и менять чтото лень главным инженерам напримерв шагающих экскаваторах) допотопные схемы и вообще непонятно какой... их туда ставил =\

думал придумать свой механизм и собрать его как игрушку))

да и старый проект 60 годов по шагающему автомобилю был когдато секретным судя по описанию и фотками механика там.. на уровне игрушек( переваливающиеся с опоры на опору поднятие центра тяжести .. неграмотные скорости и .тд там целый букет)

хотел написать программу для анализа и поиска траэкторий 4-х звенника для
нахождения возможно лудшего базового решения наподобия механизма Чебышева-Умнова
а потом проанализировать и 6 звенник поискать интересные схемы..

а еще в этой теме практических только 1 интерактивный софт а очень инетерсные вещи нахоядтся под секретом а диссертации лежат в РосГОс библиотеке...даже почитать нельзя!!(((
и вообще нет интерактивного анализа 3д кинематики хотябы геометрического( т.е показ траектори и все)

думал из любопытства написать интерактивный анализ 4 звенника с парами качения и вращения.. его нет в мире.. но почему??)) да и анализ скорости не мешало бы туда.. угла давления.. да элементарных вещей...

даже просто поигратся какие он там 3д траэктории описывает интресно! элементарная же вещ..4 звенник..основа всех механизмов.. первый предмет изучения всех вузов наверно всех стран))
а 3D четырехзвенник забыт.. типа сложный... но ведь 2013 год господа

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

вобщем это любопытсво в механике наверно и желание чтото попробывать вот так и продвинутей чем методом тыка по научному ( Монте-Карло)))