Кривая подгонки несортированных точек на плоскости

Question

Вопрос: Как вы подгоняете кривую к точкам на плоскости, если они не являются однозначными?

Для показанного примера, как можно подогнать кривую (например, черную) к шумно-голубым данным? Это похоже на сглаживание сплайнов, но я не знаю порядок данных.

Было бы предпочтительнее Matlab, но с псевдокодом все в порядке. Или указатель на правильную терминологию для этой проблемы было бы здорово.

Спасибо

Answer 1

Ваши данные выглядят как двумерный параметрический график из (x,y) как функция некоторого базового параметра t. Таким образом, может быть возможно сделать наименьших квадратов подгонки x(t) и y(t), если вы сможете придумать для них разумную модель. Похоже, ваши данные описывают limacon .

Answer 2

Я не эксперт в этом, но нашел эту страницу , говоря о реконструкции кривой , которая, кажется, подходит вашему вопросу Все еще читаю газеты и с трудом понимаю их, поэтому я пока не могу найти решение.

Answer 3

Для кусочных приближений с использованием B-сплайнов вы можете использовать этот пакет Matlab . Работает в автоматическом и полуручном режимах.

Answer 4

Вы можете попытаться определить порядок точек, а затем применить сплайн-процедуры. конечно, существует неопределенность, когда кривая пересекает себя.

пожалуй, самый наивный подход - это вычисление триангуляции Делоне (время nlogn), из которой аппроксимируется евклидово минимальное расстояние гамильтонова цикла через точки. Вам все равно придется выяснить, где находятся «концы». После заказа вы можете применить методы сплайна. Для справки см. Нахождение гамильтоновых циклов в триангуляциях Делоне. NP-Complete , или статью Рейнельта об эвристике TSP, 1992, или EMST в Википедии

НТН,

Answer 5

Редактировать: nvm неверно истолковал вопрос. Я все равно оставлю здесь этот ответ.

Возможно, попробуйте сначала найти выпуклую оболочку из точек, а затем установить выпуклую оболочку на плоскости

http://www.cse.unsw.edu.au/~lambert/java/3d/giftwrap.html http://en.wikipedia.org/wiki/Convex_hull_algorithms

Если вам не нужна эффективность, есть несколько очень простых реализаций, таких как версия подарочной упаковки, которая называется O (n ^ 2) http://en.wikipedia.org/wiki/Gift_wrapping_algorithm

Версия "разделяй и властвуй" - O (nlogn)

Answer 6

Эта проблема действительно сложная, если у вас нет заказа. Делать наименьшие квадраты для некоторых (x (t), y (t)) легко - при условии, что вы знаете порядок t .

Возможно, вам понадобится какой-то алгоритм поиска. Генетический алгоритм может быть в порядке.

Answer 7

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