Approximate replacement of cubic Bezier by two arcs

Question

Hey. My old graphical framework (GD) does not know how to draw cubic Bezier curves (in general, none can). In order to draw characters from TTF fonts (the task does not allow directly), I want to somehow partially inadequately replace the Bezier curves with arcs. But how? I do not need ready-made scientific works (I know, they exist and have industrial meaning), which allow a set of arcs to bring the result closer to the Bezier curve as accurately as possible. Two arcs are enough for me.

Here is what I have:

The coordinates of the points P₁ and P₂ are known. The coordinates of the control points are C₁ and C₂ too. From the points P₁ and P₂, I ran straight perpendicular to the P₁C₁ and P₂C₂ segments of red. The centers of the desired arcs will lie on these lines, otherwise the tangents at points P₁ and P₂ do not coincide, and the condition of the problem is violated.

Then I decided to act like this. Through the midpoint of P₀ between the points P₁ and P₂, I drew a straight line (gray color) perpendicular to the segment between them, then "gray perpendicular". Then I add the first circle (green color):

It can be seen that, depending on its radius R₁, its center simply “rides” along the red line, and the point of intersection with the gray perpendicular and the angle of intersection change.

Similarly, all with the second circle of radius R₂ (blue color):

So, I need to find such values of the radii R₁ and R₂ so that both circles intersect with the gray perpendicular at one point, moreover, they have the same tangent angle at this point. Then I already cut them on the arc myself.

That is, the source data is P₁, P₂, C₁, C₂, whose coordinates (x, y) are known. And you need to find R₁ and R₂ (radii of circles, scalar numbers).

I am no longer able to solve equations with X and Y separately, with a bunch of trigonometry. Maybe with the help of vector algebra is it somehow easier, more elegantly solved?

To the question, and what have I done myself. I solved a slightly different task when the radius of the first arc is known in advance.

<?php $width = 600; $height = 600; function demo($im) { $x1 = 124; $y1 = 253; imagefilledarc($im, $x1, $y1, 10, 10, 0, 0, 0x000000, 0); imagestring($im, 2, $x1-30, $y1+10, "x1, y1", 0x000000); $x2 = 445; $y2 = 428; imagefilledarc($im, $x2, $y2, 10, 10, 0, 0, 0x000000, 0); imagestring($im, 2, $x2+0, $y2+10, "x2, y2", 0x000000); imageline($im, $x1, $y1, $x2, $y2, 0x000000); $xc1 = $x1 + 50; $yc1 = $y1 - 200; imageline($im, $x1, $y1, $xc1, $yc1, 0x000000); imagefilledarc($im, $xc1, $yc1, 10, 10, 0, 0, 0x000000, 0); $xc2 = $x2 -5; $yc2 = $y2 -200; imageline($im, $x2, $y2, $xc2, $yc2, 0x000000); imagefilledarc($im, $xc2, $yc2, 10, 10, 0, 0, 0x000000, 0); $d1 = 10 * sqrt( pow($x1-$xc1, 2) + pow($y1-$yc1, 2) ); $ac1 = atan2($yc1-$y1, $xc1-$x1); $ap1 = $ac1 + pi() / 2.; $xp1 = $x1 + $d1*cos($ap1); $yp1 = $y1 + $d1*sin($ap1); imageline($im, $x1, $y1, $xp1, $yp1, 0x808080); $d2 = 10 * sqrt( pow($x2-$xc2, 2) + pow($y2-$yc2, 2) ); $ac2 = atan2($yc2-$y2, $xc2-$x2); $ap2 = $ac2 - pi() / 2.; $xp2 = $x2 + $d2*cos($ap2); $yp2 = $y2 + $d2*sin($ap2); imageline($im, $x2, $y2, $xp2, $yp2, 0x808080); /** Принудительно задается радиус первой (красной) дуги, что неправильно!!! */ $r1 = 135; /** Из него вычисляется положение центра красной дуги, обозначен красной точкой. */ $r1x = $x1 + $r1*cos($ap1); $r1y = $y1 + $r1*sin($ap1); imagefilledarc($im, $r1x, $r1y, 10, 10, 0, 0, 0xFF0000, 0); imagestring($im, 2, $r1x-40, $r1y-30, "r1x, r1y", 0x000000); /** Это результат решения уравнения для заданного радиуса красной дуги */ $L = ( 2.*($r1x*$x2 + $r1y*$y2) - pow($x2, 2) - pow($y2, 2) - pow($r1x, 2) - pow($r1y, 2) + pow($r1, 2) ) / 2. / ( cos($ap2)*($x2-$r1x) + sin($ap2)*($y2-$r1y) + $r1 ); $xl = $x2 + $L*cos($ap2); $yl = $y2 + $L*sin($ap2); imagefilledarc($im, $xl, $yl, 10, 10, 0, 0, 0x00FF00, 0); $aspl = atan2($r1y-$yl, $r1x-$xl); imagearc($im, $r1x, $r1y, 2*$r1, 2*$r1, rad2deg($ap1)+180, rad2deg($aspl), 0xFF0000); imagearc($im, $xl, $yl, 2*$L, 2*$L, rad2deg($aspl), rad2deg($ap2)-180, 0x0000FF); } $im = imagecreatetruecolor($width, $height); imagefilledrectangle($im, 0, 0, $width-1, $height-1, 0xc0c0c0); demo($im); header('Content-Type: image/png'); imagepng($im, null, 9);

