Как правильно построить гладкую кривую имея набор точек?
Задача следующая: пользователь ведет пальцем по экрану и вслед за пальцем на экране должна отображаться красивая гладкая кривая. В качестве примера, можно посмотреть как работает программа для ipad penultimate. Там получаются очень красивые линии.
Сейча я строю кривую из сегментов, представляющих собой кубические кривые Безье. Пробовал разные варианты. Пока лучший результат дали два способа:
1) Сегметы строятся между каждой пары точек, полученных от пользователя (между первой и второй, затем между второй и третьей и т.д.). Недостающие точки приблизительно рассчитываю математически.
Точки считаю так:
P1' = (P2 — P1) / a
Pi' = (Pi+1 — Pi-1) / a (for i=2..n-1)
Pn' = (Pn — Pn-1) / a
B1i = Pi + Pi'/3
B2i = Pi+1 — Pi+1'/3
где Pi — точка полученная от пользователя, а B1i и B2i — искомые точки.
Итог: кривая определенно есть, но недостаточно гладкая. Либо я не верно рассчитываю точки, либо способ не самый лучший.
2) Все четыре точки для сегмента беру из набора, полученного от пользователя. Чтобы избежать острых углов между соседними сегментами смещаю вторую точку текущего сегмента, основываясь на положении третьей точки предыдущего (так чтобы 3-я и 4-я точки предыдущего сегмента, а также 2-я точка текущего лежали на одной прямой).
Итог: не лучше чем в первом случае.
Как сделать чтобы кривая была более гладкой, как в penultimate?
По-моему, что-то похожее описано у Кнута в книге «Все про Metafont» (в третьей главе). Вообще там используются кривые Безье, но оператор задает непосредственно только крайние точки, через которые кривая будет на самом деле проходить, а вспомогательные точки алгоритм рассчитывает сам.
Чтобы избежать углов в точках необходимо ввести у исходные формулы условие непрерывности производных первого порядка в точках, т.к. непрерывность первой производной и является критерием гладкой кривой.
Предлагаю использовать гибрид. Выводиться: уравнение кривой, порядок гладкости который вас устраивает и выводиться уравнение прямой. Около точек касания используем первый тип кривой, вдали второй. Регулируем этот процесс с помощью весовой функции, которая зависит от расстояния до ближайшей точки:
(1-p®)*f1(x)+p®*f2(x). При удаление r — большое, результат f2(x). При стремление к точке, результат f1. В промежутке суммируем функции. Весовая функция от 0 до 1.
Осталось подобрать весовую функцию, которая будет идеально сочетать гладкость около точки и прямолинейность между точками. Данный подход хорошо работает для некоторых задач построения карт.
Простой
