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

>>сравнить две ломанные

>>Каждый элемент ломанной - прямая

>>с заданным допуском и коэффициентами сжатия по осям

ПТУ-шник детектед.

Если у тебя есть "некоторая кривая" каторую описывает ломаная-1, то ваще нет проблем имея допуски коэффициенты сжатия. Начальный курс арифметики, первый класс.

Думаю лишнее звено.

По теме - для начала их надо по какому-либо критерию свести "под общий знаменатель" - например "подтянуть одну до длины другой и выровнять в одном направлении"

Затем считать корреляцию.

Все потому что еcли есть рандом по масштабу то всегда можно одну уменьшить до звена другой и ошибочно получить утвердительный ответ.

Если известна сама "кривая", то с помощью МНК, где коэффициенты при членах со степенью равны 0.

> где коэффициенты при членах со степенью равны 0

Почему так ничтожно влияние членов со степенью?

Дык это же не многочлен, которым принято апроксимировать.

Математическое решение.

Slader, ты вопрос сам задал и сам на него ответил. Есть некая сущность (ломанная), есть определения возможных отклонений (допуски), есть другая сущность (другая ломанная). В чём проблема?

>>Начальный курс арифметики, первый класс.

«Моя математика», 1 класс, Демидова Т.Е., Козлова С.А., Тонких А.П. и др.
Оглавление учебника «Моя математика», 1 класс, Демидова Т.Е., Козлова С.А., Тонких А.П. и др., изд. «БАЛАСС»
[Карточка ресурса]

Пустые разделы Показать Скрыть
кол-во
ресурсов
Раздел I. Признаки предметов
5
Урок 1. Цвет
1
Урок 2. Форма
1
Урок 3. Размер
1
Уроки 4-6. Признаки предметов
2
Раздел II. Отношения
5
Урок 7. Порядок
1
Урок 8. Отношения равно, не равно
1
Урок 9. Отношения больше, меньше
1
Урок 10. Прямая и кривая линии. Луч
2
Раздел III. Числа от 1 до 10
54
Урок 11. Число один. Цифра 1. Один и много
1
Урок 12. Замкнутые и незамкнутые кривые
1
Урок 14. Знаки "> ", "<", "="
1
Урок 15. Равенства и неравенства
2
Урок 16. Отрезок
1
Урок 17. Число три. Цифра 3
1
Урок 18. Ломаная, Замкнутая ломаная. Треугольник
1
Урок 20. Вычитание
1
Урок 21. Выражение. Значение выражения. Равенство
2
Урок 22. Целое и части
1
Урок 24. Число четыре. Цифра 4
2
Урок 26. Числовой отрезок
1
Урок 27. Угол. Прямой угол
1
Урок 28. Прямоугольник
1
Урок 34. Число шесть. Цифра 6
1
Уроки 35-37. Числа 1-6
2
Урок 38. Число семь. Цифра 7
1
Урок 39. Числа 1-7
1
Урок 40. Слагаемое, сумма
1
Урок 42. Слагаемое, сумма
1
Урок 43. Уменьшаемое, вычитаемое, разность
1
Урок 44. Числа 1-7
1
Урок 45. Число восемь. Цифра 8
1
Урок 47. Число девять. Цифра 9
1
Урок 49. Число ноль Цифра 0
1
Урок 51. Число 10
2
Урок 54. Числа и цифры. Римские цифры
1
Уроки 55-56. Числа 0-10
1
Урок 57. Задача
1
Уроки 58-59. Задачи на нахождение целого или части
1
Урок 60. Обратные задачи
1
Урок 61. Задача на разностное сравнение
1
Урок 62. Решение задач
1
Урок 64. Решение задач
1
Уроки 66-68. Решение задач
3
Уроки 69-70. Уравнения
2
Урок 71. Уравнение. Проверка решения уравнения
2
Урок 72. Уравнение
1
Урок 73. Длина. Сантиметр
1
Урок 74. Величина. Длина
1
Урок 78. Величины. Масса. Килограмм
2
Урок 80. Величины. Объём. Литр
2
Урок 83. Решение задач
1
Раздел IV. Числа от 1 до 20
15
Уроки 84-87. Числа от 10 до 20
5
Уроки 88-91. Табличное сложение
3
Уроки 92-93. Табличное вычитание
3
Уроки 94-96. Табличное сложение и вычитание
2
Уроки 97-100. Сложение и вычитание в пределах 20
2
Повторение
12

Я по другому учебнику учился. Мы сложение/вычитание в пределах 100 проходили.

> [Русский язык] Я не знаю, как правильно пишется слово «ломаная»

fixed

> Необходимо определить, описывает ли ту же кривую и ломанная-2, с заданным допуском и коэффициентами сжатия по осям.

Поточнее? пожалуйста. Со сжатием понятно. А что за "допуски"?

Не уверен, что будет корректно работать во всех случаях, но все же...