In this case, the first arc is red. But this is not what is needed. I need a certain “parity” between the arcs, and not that the radius of the first one is set by force.

Going to start a contest. Therefore, in order not to mislead participants, I will now state what conclusions I myself have come to over time.

I received a formula for the radius of a circle from the coordinates of any point (Xz, Yz) through which it must pass:

  (Xz-X₁)² + (Yz-Y₁)² R₁ = 2 --------------------------- (Xz-X₁)Cosβ + (Yz-Y₁)Sinβ (Xz-X₂)² + (Yz-Y₂)² R₂ = 2 --------------------------- (Xz-X₂)Cosγ + (Yz-Y₂)Sinγ

Then I mark the angles (not in the picture) between the x-axis and
1) red perpendicular from point P₁ - β
2) red perpendicular from point P₂ - γ
3) gray perpendicular from point P₀ - δ
(I reserved the angle α just in case for the slope of the straight line P прямойP₂ itself, but it was not needed).

Then the condition of equality of tangent circles at the point (Xz, Yz) is added. It simply means that (Xz, Yz), (Xr₁, Yr₁) and (Xr₂, Yr₂) lie on the same line. Simple proportion:

 Xz - Xr₁ Xz - Xr₂ -------- = -------- Yz - Yr₁ Yz - Yr₂

Then I express the coordinates of points through angles and distances from other points:

 Xz = X₀ + ZCosδ Yz = Y₀ + ZSinδ Xr₁ = X₁ + R₁Cosβ Yr₁ = Y₁ + R₁Sinβ Xr₂ = X₂ + R₂Cosγ Yr₂ = Y₂ + R₂Sinγ

The result is:

EQUATION SYSTEM WITH THREE UNKNOWN (R₁, R₂, Z):

  (Xz-X₁)² + (Yz-Y₁)² R₁ = 2 --------------------------- (Xz-X₁)Cosβ + (Yz-Y₁)Sinβ (Xz-X₂)² + (Yz-Y₂)² R₂ = 2 --------------------------- (Xz-X₂)Cosγ + (Yz-Y₂)Sinγ Xz - Xr₁ Xz - Xr₂ -------- = -------- Yz - Yr₁ Yz - Yr₂ Xz = X₀ + ZCosδ Yz = Y₀ + ZSinδ Xr₁ = X₁ + R₁Cosβ Yr₁ = Y₁ + R₁Sinβ Xr₂ = X₂ + R₂Cosγ Yr₂ = Y₂ + R₂Sinγ

Moreover, all these sines and cosines are generally constants, since the angles (their arguments) are given as constants.

As soon as I twisted this system. He opened brackets, used computer algebra (Maxima program), including partial results. It turns out that there is no analytical solution . And numerical methods are not suitable, because I was going to draw symbols from fonts with arcs, can you imagine what the speed will be.

Therefore, a competition is announced. Only the question title matters. Then we decide how we want, only analytically. It is not necessary and can be harmful to take note of all the nonsense outlined by me in the text.

