Quadratic Bézier Curve

graphemecluster commented 4 years ago

"Cartesian equation type only supports straight lines. Cartesian equations for bezier curves are theoretically possible but not simple, and performance when plotted would be bad."

After simplifying a quadratic curve is actually just a simple parabola:

Implicit Function of a quadratic Bézier curve with points (A, D), (B, E) and (C, F) (x(D-2E+F)-y(A-2B+C))² +2x((A+C)(DF-E²)-A(E-F)²+2B(DE-2DF+EF)-C(E-D)²) +2y((D+F)(AC-B²)-D(B-C)²+2E(AB-2AC+BC)-F(B-A)²) +4(BD-AE)(BF-CE) +(AF-CD)² =0

And the 5 constants could be pre-calculated if necessary.

Also, it would be great if something like this could be made. Desmos Link

Thank you for reading and sorry for disturbing.

maltaisn commented 4 years ago

After simplifying a quadratic curve is actually just a simple parabola:

Implicit Function of a quadratic Bézier curve with points (A, D), (B, E) and (C, F) (x(D-2E+F)-y(A-2B+C))² +2x((A+C)(DF-E²)-A(E-F)²+2B(DE-2DF+EF)-C(E-D)²) +2y((D+F)(AC-B²)-D(B-C)²+2E(AB-2AC+BC)-F(B-A)²) +4(BD-AE)(BF-CE) +(AF-CD)² =0

The implicit equation I came up for quadratic bezier curves with was (it's the same as the one mentioned in the readme):

$(y__1^2-4 y__1 y__2+2 y__1 y__3+4 y__2^2-4 y__2 y__3+y__3^2) x^2+(-2 x__1 y__1+4 x__1 y__2-2 x__1 y__3+4 x__2 y__1-8 x__2 y__2+4 x__2 y__3-2 x__3 y__1+4 x__3 y__2-2 x__3 y__3) x y+(2 x__1 y__1 y__3-4 x__1 y__2^2+4 x__1 y__2 y__3-2 x__1 y__3^2+4 x__2 y__1 y__2-8 x__2 y__1 y__3+4 x__2 y__2 y__3-2 x__3 y__1^2+4 x__3 y__1 y__2+2 x__3 y__1 y__3-4 x__3 y__2^2) x+(x__1^2-4 x__1 x__2+2 x__1 x__3+4 x__2^2-4 x__2 x__3+x__3^2) y^2+(-2 x__1^2 y__3+4 x__1 x__2 y__2+4 x__1 x__2 y__3+2 x__1 x__3 y__1-8 x__1 x__3 y__2+2 x__1 x__3 y__3-4 x__2^2 y__1-4 x__2^2 y__3+4 x__2 x__3 y__1+4 x__2 x__3 y__2-2 x__3^2 y__1) y+x__1^2 y__3^2-4 x__1 x__2 y__2 y__3-2 x__1 x__3 y__1 y__3+4 x__1 x__3 y__2^2+4 x__2^2 y__1 y__3-4 x__2 x__3 y__1 y__2+x__3^2 y__1^2 = 0$

It seems a bit different than yours. I won't show the one for cubic bezier curves here, it has over a hundred terms. So I consider that the "direct" approach consisting of calculating each term is not very viable, unless maybe converting all cubic curves to quadratic curves beforehand.

I had also tried another method which used a number of points from the bezier curve (6 for quadratic, 10 for cubic) to make a curve fitting, essentially reducing the problem to solving a system of linear equations. It worked great, however I was using arbitrary precision numbers and I'm not sure how well it would work with floating point numbers. I have some Maple worksheets on that if you're interested.

There are other problems with implicit equations. For example finding the bounds becomes a lot more complicated. For parametric equations it's as easy as limiting the range of $t$ . For implicit equations you get complex bounds like $108 x^2 + 7xy - y^2 > 0$ (this one was made up but you get the point). I didn't look much into it though.

Performance also becomes a problem. Thousands of parametric equations can be plotted just fine since it's a matter of entering various values for $t$ . Implicit equations on the other hand are a lot harder to plot. You can already see that when comparing the performance in Desmos for plotting the generated cartesian equations vs the parametric ones for a relatively complex SVG made of only straight lines. (like a world map)

So yes, you are correct in saying this is possible. However I believe it goes beyond the intent of this project. The complexity of resulting equations makes it unappealing.

Also, it would be great if something like this could be made. Desmos Link

Adding fill would certainly be an interesting challenge. I don't have much time right now unfortunately. I encourage you to make your own research!

graphemecluster commented 4 years ago

Thank you for the reply!

I believe that the equation I gave would be the same as yours after expanding unless I made any mistake. Actually I am interested in the implicit equation of cubic Bézier curve, and I would be glad if you could provide more information on it.

Also, if performance is your concern I suggest you to add an option to plot straight lines by explicit functions.

Luckily Desmos support filling of parametric functions, so it would be easy to reproduce the SVG path (additionally, by setting the color by JavaScript).

maltaisn commented 4 years ago

Here's PDF renders of the Maple worksheets I had made:

bezier-polynomial.pdf: In this one I'm finding implicit equations for quadratic and cubic bezier curves. This basically uses the same logic as in this StackOverflow answer.
bezier-fitting.pdf: In this one I find the implicit equation for a bezier curve by curve fitting. A cubic bezier curve can be described by a 3rd degree polynomial which has 10 terms (ax^3 + bx^2*y + cx*y^3 + ... + j). I take 10 points of the bezier in the range [0..1] and evaluate each of the polynomial terms with the X, Y coordinates of that point. So each point becomes a row in a 10x10 matrix A. A.X = O, where X is a vector of the bezier polynomial coefficients (a, b, ... j) and O is a null vector (since the implicit equation = 0). Solving for X gives the coefficients. There's has an infinity of solutions so the free variable is just replaced by 1. As I said in the other comment I'm not convinced of the numerical stability of this approach, it might only work with arbitrary precision numbers.

The worksheets in case you have Maple: bezier-maple.zip

maltaisn / svg-equations

Quadratic Bézier Curve #1