На первой ломаной выберем натуральный параметр t. Это значит, что нужно найти функции x(t), y(t), z(t), такие что:
1. Точка (x(0), y(0), z(0)) есть начало ломаной.
2. Для некоторого числа T точка (x(T), y(T), z(T)) есть конец ломаной.
3. Множество точек (x(t), y(t), z(t)), получающееся при значениях t от 0 до T совпадает со множеством точек ломаной.
4. Длина отрезка ломаной от точки (x(t1), y(t1), z(t1)) до точки (x(t2), y(t2), z(t2)) равна |t2-t1| для любых значений t1 и t2 от 0 до T.

Аналогично выберем натуральный параметр s для второй ломаной. Соответствующие функции - u(s), v(s), w(s).

Теперь сам алгоритм:
1. Выберем маленькое число eps (вероятно, равное четверти заданной погрешности? -- не могу сходу сообразить).
2. Инициализируем переменные t=0, s=0
3. Оцениваем: расстояние между точками (x(t), y(t), z(t)) и (u(s), v(s), w(s)) больше, чем заданная погрешность? Если больше, то это конец алгоритма: кривые разные.
4. Оцениваем, какое расстояние меньше: между (x(t+eps), y(t+eps), z(t+eps)) и (u(s), v(s), w(s)), или между (x(t), y(t), z(t)) и (u(s+eps), v(s+eps), w(s+eps)).
5. В зависимости от результатов шага 4 увеличиваем на eps или t, или s. При этом требуем, чтобы t не превысило T, а s не превысило S. Если результаты шага 4 конфликтуют с требованием непревышения, то забиваем на них. Если же требование непревышения выполнить невозможно - и t и s вплотную подобрались к своим максимально допустимым значениям, то это конец алгоритма: кривые совпадают.
6. Переходим к шагу 3.

==================================

Жду контр-примеров от ЛОР-овских математиков и аналитиков ;)

>>Поточнее? пожалуйста. Со сжатием понятно. А что за "допуски"?

Тоже жутко интересно. А также возраст и специальность - если позволите. (Это для градуировки моего глазомера ничего личного)

>>Жду контр-примеров от ЛОР-овских математиков и аналитиков ;)

"Рождение быдлокодера" холст, масло. 2009 г.

И кто после этого будет спорить о нужности матподготовки программистов?

По теме алгоритма - так примерно секретарша макросы пишет в офисе.

Вопрос с автору топика: считается ли, что ломаные на этой картинке http://img53.imageshack.us/img53/6647/56865203.png , однозвенная красная, и трехзвенная зеленая, описывают одну и ту же кривую?

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

В некотором смысле - нет. Касательные векторы к красной и к зеленой ломаным бывают направлены практически в разные стороны. А долны быть в обоих случаях направлены примерно в ту же сторону, что касательный вектор к исходной кривой (если они эту кривую сколько-нибудь адекватно описывают). То же соображения с длинами ломаных и исходной кривой.

> "Рождение быдлокодера" холст, масло. 2009 г. И кто после этого будет спорить о нужности матподготовки программистов?

Глупенький, движение вдоль звеньев можно потом оптимизировать. Вопрос сейчас в самой идее: можно ли проверить "совпадение" ломаных за O(N1+N2)?

>>Вопрос сейчас в самой идее: можно ли проверить "совпадение" ломаных за O(N1+N2)?

Автор не сформулировал вменяемо ни одной задачи - поэтому решение тривиально и имеет порядок О(1).

>>Глупенький, движение вдоль звеньев можно потом оптимизировать

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

Изначально неверно вешать заданный интервал близости на шаг счетчика переменных параметризации и делать его вещественным - когда речь идет о ломаной и дискретном наборе.

> Автор не сформулировал вменяемо ни одной задачи - поэтому решение тривиально и имеет порядок О(1).

Правильная постановка задачи содержит в себе половину решения. А с решениями у автора туго. Вместо глума можно было бы ему помочь, в конце концов раздел форума называется "толксы", а не "лулзы" :D

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

Здоровые люди абстрагируются от ненужных деталей, и стараются сосредоточиться на сути проблемы. Бенефиты от линейности можно будет извлечь и потом - а по-большому счету она ничего не меняет.

> Изначально неверно вешать заданный интервал близости на шаг счетчика переменных параметризации и делать его вещественным - когда речь идет о ломаной и дискретном наборе.

Преждеверенная оптимизация - ты за деревьями не увидишь леса. Думай о близости двух произвольных спрямляемых кривых ;)

>Задача (кратко) - сравнить две ломанные.

Некорректная формулировка.

>состоящие из N1 и N2 элементов ... описывает некоторую кривую

Таким образом задача - сравнить 2 функции, заданные множествами точек N1 и N2.

Для этого есть куча методов, например:

>описывает некоторую кривую

Меры близости на основе вейвлет коэффициентов для сравнения статистических и расчетных временных рядов http://www.ccas.ru/olenev/bo_2006.html

>определить, описывает ли ту же кривую

Алгоритмы выделения параметрических кривых на основе преобразование Хафа http://cgm.computergraphics.ru/content/view/107

>с заданным допуском и коэффициентами сжатия по осям

Любой корреляционный метод, инвариантный к масштабу.