Главная

Интерполяция: рисуем плавные графики с помощью кривых Безье

2016-05-03 в 6:48, admin, рубрики: canvas, html, javascript, Алгоритмы, безье, графики, интерполяция, Программирование

Доброго времени суток, харбачитатель.

В этой статье мне хотелось бы рассказать об одном придуманном когда-то алгоритме (или скорее всего — переизобретённом велосипеде) построенного плавного графика по заданным точкам, используя кривые Безье. Статья была написана под влиянием вот этой статьи и очень полезного комментария товарища lany, за что им отдельное спасибо.

Постановка задачи
Есть массив Y-ков точек, расположенных равномерно по оси X. Нужно получить плавный график, который проходит через все заданные точки. Пример на рисунке ниже:

Интерполяция: рисуем плавные графики с помощью кривых Безье - 1

Всех, кому интересно, прошу под кат.

Существует ряд стандартных решений для проведения плавной кривой через точки (по этому поводу много интересного написано в уже упомянутой статье) таких, как например, интерполяции сплайнами. Когда на третьем курсе был придуман этот алгоритм, слово «интерполяция» вселяло в меня ужас, а гугление по запросу «сглаживание графиков» не давало посильных пониманию результатов. Но как-то я дошел до кривых Безье и уж очень они мне понравились. Рисует быстро, алгоритм интуитивно понятный… Что еще надо для счастья. Ну и как-то понеслось.

Основная идея

Разобью идею на три подпункта, чтобы было понятней и читабельней.

О кривых Безье хорошо написано на вики и на javascript.ru. Если внимательно читать, то можно обратить внимание, что кривая Безье выходит из первой точки касательно к прямой начальная_точка-первая_опорная_точка. Аналогично и в конце — кривая заходит касательно прямой последняя_опорная_точка-конечная_точка. Таким образом получается, что если у нас одна кривая заканчивается в точке А и зашла касательно к прямой а, а другая кривая выходит из этой точки А касательно к той-же прямой а, то этот переход между двумя кривыми Безье у нас получится плавным.
Исходя из первого пункта получается, что у нас опорные точки слева и справа относительно точки А должны лежать на одной прямой. Поразмыслив немного, было решено, что эта прямая должна быть такой, чтобы ∠BAB₁=∠CAC₁ (рисунок ниже), где точки B₁ и C₁ — опорные.
Расстояние от точки А до точек B₁ и C₁ было решено взять равным половине шага по X между точками B и A, A и C, и т.д. Мне сложно как-то обосновать такой выбор, но важно, чтобы это расстояние было меньше, чем шаг по X между точками А и B, иначе может получится что-то такое, как на рисунке ниже. Важно понимать, что чем больше будет это расстояние, тем более извилистой будет кривая и наоборот. Расстояние в половину шага по X мне кажется оптимальным, но тут уже возможны варианты.

Таким образом получается, что задача сводится к поиску прямой (B₁C₁) и, собственно, опорных точек B₁ и C₁, по которым мы потом будем строить кривые Безье.

Поиск прямой

Как известно, прямая на плоскости выражается формулой y=kx+b, где k — тангенс угла наклона прямой к оси Х. Когда мы найдем k, то зная, что прямая проходит через точку А, и зная ее координаты, мы легко можем найти b: b=Y_A-kX_A. Таким образом все сводится к поиску коэффициента k.

Поиск коэффициента k

Скажу наперед, что k = tg(φ) = tg((α-β)/2) = (Sqrt((ΔX²+(Y_A-Y_B)²)*(ΔX²+(Y_A-Y_C)²))-ΔX²-(Y_A-Y_B)*(Y_A-Y_C)) / (ΔX*((Y_A-Y_B)-(Y_A-Y_C))), где ΔX — расстояние по Х между точками (напомню, что у нас точки расположены равномерно по Х). Ниже представлено математическое доказательство правильности формулы, но если вы не в настроении, то можете его просто пропустить.

Интерполяция: рисуем плавные графики с помощью кривых Безье - 4