PS I, among other things, are interested in "parity" on the basis of some relation between arcs (radii). To make a small circle with a given radius and "fasten" the second on it - this has already been done in the text of the question.

Here, by the way, is the negative value of R₂. Drawn in PHP GD based on the first two formulas without any additional conditions:

That is, there is no restriction on how far from the point P a circle can intersect with a gray perpendicular — no.

Here, just in case, for whom it is necessary, the cubic Bezier curve for the points P₁, P₂ and the control points C₁ and C кому, for whom it is necessary, with a red dotted line:

It does not need to be approximated, but simply needs to be replaced with something smooth based on two arcs.

I will add animation to the question, but something is not enough attention to it.

 $r2 = .5 * (pow($r1, 2.) - pow($x2-$r1x, 2.) - pow($y2-$r1y, 2.)) / (cos($ap2)*($x2-$r1x) + sin($ap2)*($y2-$r1y) + $r1);

Where $ ap2 is just perpendicular to the tangent at P2.

I understood almost nothing, but it is awesome to be awesome.
@NickVolynkin, at first I was going to do it in 10 minutes, then in 2 hours, then I thought: there will be nothing terrible if I have a dazed day over school geometry, the schedule is free.
@VladD is the point on which the Bezier curve is built (which I really don't need at all).
The curve passes through the points P1 and P2 along the tangents, which are given by the points C1 and C2.
In the case of a Bezier curve, the length of the P1C1 and P2C2 segments also makes sense.

VladD VladD 183k 16 gold signs 228 silver marks 434 bronze marks · Accepted Answer · 2017-08-24T22:42:48

As a simple alternative, I suggest rasterization.

Intermediate points are calculated very easily:

 Point GetMiddlePoint(double alpha) { Point Q0 = Middle(P1, C1, alpha); Point Q1 = Middle(C1, C2, alpha); Point Q2 = Middle(C2, P2, alpha); Point R0 = Middle(Q0, Q1, alpha); Point R1 = Middle(Q1, Q2, alpha); return Middle(R0, R1, alpha); } Point Middle(Point X, Point Y, double alpha) => X + (Y - X) * alpha;

By connecting intermediate points with lines, already at 8 points we get a not-so-bad result:

rasterization not govnokod!

If you have seen how the characters are encoded in fonts (the P points are quite dense), then with your rasterization, this results in pixel-by-pixel rendering for small character sizes.
And this can be done simply by the Bezier formulas, but very slowly.
Then, PHP on default hosting does not know how to draw straight lines with anti-aliasing.
The depth of rasterization can be changed according to the current resolution.

Zergatul Zergatul 9,161 1 golden mark 13 silver marks 26 bronze marks · Answer 2 · 2017-08-24T00:28:49

You formulated the problem in such a way that it has no solution in the general case.

So, I need to find such values of the radii R₁ and R₂ so that both circles intersect with the gray perpendicular at one point, moreover, they have the same tangent angle at this point.

If 2 circles intersect, then at the intersection point they have the same tangent angle if and only if the intersection point is one:

In the example above, in the first 2 cases the angle of the tangent is the same; in the 3 cases, there is no way to combine the 2 arcs.

I drew in the editor a solution for the example, as in your drawings. The solution does not take into account your condition about the intersection on the perpendicular:

If I continue to increase the radius of the larger circle, and select a smaller radius so that they intersect at one point, this point will never be perpendicular. Even if we increase the radius of the second circle to infinity (it becomes straight), the intersection still does not reach the perpendicular:

The solution without nested circles is not suitable, because arcs do not come out on the right side:

The same with the solution, when the second circle is inside the first one:

The condition for the presence of a single intersection point is not at all clear how to formulate, therefore I simply designed the coincidence of tangents as a proportion of the centers of the circles with the intersection point - they lie on one straight line (there is a question there).
I showed you "on the fingers" that the problem has no solution.
Two circles passing through certain different points, manipulating their radii, cannot be brought to the point that they also pass through one and only one common ?
You have shown in the pictures that you can, and you write that you can not.
Your condition says that the intersection should be perpendicular.
2 other options will not suit you, because the result will not be what you need.
Girls, why not take some kind of library from Flash, where the cubic Bezier was not and these libraries were written like dirt?

Approximate replacement of cubic Bezier by two arcs

2 answers 2

More articles: