1
$\begingroup$

$$ y = a^2+b^2+1 $$ $$ a = 3cx(1-x)^2 + 3x^2(1-x) + x^3 $$ $$ b = 3cx^2(1-x) + 3x(1-x)^2 + (1-x)^3 $$ For x between 0 and 1, for what value of c is the area under the curve the smallest?

For context, this is the equation for the error in an approximation of a cubic Bézier curve for a given value of c.

Also see, http://spencermortensen.com/articles/bezier-circle/

The naive result for the approximation is $$ c = \frac4 3 (\sqrt2 - 1) = 0.5522847498 $$

Mortensen's result seeks to equalizing the positive and negative error and gets: $$ c = 0.551915024494 $$

Whereas because there's clearly more space for the error in the positive than negative so if we want to minimize the error overall we need to minimize the area under the graph:

From brute-forcing it (i'm a computer scientist) the answer should be something like $$ c = 0.5520137217 $$ But, my actual skills to do the calculus needed are lacking and my brute force methodology is quite likely to have error (since I can only find the maxima with very many samples.


So I know that given a value of c = 0.55191502449 at 0.0000001 increments so 10,000,001 samples. gives me a total sum of the errors equal to: 1180.57375326880...

Adjusting the value of c and just throwing a computer at it finds that 0.55201372171 gives a total error 1159.83397426356..., for the same samples.

Clearly there's a marked improvement if our metric is not difference in extrema but rather total error. But, my calculus-fu is weak and I can't figure either the optimal result or the equation for the total sum of the error. I know it requires calculus. But, if we seek to not just reduce the error at the extremes but the error as a whole, this would seem to give a different value. Largely in part because the two twin extremes, or generally flattening out the graph of the error.

$\endgroup$
  • $\begingroup$ Bezier splines differ from other splines only in the way that the coefficients are determined. Bezier curves are determined by values and tangents in select points. If you want to minimize then Bezier spline is probably not the correct choice. $\endgroup$ – skyking Jun 30 '17 at 7:24
  • $\begingroup$ The man's name was Bézier. Not Bezier, and certainly not Bezier. $\endgroup$ – bubba Jun 30 '17 at 7:26
2
$\begingroup$

A good reference is

Approximation of circular arcs by cubic polynomials
Michael Goldapp
Computer Aided Geometric Design
Volume 8, Issue 3, August 1991, Pages 227-238

Suppose we're approximating the first quadrant of a unit arc. We use a cubic Bézier curve with control points at $(1,0)$, $(p,q)$, $(q,p)$, $(0,1)$, so the curve equation is \begin{align} x(t) &= (1-t)^3 + 3pt(1-t)^2 + 3qt^2(1-t) \\ y(t) &= 3qt(1-t)^2 + 3pt^2(1-t) + t^3 \end{align}

As you said, the simplest approach is to use $p=1$ and $q = \tfrac43(\sqrt2 - 1)$. This gives an error $+2.72 \times 10^{-4}$. Note that the error is everywhere positive -- the cubic lies outside the circle. This is the blue error curve in the picture below.

Next attempt is to use $p=1$ and $q = 0.55191496$. This gives an error of $\pm 1.96 \times 10^{-4}$. Here the error equioscillates, as shown by the red curve in the picture below. This is the best you can do with $p=1$.

If you're willing to allow $p \ne 1$, you can do even better. Use $p=0.998978326$ and $q = 0.553429265$, and you get an error of $\pm 0.55 \times 10^{-4}$. Again the error equioscillates, as shown by the green curve in the picture. The cubic is no longer tangent to the circular arc its end points. This may or may not matter to you.

The graphs below show the error $$ \text{error}(t) = \sqrt {x(t)^2 + y(t)^2} - 1 $$ for the three curves, for $0 \le t \le 1$. In other words, they show the true geometric (distance) error, not an area error, and not a sum-of-squares error.

enter image description here

$\endgroup$
  • $\begingroup$ Even with p = 1, if your metric is not finding the extrema of the error but rather the sum of the error at each place along the graph [0,1] the optimal value of q changes, from brute forcing it seems very close to q = 0.552013 gives a sum of total error less than the 0.55191496 value. $\endgroup$ – Tatarize Jun 30 '17 at 16:26
  • $\begingroup$ @Tatarize -- I don't know if your comment is directed to me or to the OP. The errors I discuss are true distance errors (i.e. distance between the cubic and the true circular arc), as functions of $t \in [0,1]$. The turning points on the graphs show extrema of this distance error. $\endgroup$ – bubba Jul 1 '17 at 2:01
  • $\begingroup$ I know, I'm the OP, I calculated them a great many times. The difference in the question is that I'm asking about the total overall error, not the difference between the extrema. Minimizing the region below the curve, throughout the graph rather than simply minimizing the values at the extremes. This metric turns out to yield a different value. It's somewhere very close to 0.552013 but I got that by doing 10 million samples across the graph and adjusting the the value of C. The total error over 10,000,001 for the graph at 0.55191496 (minimal extreme difference) is 1180. At 0.552 it's 1160. $\endgroup$ – Tatarize Jul 1 '17 at 3:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.