Інтерполяція: малюємо плавні графіки за допомогою кривих Безьє

Доброго часу доби, харбачитник.

У цій статті мені хотілося б розповісти про один придуманий колись алгоритм (або швидше за все - переобретенный велосипед) побудови плавного графіка за заданими точками, використовуючи криві Безьє. Стаття була написана під впливом ось цієї статті і дуже корисного коментаря товариша lany, за що їм окреме спасибі.

Показ завдання

Є масив Y-ків точок, розташованих рівномірно по осі X. Потрібно отримати плавний графік, який проходить через всі задані точки. Приклад на малюнку нижче:

Всіх, кому цікаво, прошу під кат.

Існує ряд стандартних рішень для проведення плавної кривої через точки (з цього приводу багато цікавого написано в вже згаданій статті) таких, як наприклад, інтерполяції сплайнами. Коли на третьому курсі був придуманий цей алгоритм, слово «інтерполяція» вселяло в мене жах, а гуглення за запитом «згладжування графіків» не давало посильних розумінню результатів. Але якось я дійшов до кривих Безьє і вже дуже вони мені сподобалися. Малює швидко, алгоритм інтуїтивно зрозумілий... Що ще треба для щастя. Ну і якось понеслося.

Основна ідея

Розіб'ю ідею на три підпункти, щоб було зрозуміліше і читабельніше.

1. Про кривих Безьє добре написано на віки і на javascript.ru. Якщо уважно читати, можна звернути увагу, що крива Безьє виходить з першої точки відносно прямої початкова _ точка-перша _ опорна _ точка. Аналогічно і в кінці - крива заходить відносно прямої остання _ опорна точка-кінцева _ точка. Таким чином виходить, що якщо у нас одна крива закінчується в точці А і зайшла відносно прямої, а інша крива виходить з цієї точки А щодо тієї-ж прямої а, то цей перехід між двома кривими Безьє у нас вийде плавним.
2. Виходячи з першого пункту виходить, що у нас опорні точки ліворуч і праворуч відносно точки А повинні лежати на одній прямій. Поміркувавши трохи, було вирішено, що ця пряма повинна бути такою, щоб ∠BAB₁=∠CAC₁ (малюнок нижче), де точки B₁ і C₁ - опорні.
3. Відстань від точки А до точок B₁ і C₁ було вирішено взяти рівною половині кроку по X між точками B і A, A і C, і т. д. Мені складно якось обґрунтувати такий вибір, але важливо, щоб ця відстань була менше, ніж крок по X між точками А і B, інакше може вийде щось таке, як на малюнку нижче. Важливо розуміти, що чим більше буде ця відстань, тим більш звивистою буде крива і навпаки. Відстань у половину кроку по X мені здається оптимальною, але тут вже можливі варіанти.

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

Пошук прямої

Як відомо, пряма на площині виражається формулою y = kx + b, де k - тангенс кута нахилу прямої до осі Х, а b - «висота» перетину прямої і осі Y.

Пошук коефіцієнта k

Скажу наперед, що k = tg ( ) = tg ((в-у-у )/2) = (Sqrt ₍((_YA^-YB) 2 + В X2) * ((Y^A-YC) ² + В X2₎  (YA-YB) * (_YA-_YC)) де (В X Точ( Y* (Y-yb розташовані, X) Y) Y) YA- Y- YC- Y- Y- YC- Y- Y- Y- Y- Y- Y- Y- Y- Нижче представлено математичний доказ правильності формули, але якщо ви не в настрої, то можете його просто пропустити.

Математичне виведення коефіцієнта k

1. Нехай кут ∠O₁BA=α, а кут ∠O₂CA=β.

Тоді ∠BAO₁=90^o - ∠CA_O2=9⁰o, так як △A_BO1 і △A_CO2 - прямокутні.

2. (1) ∠B₁AС₁=∠B₁AB+∠BAO₁+∠O₁AС+∠CAС₁=180^o

(2) ∠B₁AB=∠C₁AC - за умовою

(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

3. (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

4. k=tg(φ)=tg((α-β)/2)

З △ABO₁:

sin(α)=[AO₁]/[AB]

cos(α)=[BO₁]/[AB]

З △ACO₂:

sin(β)=[AO₂]/[AC]

cos(β)=[CO₂]/[AC]

Під квадратними дужками мається на увазі довгий відрізок (не хотів використовувати вертикальні прямі - сподіваюся, що читач мене пробачить)

5. З попереднього підпункту випливає:
6. Знаючи, що:

[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'= ^ X/2 * Sqrt (1/( 1 + k²)), координати опорної точки праворуч: X_C1=X_A+ΔX'; Y_C1 = Y_A + k * ^ X', і зліва:X_B1=X_A-ΔX'; Y_B1=Y_A-k*ΔX'.

Трохи математики, яка це доводить

З тригонометрії ми пам'ятаємо, що:

З △AC₁O:

ΔX'=[AO]=[AC₁]*cos(φ).

[C₁O]=[AO]*tg(φ)=k*ΔX'

Якщо ми приймаємо [AC₁] рівним половині кроку по X між основними точками графіка (точками B і A, A і C, т. д.), то:

І ось, власне:

X_C1=X_A+ΔX'

X_B1=X_A-ΔX'

Y_C1=Y_A+k*ΔX'

Y_B1=Y_A-k*ΔX'

До приємного!

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

Приклад реалізації на JSFiddle

UPDATE:

1. Спроби зробити так, щоб опорні точки потрібно було рахувати один раз, а потім, при масштабуванні графіка, просто використовувати їх координати, зазнали невдачі. Все впирається в те, що в розрахунок коефіцієнта k входить і поточний масштаб по X, і поточний масштаб по Y. І витягнути їх з формули не виходить. Товариш quverty мене про це попереджав і виявився правий.
2. Хотів би звернути увагу, що кривизну побудованого графіка можна регулювати. Для цього слід змінювати відстань до опорних точок - змінювати коефіцієнт ^ X'= ^ X/2 * Sqrt (1^/( 1 + k2)), а саме - знаменник ось цього його шматочка: ΔX/2. Знаменник менше 1 брати не слід (читай третій підпункт пункту «Основна ідея»). Поекспериментувати можна на JSFiddle (129 рядок JavaScript-а).
3. Зверніть увагу на реалізацію сплайну Катмулла-Рома товариша ^ vana. І спасибі йому за цей коментар.