- PVSM.RU - https://www.pvsm.ru -
Доброго времени суток, харбачитатель.
В этой статье мне хотелось бы рассказать об одном придуманном когда-то алгоритме (или скорее всего — переизобретённом велосипеде) построенного плавного графика по заданным точкам, используя кривые Безье. Статья была написана под влиянием вот этой статьи [1] и очень полезного комментария [2] товарища lany [3], за что им отдельное спасибо.
Постановка задачи
Есть массив Y-ков точек, расположенных равномерно по оси X. Нужно получить плавный график, который проходит через все заданные точки. Пример на рисунке ниже:
Всех, кому интересно, прошу под кат.
Существует ряд стандартных решений для проведения плавной кривой через точки (по этому поводу много интересного написано в уже упомянутой статье [1]) таких, как например, интерполяции сплайнами. Когда на третьем курсе был придуман этот алгоритм, слово «интерполяция» вселяло в меня ужас, а гугление по запросу «сглаживание графиков» не давало посильных пониманию результатов. Но как-то я дошел до кривых Безье и уж очень они мне понравились. Рисует быстро, алгоритм интуитивно понятный… Что еще надо для счастья. Ну и как-то понеслось.
Разобью идею на три подпункта, чтобы было понятней и читабельней.
Таким образом получается, что задача сводится к поиску прямой (B1C1) и, собственно, опорных точек B1 и C1, по которым мы потом будем строить кривые Безье.
Как известно, прямая на плоскости выражается формулой y=kx+b, где k — тангенс угла наклона прямой к оси Х. Когда мы найдем k, то зная, что прямая проходит через точку А, и зная ее координаты, мы легко можем найти b: b=YA-kXA. Таким образом все сводится к поиску коэффициента k.
Скажу наперед, что k = tg(φ) = tg((α-β)/2) = (Sqrt((ΔX2+(YA-YB)2)*(ΔX2+(YA-YC)2))-ΔX2-(YA-YB)*(YA-YC)) / (ΔX*((YA-YB)-(YA-YC))), где ΔX — расстояние по Х между точками (напомню, что у нас точки расположены равномерно по Х). Ниже представлено математическое доказательство правильности формулы, но если вы не в настроении, то можете его просто пропустить.
Из (1), (2), (3) и (4) получается, что:
2*∠C1AС+(90o-α)+(90o-β)=180o
2*∠C1AС+180o-α-β=180o
(5) ∠C1AС=(α+β)/2
Из (5), (6) и (7) получается, что:
∠C1AС=φ+∠DAC
(α+β)/2=φ+β
φ+β=(α+β)/2
(8) φ=(α-β)/2
Из △ABO1:
sin(α)=[AO1]/[AB]
cos(α)=[BO1]/[AB]
Из △ACO2:
sin(β)=[AO2]/[AC]
cos(β)=[CO2]/[AC]
Под квадратными скобками подразумевается длинна отрезка (не хотел использовать вертикальные прямые — надеюсь, что читатель меня простит)
Получаем, что:
И так, k мы нашли; b мы тоже знаем (смотри выше), а значит прямая, на которой лежат опорные точки, нам известна.
Сразу скажу, что: ΔX'=Sqrt(ΔX2/(4+4*k)), координаты опорной точки справа: XC1=XA+ΔX'; YC1=k*XC1+b, и слева:XB1=XA-ΔX'; YB1=k*XB1+b.
Из △AC1O:
ΔX'=[AC1]*cos(φ).
Если мы принимаем [AC1] равным половине шага по X между основным точками графика (точками B и A, A и C, т.д.), то:
И вот, собственно:
XC1=XA+ΔX'
XB1=XA-ΔX'
YC1=k*XC1+b
YB1=k*XB1+b
Пример реализации на JSFiddle [9]
Автор: Nabytovych
Источник [10]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/javascript/119788
Ссылки в тексте:
[1] вот этой статьи: http://habrahabr.ru/post/130873/
[2] очень полезного комментария: http://habrahabr.ru/post/163073/#comment_5615389
[3] lany: https://habrahabr.ru/users/lany/
[4] вики: https://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B8%D0%B2%D0%B0%D1%8F_%D0%91%D0%B5%D0%B7%D1%8C%D0%B5
[5] javascript.ru: http://learn.javascript.ru/bezier
[6] внутренние разносторонние углы образованные двумя параллельными прямыми (AD) и (O2C) и секущей (AC): http://goo.gl/jp6o28
[7] quadraticCurveTo(): http://www.html5canvastutorials.com/tutorials/html5-canvas-quadratic-curves/
[8] bezierCurveTo(): http://www.html5canvastutorials.com/tutorials/html5-canvas-bezier-curves/
[9] JSFiddle: http://jsfiddle.net/Nabytovych/L9ojewkm/
[10] Источник: https://habrahabr.ru/post/247235/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.