Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
Форум программистов > Алгоритмы > Алгоритм распознания прямого участка замкнутой кри |
Автор: Excalibur921 12.10.2013, 11:31 |
подскажите плз алгоритм или в каком направлении искать вот такая задача: источник данных есть механизм 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 на этом близким к ровному участке Итого задачи : -найти участок с близкой к равномерной скоростью и как далека эта скорость от равномерной -найти участок траэктории близкий к прямой и как далек этот участок от прямой даже незнаю как подступится траэкторий возможно сотни тысяч или больше нужен простой и быстрый алгоритм подкажите в каком направлении искать |
Автор: Pavia 12.10.2013, 12:02 |
Пусть кривая задана точками. точки добавляем в массив. Проводим от первой до последней точки прямую смотрим отклонение промежуточных точек от прямой если хотя бы одна точка превышает порог то прямой участок будет состоять из N-1 точку массива. Понятно что порог соответствует масштабу. Оценку качества можно сделать по СКВ. |
Автор: Excalibur921 12.10.2013, 17:15 | ||||||||||
но здесь первая и онаже последняя..
сам алгоритм должен указывать как далеко искомое отличается
както нужно не зависить от масштаба
эм... что такое СКВ? узкоспециализированное сокращение какогото метода? напишите плз полностью... |
Автор: _Y_ 12.10.2013, 17:43 |
Я бы попытался использовать обычный метод наименьших квадратов. Скажем, примерно так:
|
Автор: Pavia 12.10.2013, 18:03 |
Имелось в виду на текущем шаге алгоритма. Не получится. Это физика, а она зависит от масштаба. СКВ- опечатался имел в веду средне квадратичное значение |
Автор: Excalibur921 12.10.2013, 18:11 | ||
насколько я понял ![]() очень тежелый метод.. много вычеслений а проще? траэкторий возможно сотни тысяч или больше! может есть какаято простая формула построить какойто график на основании координат точек какойто график чтобы был ровный если скорость постоянная и начинал исвревлятся если она не постоянна? а по поиску прямого участка траектории вродебы есть такая штука она так и называется Кривизна ![]() http://ru.wikipedia.org/wiki/Кривизна но сильно заумно написано не практично(( |
Автор: Excalibur921 12.10.2013, 20:34 |
не боюсь .. я ее незнаю вообще))) офтоп : а очень хотелось бы.. но потребуются годы на изучение а литература написана математиками для математиков... качал книги по мат анализу... диф геометрию)) искал в гугле один сленг математиков понять чтото... мрак.... боюсь моя математика заканичвается 3 классом школы)) но в программе требывалась применять тригометрические сложные формулы.. я скачал 5 книг по механике... читал в инете... кучи книг... нашол расчеты формулы..поставил формулы по Артоболевскому .. по Левитскому .. современные авторы... и у всех разные формулы!! это ужас... 5 разных методик ничего не работало... видимо они их упращали очевидными только для математиков методами... и они не работали((( отказался от них.. сел подумал 2 дня))) взял элементарные тригометрические формулы с выкипедии.... немгого своих идей и.. программа стала считать точно и быстро ![]() думал может тут кто подскажет чтото простое... задал эту тему на 5 форумах... предлагают какойто Метод Наименьших Квадратов (МНК) гуглил..читал... скачал книгу.. ну ненмогу нислова понять((( опять литература написана математиками для математиков ![]() почему их не пишут простым понятным языком типа Метод Наименьших Квадратов обяснение на яблоках))) или на пальцах и обязательно с примером расчета... нет одни кони в ваккуме... кстати если вы дочитали этот крик души до этого места... ![]() то есть вообще какойто метод полиномов Чебышева.. он бы позволл вообще расчтать что я хочу сразу без милиона левых вычеселний, оптимизаций, и т.д.... но понять его.... сверх меня!! даже прям в книге (!!!) написано было что изза мат аппарата простые люди немогут использовать выдающиеся крутые матиматические хитрости...настолько крутые что именами создателей этих штук называли институты... нужно взять дурака и гения и пусть они напишут учебник по мат анализу)))) мат анализ на яблоках... там былобы 10 000 страниц... но открыв любую главу прочитав можно былобы применить на практике надеюсь модератор не сотрет это быстро)) аминь ![]() |
Автор: Pavia 12.10.2013, 21:47 | ||
Excalibur921, Чтобы говорить на языке надо знать его грамматику и лексику. Чтобы понимать надо знать не мало слов порядка 3000 для сносного общения. А для хорошего 6000, а на отлично 9000 слов. Также и с математикой чем больше знаешь тем лучше понимаешь. И не только с математикой, но и с физикой. Самый простой способ это нанять специалиста в физике и математике. Кстати вся теоретическая физика основана на математике. А теперь к задаче. Постановка задачи у вас странная. Для чего вам знать прямые участки? Скорее всего ваша задача решается гораздо проще. Более того определения метрики для анализа качества кривой должны были вы сами определить из сходя из требований. Мы вам можем посоветовать но не более того.
Это видимо вы не те учебнике скачали. Метод наименьших квадратов очень прост. Но проблема в том что видимо ваши знания и правда остались на уровне 3 класса. А рассказывать всё на таком уровне будет очень долго поэтому так никто не делает. |
Автор: Excalibur921 12.10.2013, 23:35 | ||
думал им стать за 1 вечер))) именно)) уже вчера накатал алгоритм решения) прост как двери натурально искуственный интелект в какойто мере)) и без нейросетей кохо.. какогото там) и без преобразование Хафа и без дифференциальной геометрии и т.п ненужных тут вещей) вот жду вдруг появятся интересные решения или нет на 5 то форумах ![]() чтобы в них искать равномерную скорость ![]() алгоритм должен будет менять кординаты точек механизма и самооптимизироватся для моих сверхсекретных нужд))) чтото типа генетического алгоритма с пред анализом во как.. незнаю изобрели ли его уже)) + анализ много разных вариантов ( сбор статистики) и анализ по этим данным лудшего варианта для начала оптимизации.. хотя этим занимаются целые НИИ ![]() те... 3 тома мат анализа... и другая макулатура)) заучив однотипные подходы к проблемам люди перестали думать творчески =) |
Автор: _Y_ 13.10.2013, 03:25 |
Excalibur921, сочувствую, без математики трудно. Но, действительно, не стОит пытаться все освоить "за одну ночь". Да и способности у разных людей к разным предметам ну о-чень разные. Я, вот, блещу абсолютной тупизной в отношении иностранных языков. При том, что без них мне ну просто никуда. Ладно, ближе к делу. Без математики все равно не обойтись как ни крути. Но предложу способ, принцип которого будет, видимо, понятен и со знаниями третьеклассника ![]() Берем график и вращаем его вокруг любой точки, можно даже и не лежащей на самом графике. Выбираем участки, на которых точки отклоняются от среднего значения не более, чем на определенную величину. Наглядно это будет выглядеть примерно так ![]() Красные линии на обоих графиках задают один и тот же интервал значений. Видно, что на втором рисунке число точек попавших в интервал и, соответвтвенно, признанных "линейным участком" больше, хотя сам график просто повернут не некоторый угол. Думаю, такое верчение нагрузит компьютер больше, чем подходы высказанные в предидущих постах. Зато серьезно съэкономите на изучении математики ![]() |
Автор: Excalibur921 13.10.2013, 09:48 | ||
вот первая оригинальная идея))) спс) еще бы убрать синусы и косинусы через которые придется крутить.. сопросцессор незнаю как использовать все книги написаны под Intel у меня AMD ![]() говорили чтото типа какието ряды тейлора вобщем синусы и косинусы замедляют работу сильно.. раьше думал вообще забахать все чисто в железе на ПЛИС и логике... он бы у меня за 1 такт все считал конвеером... но это уж сильно круто хотя несколько млн вычеслений в сек другоге дело) другая планета.. заюзать бы GPU... но GeForce 4 ![]() CUDA или TESLA нам только снится... _Y_, а почему бы не перенести работу с траэкторией на работу с графиком? может есть какойто "график кривизна прямой на плоскости" к вопросу траектории и может есть какойто "график приближенности к горизонтали" к вопросу скорости на траектории ведь это два условия должны выполнятся вместе это можно както использовать? P.S кста спасибо за рисунок никто не зает что лудше 1 раз увидеть... офтоп : ато крутые програмисты шарят как написать алгоритм и код для фотошопа но неумеют им пользоватся ?)) |
Автор: Pavia 13.10.2013, 10:07 | ||||||||
GP GPU появилась ещё во времена GeForce 4.
А смысл, ты хочешь ещё более усложнить расчёты? А во вторых есть правила разделять модель и визуализацию. Делается это как раз для удобство кодирования.
Конечно не умеют. Это разные области. Мы знаем элементарные методы. Понимаем как они работают, но не знаем как их комбинировать. А вот удачные комбинации обычно и написаны в статьях по рисованию в Photoshop. Добавлено @ 10:11
Да есть такое. Cos и sin работают медленее умножения и сложения в 10 раз. Поэтому используют следующий подход один раз вычисляют, а далее используют сложения углов. Но это оптимизация. А преждевременная оптимизация вредит разработке. |
Автор: _Y_ 13.10.2013, 12:35 |
Не думаю, что такая уж оригинальная. Наглядная визуализация, да и все. Если с фанатом-математиком общаться будете, то он скажет, что в этом методе тоже среднего мало - нужен метод наименьших квадратов. Но, как известно, от многой мудрости много печали ![]() Я не знаю на каком языке вы будете это реализовывать. В некоторых есть готовые библиотеки преобразования координат. Они, зачастую, уже оптимизированы и работают быстрее синусов-косинусов обсчитываемых "в лоб". Но, по любому, если интересует скорость вычислений, такое "вращение" вряд-ли будет оптимальным. Кстати, для метода наименьших квадратов многие языки тоже имеют оптимизированные библиотеки. |
Автор: Excalibur921 13.10.2013, 12:35 | ||||
офтоп:
думаю вы толькочто ускорили мою программу в 10 раз ![]() у меня 90 раз cos 90 раз sin... и это только начало.. Добавлено через 11 минут и 7 секунд на данный момент мучаю Visual Studio C++ 2005 + OpenGL +GLUT и если будет результат у меня..какой мне понравится наверно еще круче на Ассемблер перейду без опенгл.. наверно его там нет.. а позже может и на кодирование в железе http://ru.wikipedia.org/wiki/ПЛИС т.е ниже Ассемблера... это почти самый низкий уровень пограммирования если это еще оно... ниже только создание своих микросхем..своей логики)) это дорого очень...
вы уже не первый человек кто намекает на них)) не здесь не сегодня... хочу но немогу(( |
Автор: maxim1000 15.10.2013, 14:37 |
Модератор: Почистил... Вроде, ничего по теме, не зацепил. Сообщения были перенесены сюда: http://forum.vingrad.ru/forum/topic-372778.html |
Автор: Excalibur921 14.12.2013, 13:06 |
Проблема решилась на другом форуме http://forum.developing.ru/showthread.php/26004-Алгоритм-распознания-прямого-участка-замкнутой-кривой может пригодится комуто |