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

[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 год господа

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

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

P.S Как выделять текст для коментариев (( немогу понять

[Excalibur921]

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

Напишите плз псевдокод как вы дифференцировали?
на простом примере
по типу X1 Y1 X2 Y2 X3 Y3
для нахождения прямого участка нужно X1-X2/ (количество точек) = чтото там..
наподобие такого хотябы с 5 кординатами

[somewhere]

Брались две соседние точки, из них создавался вектор. Затем вычислялся угол между осью OX и этим вектором - таким образом получается число, аналог азимута в географии.
Эта операция повторялась для всех точек и формировала массив азимутов.
Затем массив просто дифференцировался, т.е. считалась разница между соседними элементами. Таким образом массив показывает насколько азимуты отличаются между собой.
Ну а дальше анализ - искались участки с условием:
1) Сумма разниц азимутов не превышает Z
2) Отдельно взятый элемент в участке не превышает Z
Из всех участков выбирался участок максимальной длинны.

[Excalibur921]

Брались две соседние точки, из них создавался вектор. Затем вычислялся угол между осью OX и этим вектором - таким образом получается число, аналог азимута в географии.
Эта операция повторялась для всех точек и формировала массив азимутов.
Затем массив просто дифференцировался, т.е. считалась разница между соседними элементами. Таким образом массив показывает насколько азимуты отличаются между собой.
Ну а дальше анализ - искались участки с условием:
1) Сумма разниц азимутов не превышает Z
2) Отдельно взятый элемент в участке не превышает Z
Из всех участков выбирался участок максимальной длинны.

спасибо сразу стало понятно
а слово то страшное какое дифференцирование =) думал какаято хитрая формула с мат анализа...

А не подскажете чтото по поводу поиска равномерной скорости?
уже думаю а ведь его тоже можно таже продифференцировать - нужные участки будут внизу графика ( т.е низкие значения отколнения аналог Z в вашем методе для траекторий )
А потом просто прогнать соклько точек входит в интервал от 0 до Z

Интересный подход ..а у меня сложней получился алгоритм ((

P.S не подскажете как убрать acos? думаю он также медленно считается
пример кода..
Alfa1 = (x3 - x2) / dAB;
Alfa1=acos(Alfa1); // наход стартов угол


if (y3 < y2) //устранение проблемы четвертей тригонметрич круга
{
Alfa1 = (3.1415 - Alfa1) + 3.1415;
}

[somewhere]

P.S не подскажете как убрать acos? думаю он также медленно считается

Вы там под микроконтроллеры пишите что-ли? Ничего не медленно, 240-300 тактов было на 486. Сейчас наверняка еще меньше.

а слово то страшное какое дифференцирование =) думал какаято хитрая формула с мат анализа...

Порой самое страшное выражение из матана в программировании записывается двумя строчками.

А не подскажете чтото по поводу поиска равномерной скорости?
уже думаю а ведь его тоже можно таже продифференцировать - нужные участки будут внизу графика ( т.е низкие значения отколнения аналог Z в вашем методе для траекторий )
А потом просто прогнать соклько точек входит в интервал от 0 до Z

Да, тоже самое, только нужно считать не длинну участка, в котором каждый элемент от -Z до +Z, а сумму элементов на участке, т.к. мы имеем дело уже не со скоростью, а с ускорением и на протяжении некоторого времени суммарное значение величин (интеграл) должен быть от -Z до Z. В идеале конечно нуль.
Например, имеем скорости:
19, 20, 21, 21, 22, 23, 24, 24
После дифференцирования:
1, 1, 0, 1, 1, 1, 0
При Z = 1 по вашему методу войдут все числа. Но это не правильно, скорость почти линейно возрастает, потому если интегрировать по длине, то
1 шаг: (1 + 1) = 2, входит в (2Z)
2 шаг: (1 + 1 + 0) = 2, входит в (2Z)
3 шаг: (1 + 1 + 0 + 1) = 3, не входит в (2Z)
В то время как если бы ряд выглядел бы как
19, 20, 20, 19, 21, 19, 20, 21
то алгоритм посчитал бы скорость постоянной

[Excalibur921]

Вы там под микроконтроллеры пишите что-ли? Ничего не медленно, 240-300 тактов было на 486. Сейчас наверняка еще меньше.

эм... я думал 1 такт..ну 10 это для 1 acos тратится 300 тактов 0_0?
у меня... около 200 acos...
нет не для микроконтроллеров.. но поглядывать на то сколько какая операция занимает не мешалобы..
ведь траекторий будут миллионы .. а может и пару сотен тыщ...

мы имеем дело уже не со скоростью, а с ускорением

А зачем брать ускорение?
Уменя сечас есть абстрактный график абсолютной скорости в процентах
считался так:
расстояния между двумя точками - это длинна отрезка
прощет всех точек
поиск в массиве макимальной длинны отрезка
макс длинна \100= 1%
перещет всех отрезков в процентах
итог: график абсолютной скорости процентах

а продифференцировав длинны отрезков можно построить график где линии близкие к 0 будут какраз ровные участки

Например, имеем скорости:
19, 20, 21, 21, 22, 23, 24, 24
После дифференцирования:
1, 1, 0, 1, 1, 1, 0

ну правильно близкие к линейной скорости ониже не отличаются почти на вплеске есть скорост к примеру 80
тогда к примеру будет
19, 20, 21,80, 22, 23, 24, 24
-1 ,-1, -59 ,58 ,-1 , -1,0 и взять по модулю вроде норм =)
а потом по дипазону прогнать массив и все

