Поиск алгоритма «замыкания кривых, соединяющихся относительно точек»

Question

Я ищу алгоритм, который может соединять точки непрерывной линией кривой.Представьте, что вы рисуете от точки a до b до c до последней точки, и когда вы рисуете от точки к точке, линия должна быть кривой и является непрерывной относительно предыдущей точки и следующей точки, как если бы данные точки были просто образцамизамкнутого цикла.Пожалуйста, смотрите рисунок ниже для иллюстрации.

Существует ли такой алгоритм для чего-то подобного?

* Круги на рисунке - мой список точек.

Answer 1

Учитывая, что ваши точки упорядочены, сплайн-интерполяция, безусловно, является наилучшим способом. (Как указано в комментарии bo1024) Я настоятельно рекомендую следующие примечания:

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/

И, в частности, данный раздел будет наиболее релевантным для получения замкнутого цикла, как вы просили:

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/B-spline/bspline-curve-closed.html

РЕДАКТИРОВАТЬ: если кривая должна проходить через точки, то единственным решением степени n является интерполяционный полином Лагранжа. Вы можете просто сделать один полином для каждого компонента ваших векторов точек, используя формулу на вики-странице:

http://en.wikipedia.org/wiki/Lagrange_polynomial

К сожалению, интерполяция Лагранжа может быть довольно шумной, если у вас слишком много точек. В результате я все же рекомендовал бы использовать некоторую сплайн-интерполяцию с фиксированной степенью. Вместо B-сплайнов другим вариантом являются полиномы Эрмита:

http://en.wikipedia.org/wiki/Cubic_Hermite_spline

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

Answer 2

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

Например, эволюционные алгоритмы легко адаптировать, и вы найдете множество ссылок на их использование для решения TSP.