Вопрос: Как вы соответствуете кривой точкам на плоскости, если они не являются однозначными?Кривая установки несортированных точек на плоскости
Для примера показано, как можно подогнать кривую (например, черную) к шумным синим данным? Это похоже на сглаживание сплайнов, но я не знаю порядок данных.
Matlab было бы предпочтительным, но псевдокод прекрасно. Или указатель на то, что правильная терминология для этой проблемы будет велика.
Благодаря
Проверьте эту статью: Shape-preserving least-squares approximation by polynomial parametric spline curves, кажется, a решение. Также см. Библиографию в конце.
Вам придется сделать несколько кусочно фитинга или шлицы. Не ожидайте, что любой алгоритм сможет сделать все это за один раз. Может быть как минимум три кривые: первая - до пересечения, петля, а затем назад от пересечения вперед.
Редактировать: nvm неверно истолковал вопрос. В любом случае, я оставлю этот ответ.
Может быть, попытаться найти convex hull точек первой смонтируйте выпуклой оболочки на равнине
< http://www.cse.unsw.edu.au/~lambert/java/3d/giftwrap.html --includes ява анимации реализации http://en.wikipedia.org/wiki/Convex_hull_algorithms
Если вы не хотите эффективности Есть некоторые очень простые реализации, такие как версия для упаковки подарка, которая представляет собой O (n^2) http://en.wikipedia.org/wiki/Gift_wrapping_algorithm
Вариант разрыва и покорения O (nlogn)
Ваши данные выглядят как двумерные parametric plot из (x,y) как функция некоторого базового параметра t. Таким образом, может быть возможно выполнить least-squares при посадке x(t) и y(t), если вы можете найти подходящую модель для них. Ваши данные выглядят как limacon.
+1 - очень приятно. – duffymo
Хотя данные, показанные * *, имеют основную кривую (функция розы), это было просто потому, что было легко сделать сюжет. Мне нужно подогнать кривую к любым произвольным данным. – tkw954
Вы должны знать что-то о базовых данных для любого подходящего подбора кривой. Из приведенного выше примера нет особой причины (для наивного алгоритма), чтобы выбрать прямо на пересечении, вместо того, чтобы делать два резких правильных поворота. Вы можете поместить любую кривую в любой набор точек, это просто вопрос «пригодности». Вам нужна эвристика, чтобы выбрать, какую кривую вы собираетесь использовать, тогда любая стандартная процедура минимизации ошибок будет соответствовать кривой точкам. –
Эта проблема действительно трудно, если у вас нет заказа. Выполнение наименьших квадратов на некотором (x (t), y (t)) легко - при условии, что вы знаете порядок t.
Возможно, вам понадобится какой-то алгоритм поиска. Генетический алгоритм может быть в порядке.
вы можете попытаться сделать вывод о точках, а затем применить процедуры сплайна. есть двусмысленность, где кривая пересекает себя, конечно.
Возможно, самым наивным подходом было бы вычисление триангуляции Делоне (nlogn time), из которой аппроксимирует цикл гамильтониана минимального расстояния Евклида через точки. Вам все равно придется выяснить, где «концы». После заказа вы можете применить методы сплайнов.Для справки см Finding Hamiltonian Cycles in Delaunay Triangulations Is NP-Complete, или бумага Reinelt на TSP эвристик, 1992, или Эмсте в Википедии
НТН,
Для кусочно приближений с использованием B-сплайнов можно использовать this Matlab пакет. Он работает в автоматическом и полуавтоматическом режимах.
Что бы вы хотели получить, в результате? Это одно уравнение? Или сплайны? Или что-то другое? –
Лучше всего было бы одно уравнение (вернее, два x = f (t) y = f (t)), хотя кусочно-уравнения тоже ок. – tkw954