[somewhere]

а потом по дипазону прогнать массив и все

Я ж про это и говорил - прогонишь массив по диапазону и получится что 19, 20, 21, 21, 22, 23, 24, 24 - станет для алгоритма прямым участком, а это не так.

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

Можно сделать таблицу для arccos, т.к. выдаваемая погрешность будет не существенна для алгоритма. Только вот реализация подобных вычислений на С++ не даст абсолютно никаких преимуществ, а боюсь даже замедлит работу.
Во-вторых вычисление arccos делается X раз для одной тректории из Х точек. При миллионе траекторий и сотне точек на каждую потеря времени на arccos составит 1E6 * 1E2 * 240 / 3E9 = около 8 секунд на процессоре 3Ghz, а максимальная экономия на оптимизации не более 6 секунд. Так что на данных момент не критично.

[Excalibur921]

около 8 секунд на процессоре 3Ghz, а максимальная экономия на оптимизации не более 6 секунд. Так что на данных момент не критично.

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

в 3 часа ночи придумал:

Вот еще подумал как бы проще создать алгоритм
посмотрите может я гдето не прав в рассуждениях он немного экстравогантнен =)

итак упрщение:
отказ от двух отдельных алгоримов..
отказ от построения гарфика абсолютной скорости..
---
анализ ТРАЕКТОРИИ
чем вообще характерезуется ровный учаткой траектории??
близким к линейному росту кординат X и Y
т.е если построить график где:

вертикаль: X + Y
горизонталь : время

получается что ровный участок кривой траектории это произвольно наклоненная прямая на этом графике( рост кординат со временем линеен это суть создания прямой)
--
анализ СКОРОСТИ
чем вообще харакетерзуется равномерная скорость?
равномерными отрезками на траектории.. но если они не близкие по длинне то для X и Y приращение по времени не будет линейным

т.е получается линейность изменения координат X Y определяет и РАВНОМЕРНУЮ скорость и РОВНЫЙ участок траектории??
годится для быстрого алгоритма? ( милионы вычеслений) =)

тогда прямой участок на этом графике будет только при выполнении двух условий:
1) равномерная скорость
2) ровный участок

в итоге получается задача поиска произвольно наклоненой близкой к прямой на графике
теперь наверно диффеернцируем по вашему методу но..
хитрость: не берем ACOS ... это медленно и незачем..

пример кода для нахождения только угла 1 отрезка
------------
Alfa1 = (x3 - x2) / dAB; // <------- так нужно если работать с траекторией а если с графиком? ( т.е временный интервалы константа) тогда (x3 - x2) заменяется на константу? эконимия сотен тыщ отниманий))
<------ (x3 - x2) / dAB; деление на dAB... деление плохо.. может округлять до парных целых? тогда деление сдивигом? и вообще горизонтальный интервал на графике сделать удобным ( т.е парным 8 битным?)
вот тут странность... а зачем делить на неудобные числа? лудше число в формуле заменяющее (x3 - x2) делить просто на два сдвигом 1 раз? или вообще неделить? тут мой мозг отказал)))
------------

------------
Alfa1=acos(Alfa1); // наход стартов угол <------- медленная операция не делать! позже напишу почему..
------------


------------
if (y3 < y2) //устранение проблемы четвертей тригонметрич круга <--------- нет COS нет поблем =) тригонметрич круга ненужный код =)
{
Alfa1 = (3.1415 - Alfa1) + 3.1415;
}
-----------
в итоге на дифференцирование по вашему методу выходит график не углов а соотнешний сторон... помоему удобно

получается график где наклоненые прямые на первом графике стали горизонталынми прямыми после дифференцирования

затем анализ:
ищем участки минимально из ( количество точек траектории/3 мой критерий 120 градусов или на 90 градусов т.е количество точек траектории/4 )
и ониже должны быть близкие к горизонтали

[Excalibur921]

- вычесления с косинусом в посте-

толькочто подумал нет я немного напутал с COS...
но возможно улудшить если определять не угол всеже ..а ТАНГЕНС соотношение сторон а не брать АРКТАНГЕНС это проще намного
--------
для нахождения угла через коснус нужно:
1)найти длинну хоть траекториии хоть на графике.. по большой неудобной формуле:
dBO=sqrt(pow(x3-x2,2)+ pow(y3-y2,2)); //находим разово длинну отрезка BO
+ черт его знает что там накодили эти функции sqrt и pow черный ящик...

2)потом находит соотнешение сторон через деление неудобных процессору чисел((
Alfa1 = (x3 - x2) /dBO;
без угла оставить соотношение

---------------
а для тангенса
1) OA это вообще константа на графике ( временной интервал можно взять к примеру абстрактно равен 2 удобно делить сдвигом помоему на асемблере)
2) длинна AB = By-Ay
3) тангенс = AB/OA = т.е сдвигаем биты AB на помоему на 1 знак непомню уже и все 0_0

вот с тангенсом я не работал... но вроде много проще!

Котангенс брать нельзя получается деление 2 на неудобное число
а с тангенсом вроде красота ..

[somewhere]

Arccos(dx/R) дает линейное приращение значений при линейном изменении угла. Y = C/X - наоборот, изменение углов в середине четверти и на ее краях дадут абсолютно разные изменения отношений катетов. А значит эта функция не пригодна для анализа.
Дальнейшие рассуждения не имеют смысла.