Математическое выведение коэффициента k

Пускай угол ∠O₁BA=α, а угол ∠O₂СA=β.
Тогда ∠BAO₁=90^o-α; ∠CAO₂=90^o-β, так как △ABO₁ и △ACO₂ — прямоугольные.
(1) ∠B₁AС₁=∠B₁AB+∠BAO₁+∠O₁AС+∠CAС₁=180^o
(2) ∠B₁AB=∠C₁AС — по условию
(3) ∠BAO₁=90^o-α
(4) ∠O₁AС=∠CAO₂=90^o-β

Из (1), (2), (3) и (4) получается, что:
2*∠C₁AС+(90^o-α)+(90^o-β)=180^o
2*∠C₁AС+180^o-α-β=180^o
(5) ∠C₁AС=(α+β)/2
(6) ∠C₁AС=∠C₁AD+∠DAC=φ+∠DAC
(7) ∠DAC=∠O₂CA=β — как внутренние разносторонние углы образованные двумя параллельными прямыми (AD) и (O₂C) и секущей (AC)

Из (5), (6) и (7) получается, что:
∠C₁AС=φ+∠DAC
(α+β)/2=φ+β
φ+β=(α+β)/2
(8) φ=(α-β)/2
k=tg(φ)=tg((α-β)/2)
Из △ABO₁:
sin(α)=[AO₁]/[AB]
cos(α)=[BO₁]/[AB]

Из △ACO₂:
sin(β)=[AO₂]/[AC]
cos(β)=[CO₂]/[AC]

Под квадратными скобками подразумевается длинна отрезка (не хотел использовать вертикальные прямые — надеюсь, что читатель меня простит)
Из предыдущего подпункта следует:
Зная, что:
[BO₁]=[CO₂]=ΔX
[AO₁]=Y_A-Y_B
[AO₂]=Y_A-Y_C
[AB]=Sqrt([AO₁]²+[BO₁]²)=Sqrt((Y_A-Y_B)²+ΔX²)
[AC]=Sqrt([AO₂]²+[CO₂]²)=Sqrt((Y_A-Y_C)²+ΔX²)

Получаем, что:

И так, k мы нашли; b мы тоже знаем (смотри выше), а значит прямая, на которой лежат опорные точки, нам известна.

Ищем опорные точки

Сразу скажу, что: ΔX'=Sqrt(ΔX²/(4+4*k)), координаты опорной точки справа: X_C1=X_A+ΔX'; Y_C1=k*X_C1+b, и слева:X_B1=X_A-ΔX'; Y_B1=k*X_B1+b.

Интерполяция: рисуем плавные графики с помощью кривых Безье - 7

Немного математики, которая это доказывает

Из тригонометрии мы помним, что:
Интерполяция: рисуем плавные графики с помощью кривых Безье - 8

Из △AC₁O:
ΔX'=[AC₁]*cos(φ).

Если мы принимаем [AC₁] равным половине шага по X между основным точками графика (точками B и A, A и C, т.д.), то:
Интерполяция: рисуем плавные графики с помощью кривых Безье - 9

И вот, собственно:
X_C1=X_A+ΔX'
X_B1=X_A-ΔX'
Y_C1=k*X_C1+b
Y_B1=k*X_B1+b

К приятному!

От товарища lany (огромное ему за это спасибо и плюс ему к карме) я узнал, что html5 с помощью функций quadraticCurveTo() и bezierCurveTo() умеет рисовать по canvas-у кривые Безье сам. Соответственно, алгоритм можна применить с JavaScript-ом.
Приятной особенностью алгоритма есть то, что график предсказуемо «выпирает» за границы пространства точек, через которые мы собственно проводим график. Если брать расстояние до опорных точек равными половине шага по X (отрезок [AC₁] на последнем рисунке), то зазора в четверть шага по X сверху и снизу от границ canvas-а будет достаточно.

Пример реализации на JSFiddle

Автор: Nabytovych

Источник