Draw smooth graphs using Bezier curves. Version 2
Good day, dear reader.
This is how the article begins, introducing the community to the first interpolation algorithm published here:
In this article I would like to tell about one invented algorithm (or rather, a reinvented bicycle) for constructing a smooth graph from given points using Bezier curves. The article was written under the influence of this article…
The point is that the author of this article did not take the direct route, but a roundabout one, using cumbersome trigonometry of half angles to calculate the tangent of angle φ. In addition, the author did not pay attention to the analysis of the lengths of the support segments, simply assuming that the data are uniformly distributed along the X-axis with a fixed step, and therefore the lengths of the support segments can also be taken as fixed along the X-axis.
In fact, in order to calculate the coordinates of the reference points, you don't need trigonometry, you don't need to calculate the angle φ, and you don't even need the coefficient k. All you need is knowledge of the Pythagorean theorem and a little ingenuity in determining the proportions between the segments. At the same time, I got an algorithm that does not require uniformity of the step or even strict directionality along the X axis. You can direct the data arbitrarily, even along the Y axis, or in a circle.
To understand the algorithm for calculating the coordinates of reference points, let us construct a figure similar to the corresponding figure from the article of the first version.
![](https://habrastorage.org/getpro/habr/upload_files/43f/55d/a1f/43f55da1f7722ee38ba3702c72b0e86d.png)
I just moved point D to segment AB in such a way that segment CD was also inclined to the X axis, like segment B.1C1. It is easy to see that triangle DAC is isosceles. Also note that the length of segment CD is equal to twice the length of the support segment to the right of point A, at which the interpolation arc will be close to a circle. In the figure above, such a length is indicated by two gray lines perpendicular to the red line with support segments and segment CD. Let's take the length of CD in 2 relative units. Also note right away that the maximum possible length of the support segment on the left in the same units will be equal to the ratio |AB|/|AC|. Accordingly, in the case when |AB|=|AC|, the maximum length of the support segment on the left will also be equal to 1. Let's denote by m the relative length of the support segments required for construction. Usually, when using cubic Bezier curves, m=0.333, and for quadratic ones, m=0.5.
Now we can write formulas to calculate the coordinates of the control points on the left and right:
XB1 = XA-m*ΔXCD*|AB|/|AC|/2 | (1) | |
YB1 = YA-m*ΔYCD*|AB|/|AC|/2 | (2) | |
XC1 = XA+m*ΔXCD/2 | (3) | |
YC1 = YA+m*ΔYCD/2 | (4) |
Here
X and Y are the coordinates corresponding to the notations of the points;
ΔXCD=XWITH-XD And ΔYCD=YWITH-YD (no modulus, values may be greater or less than zero).
The absolute values of the modules of the lengths of the segments are easily determined using the Pythagorean theorem. Therefore, in essence, determining the coordinates of point D may present some difficulty for us here.
Let us take the entire length of the segment AB, on which the point D is located, as 1. Then the length of the segment AD relative to AB (denoted by d) d=|AC|/|AB| and the coordinates of the point D:
XD = XA-d*ΔXA.B. | (5) | |
YD = YA-d*ΔYA.B. | (6) |
And we will slightly optimize formulas (1), (2), (3) and (4) by making a change of variables using d and m2=m/2:
XB1 = XA-m2*ΔXCD /d | (7) | |
YB1 = YA-m2*ΔYCD /d | (8) | |
XC1 = XA+m2*ΔXCD | (9) | |
YC1 = YA+m2*ΔYCD | (10) |
And the last touch that, in my opinion, should be added to the algorithm is the elimination of the dips that appear at strong angles of inclination of the reference segments, including at a large difference in the scale along the Y axis compared to the scale along the X axis. In such a situation, the curve may begin to stretch too much to the right or left. It is reasonable to assume that, after all, maxima and minima in nature are more or less symmetrical both on the right and on the left. Therefore, we can introduce a softer condition than requiring a uniform step from the original data. In addition, interpolation is often necessary in order to bring the original data with an uneven step to a uniform step. It will be logical to make the length of the reference segments on the right and left the same, or close in size. To begin with, we will replace the variables in formulas 7 and 8, denoting m1=m2/d:
XB1 = XA-m1*ΔXCD | (eleven) | |
YB1 = YA-m1*ΔYCD | (12) |
Having calculated m1 and m2we check that the larger of them is not too large. We can set a requirement, say, that the larger of the support segments is no more than 7% larger than the smaller one. Visually, a 5% difference in the lengths of the support segments is not noticeable at all, but with a 10% difference, asymmetry is already slightly noticeable.
![The figure shows two interpolation results on the original data that were used in the first version of the algorithm, with the data arranged along the X axis and along the Y axis. In the construction, cubic Bezier curves with m=0.33333 were used for the middle sections, quadratic Bezier curves with m=0.4 for the extreme sections, and the requirement for the asymmetry of the lengths of the support segments to be no more than 7%. The figure shows two interpolation results on the original data that were used in the first version of the algorithm, with the data arranged along the X axis and along the Y axis. In the construction, cubic Bezier curves with m=0.33333 were used for the middle sections, quadratic Bezier curves with m=0.4 for the extreme sections, and the requirement for the asymmetry of the lengths of the support segments to be no more than 7%.](https://habrastorage.org/getpro/habr/upload_files/b98/fcc/e08/b98fcce08c5c7f9c176194a7023b46c1.png)
Actually, this was my answer to the author of the first version of this algorithm. You can check the algorithm's operation online on my website. By the way, the site works on https.net server of our own design for Windows.