Вопрос: Как подобрать кривую к точкам на плоскости, если они не однозначны?
В показанном примере, как подобрать кривую (например, черную) к синим зашумленным данным? Это похоже на сглаживание сплайнов, но я не знаю порядка данных.
Matlab был бы предпочтительнее, но псевдокод подойдет. Или указатель на правильную терминологию для этой проблемы было бы замечательно.
Спасибо
Ваши данные выглядят как двумерный параметрический график (x,y) как функции некоторого базового параметра t. Таким образом, можно выполнить подгонку методом наименьших квадратов x(t) и y(t), если сможете придумайте для них разумную модель. Похоже, ваши данные описывают лимакон.
Изменить: 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)
вы можете попытаться определить порядок точек, а затем применить сплайновые процедуры. конечно, существует двусмысленность там, где кривая пересекает саму себя.
возможно, наиболее наивным подходом было бы вычислить триангуляцию Делоне (время без учета времени), исходя из которой аппроксимируют евклидов гамильтонов цикл минимального расстояния через точки. Вам все равно придется выяснить, где находятся «концы». После этого вы сможете применить технику сплайнов. Для справки см. Поиск гамильтоновых циклов в триангуляции Делоне является NP- Complete, или статью Райнельта об эвристике TSP, 1992 г., или EMST в Википедии
hth,
Для кусочных аппроксимаций с использованием B-сплайнов вы можете использовать этот пакет Matlab. Работает в автоматическом и полуручном режимах.
Я не эксперт в этом, но я нашел эту страницу, речь идет о реконструкции кривой, которая, кажется, соответствует вашему вопросу. Все еще читаю газеты и с трудом разбираюсь в них, поэтому пока не могу предложить решение.
Вам придется делать несколько кусочков или шлицев. Не ожидайте, что какой-либо алгоритм сможет сделать все за один раз. Может быть как минимум три дуги: первая до перекрестка, петля, а затем назад от перекрестка вперед.
Эта проблема действительно сложна, если у вас нет заказа. Выполнить метод наименьших квадратов для некоторых (x (t), y (t)) легко - если вы знаете порядок t.
Возможно, вам понадобится какой-нибудь алгоритм поиска. Генетический алгоритм может подойти.
