Interpolation: draw smooth graphs using Bezier curves
Good day, harbachitel.
In this article, I would like to talk about one once invented algorithm (or, most likely, a reinvented bicycle) for constructing a smooth graph at given points using Bézier curves. The article was written under the influence of this article and a very useful commentary by comrade lany , for which I would like to thank them specially .
Problem statement
There is an array of Y-points that are distributed uniformly along the X axis. You need to get a smooth graph that goes through all the given points. An example in the figure below:
Anyone who is interested, I ask under the cat.
There are a number of standard solutions for drawing a smooth curve through points (a lot of interesting things were written in the already mentioned article ), such as, for example, interpolation with splines. When this algorithm was invented in the third year, the word “interpolation” shocked me, and googling for the query “smoothing graphs” did not give any meaningful understanding of the results. But somehow I got to the Bezier curves and I really liked them. Draws quickly, the algorithm is intuitive ... What else is needed for happiness. Well, somehow it started.
I will divide the idea into three subparagraphs, so that it is more understandable and readable.
Thus, it turns out that the problem reduces to finding a straight line ( B 1 C 1 ) and, in fact, reference points B 1 and C 1 , from which we will then construct Bezier curves.
As you know, a line on the plane is expressed by the formula y = kx + b , where k is the tangent of the angle of inclination of the line to the X axis, and b is the "height" of the intersection of the line and the Y axis.
I will say in advance that k = tg (φ) = tg ((α-β) / 2) = (Sqrt (((Y A -Y B ) 2 + ΔX 2 ) * ((Y A -Y C ) 2 + ΔX 2 )) - ΔX 2 - (Y A -Y B ) * (Y A -Y C )) / (ΔX * (Y C -Y B )) , where ΔX is the distance along X between the points in the graph (I recall that us points are evenly distributed along X). Below is a mathematical proof of the correctness of the formula, but if you are not in the mood, you can simply skip it.
And so, k we found. Looking ahead, I’ll say that b is not useful to us in our calculations. Let's start the search for reference points.
Imust say right away that: ΔX '= ΔX / 2 * Sqrt (1 / (1 + k 2 )) , the coordinates of the reference point on the right: X C1 = X A + ΔX'; Y C1 = Y A + k * ΔX ' , and to the left: X B1 = X A -ΔX'; Y B1 = Y A -k * ΔX ' .
JSFiddle UPDATE implementation example
:
In this article, I would like to talk about one once invented algorithm (or, most likely, a reinvented bicycle) for constructing a smooth graph at given points using Bézier curves. The article was written under the influence of this article and a very useful commentary by comrade lany , for which I would like to thank them specially .
Problem statement
There is an array of Y-points that are distributed uniformly along the X axis. You need to get a smooth graph that goes through all the given points. An example in the figure below:
Anyone who is interested, I ask under the cat.
There are a number of standard solutions for drawing a smooth curve through points (a lot of interesting things were written in the already mentioned article ), such as, for example, interpolation with splines. When this algorithm was invented in the third year, the word “interpolation” shocked me, and googling for the query “smoothing graphs” did not give any meaningful understanding of the results. But somehow I got to the Bezier curves and I really liked them. Draws quickly, the algorithm is intuitive ... What else is needed for happiness. Well, somehow it started.
main idea
I will divide the idea into three subparagraphs, so that it is more understandable and readable.
- Bezier curves are well written on the wiki and on javascript.ru . If you carefully read, you can pay attention to the fact that the Bezier curve leaves the first point with respect to the straight line initial_point-first_support_point. Similarly, at the end, the curve goes along the line last_support_point-end_point. Thus, it turns out that if one curve ends at point A and goes tangent to the line a , and the other curve leaves this point A with respect to the same line a , then this transition between the two Bezier curves will turn out smooth.
- Based on the first paragraph, it turns out that we have the anchor points on the left and right relative to point A should lie on one straight line. After thinking a bit, it was decided that this line should be such that ∠BAB 1 = ∠CAC 1 (figure below), where the points B 1 and C 1 are reference points .
- It was decided to take the distance from point A to points B 1 and C 1 equal to half the step along X between points B and A , A and C , etc. It’s difficult for me to somehow justify such a choice, but it’s important that this distance is less than the step along X between points A and B , otherwise something like that in the figure below may turn out. It is important to understand that the greater this distance, the more tortuous the curve will be and vice versa. The distance of half a step along X seems to me optimal, but there are already possible options.
Thus, it turns out that the problem reduces to finding a straight line ( B 1 C 1 ) and, in fact, reference points B 1 and C 1 , from which we will then construct Bezier curves.
Direct search
As you know, a line on the plane is expressed by the formula y = kx + b , where k is the tangent of the angle of inclination of the line to the X axis, and b is the "height" of the intersection of the line and the Y axis.
Search for coefficient k
I will say in advance that k = tg (φ) = tg ((α-β) / 2) = (Sqrt (((Y A -Y B ) 2 + ΔX 2 ) * ((Y A -Y C ) 2 + ΔX 2 )) - ΔX 2 - (Y A -Y B ) * (Y A -Y C )) / (ΔX * (Y C -Y B )) , where ΔX is the distance along X between the points in the graph (I recall that us points are evenly distributed along X). Below is a mathematical proof of the correctness of the formula, but if you are not in the mood, you can simply skip it.
Mathematical derivation of the coefficient k
- Let the angle ∠O 1 BA = α , and the angle ∠O 2 CA = β .
Then ∠BAO 1 = 90 o -α ; ∠CAO 2 = 90 o -β , since △ ABO 1 and △ ACO 2 are rectangular. - (1) ∠B 1 AC 1 = ∠B 1 AB + ∠BAO 1 + ∠O 1 AC + ∠CAС 1 = 180 o
(2) ∠B 1 AB = ∠C 1 AC - by condition
(3) ∠BAO 1 = 90 o -α
(4) ∠O 1 AC = ∠CAO 2 = 90 o -β
From (1), (2), (3) and (4) it turns out that:
2 * ∠C 1 AC + (90 o -α) + (90 o -β) = 180 o
2 * ∠C 1 AC + 180 o -α-β = 180 o
(5) ∠C 1 AC = (α + β) / 2 - (6) ∠C 1 AC = ∠C 1 AD + ∠DAC = φ + ∠DAC
(7) ∠DAC = ∠O 2 CA = β - as internal miscellaneous angles formed by two parallel straight lines (AD) and (O 2 C) and secant (AC)
From (5), (6) and (7) it turns out that:
∠C 1 AC = φ + ∠DAC
(α + β) / 2 = φ + β
φ + β = (α + β) / 2
(8) φ = (α-β) / 2 - k = tg (φ) = tg ((α-β) / 2)
From △ ABO 1 :
sin (α) = [AO 1 ] / [AB]
cos (α) = [BO 1 ] / [AB]
From △ ACO 2 :
sin (β) = [AO 2 ] / [AC]
cos (β) = [CO 2 ] / [AC]
The square brackets mean the length of the segment (did not want to use vertical lines - I hope the reader will forgive me) - From the previous subparagraph follows:
- Knowing that:
[BO 1 ] = [CO 2 ] = ΔX
[AO 1 ] = Y A -Y B
[AO 2 ] = Y A -Y C
[AB] = Sqrt ([AO 1 ] 2 + [BO 1 ] 2 ) = Sqrt ((Y A -Y B ) 2 + ΔX 2 )
[AC] = Sqrt ([AO 2 ] 2 + [CO 2 ] 2 ) = Sqrt ((Y A -Y C ) 2 + ΔX 2 )
We get that:
And so, k we found. Looking ahead, I’ll say that b is not useful to us in our calculations. Let's start the search for reference points.
We are looking for reference points
I
A bit of math that proves it
From trigonometry, we recall that:
From △ AC 1 O :
ΔX '= [AO] = [AC 1 ] * cos (φ).
[C 1 O] = [AO] * tg (φ) = k * ΔX '
If we take [AC 1 ] equal to half the X step between the main points of the graph (points B and A , A and C , etc.) , then:
And now, in fact:
X C1 = X A + ΔX '
X B1 = X A -ΔX'
Y C1 = Y A + k * ΔX '
Y B1 = Y A-k * ΔX '
From △ AC 1 O :
ΔX '= [AO] = [AC 1 ] * cos (φ).
[C 1 O] = [AO] * tg (φ) = k * ΔX '
If we take [AC 1 ] equal to half the X step between the main points of the graph (points B and A , A and C , etc.) , then:
And now, in fact:
X C1 = X A + ΔX '
X B1 = X A -ΔX'
Y C1 = Y A + k * ΔX '
Y B1 = Y A-k * ΔX '
To pleasant!
- From comrade lany (thank you very much for that and plus him karma) I learned that html5 using the quadraticCurveTo () and bezierCurveTo () functions can draw Bezier curves on canvas itself. Accordingly, the algorithm can be applied with JavaScript.
- A nice feature of the algorithm is that the graph predictably “sticks out” beyond the boundaries of the space of points through which we actually draw the graph. If we take the distance to the anchor points equal to half the step along X (segment [AC 1 ] in the last figure), then a gap of a quarter step along X above and below the canvas’s borders will be enough.
JSFiddle UPDATE implementation example
:
- Attempts to make the control points need to be counted once, and then, when scaling the chart, just using their coordinates failed. It all comes down to the fact that the calculation of the coefficient k includes both the current scale in X and the current scale in Y. And drawing them out of the formula does not work. Comrade quverty warned me about this and turned out to be right.
- I would like to draw attention to the fact that the curvature of the plotted plot can be adjusted. To do this, you must change the distance to the reference points - change the coefficient
ΔX '= ΔX / 2 * Sqrt (1 / (1 + k 2 )) , namely, the denominator of this piece of it:ΔX / 2 . A denominator of less than 1 should not be taken (read the third subparagraph of the paragraph "Main idea"). You can experiment with JSFiddle (line 129 of JavaScript). - Pay attention to the implementation of the Kathmulla-Roma spline of comrade IIvana . And thanks to him for this comment.