Вопрос: Как вы соответствуете кривой точкам на плоскости, если они не являются однозначными?
В приведенном примере, как бы подогнать кривую (например, черную) к шумным синим данным? Это похоже на сглаживание сплайнов, но я не знаю порядок данных.
Matlab будет предпочтительнее, но псевдокод в порядке. Или указатель на то, что правильная терминология для этой проблемы будет большой.
Спасибо
Проверьте эту статью: Аппроксимация наименьших квадратов с помощью полиномиальных параметрических кривых сплайна, кажется, представляет собой решение. Кроме того, см. Библиографию в конце.
Ваши данные выглядят как двумерный параметрический график (x,y) как функция некоторого базового параметра t. Таким образом, может быть возможно выполнить наименьшие квадраты подгонки x(t) и y(t), если вы можете придумать разумную модель для них. Ваши данные, как представляется, описывают limacon.
Изменить: nvm неправильно истолковал вопрос. В любом случае, я оставлю этот ответ.
Возможно, попробуйте найти выпуклый корпус точек, а затем установите выпуклую оболочку на равнине
http://www.cse.unsw.edu.au/~lambert/java/3d/giftwrap.html < - включает java-анимацию реализации http://en.wikipedia.org/wiki/Convex_hull_algorithms
Если вы не хотите эффективности, есть некоторые очень простые реализации, такие как версия упаковки подарка, которая является O (n ^ 2) http://en.wikipedia.org/wiki/Gift_wrapping_algorithm
В версии с разделителем и покорением O (nlogn)
вы можете попытаться сделать вывод о точках, а затем применить процедуры сплайнов. есть двусмысленность, где кривая пересекает себя, конечно.
возможно, самым наивным подходом было бы вычисление триангуляции Делоне (nlogn time), из которой аппроксимирует цикл гамильтониана минимального расстояния Евклида через точки. Вам все равно придется выяснить, где "концы". После заказа вы можете применить методы сплайнов. Для справки см. Поиск гамильтоновых циклов в триангуляциях Delaunay NP-Complete или статья Рейнельта по эвристике TSP, 1992 или EMST в Википедии
HTH,
Для кусочных аппроксимаций с использованием B-сплайнов вы можете использовать этот пакет Matlab. Он работает в автоматическом и наполовину ручном режимах.
Вам придется делать несколько кусочных фитингов или сплайнов. Не ожидайте, что любой алгоритм сможет сделать все это за один раз. Может быть как минимум три кривые: первая - до пересечения, петля, а затем назад от перекрестка вперед.
Эта проблема действительно сложна, если у вас нет заказа. Выполнение наименьших квадратов на некотором (x (t), y (t)) легко - если вы знаете порядок t.
Вам, вероятно, понадобится какой-то алгоритм поиска. Генетический алгоритм может быть в порядке.