Find Best Quadratic Bezier Curve Fit for Points

[temp]

hello
having a set of points of a curve, how i can find the best quadratic bezier curve that fits this curve?
(so we have start and end points of bezier curve, and only the position of control point is required.)
THX.

 

[hotvette]

Welcome to the forums!

Are you looking for a mathematical/theoretical development or a practical 'how to' approach?

Also, I presume you are fitting a single curve to the data points vs a series of connected quad Bezier splines. Also depends on what method you want for 'best fit'. Least squares comes to mind, but even then, there are at least two variations - sum of the square of vertical distances or sum of square of normal distances (sometimes called total least squares). Lastly, you imply the only unknown is the control point. That's true if you assume the Bezier start and end points are coincident with the start and end data points. If the Bezier start and end points are allowed to float, then there are 6 unknowns.

I've studied this a bit using cubic Beziers (https://www.physicsforums.com/showthread.php?t=166391) and haven't yet found (or created) a good mathematical development. What makes it tricky is having to find the value of the independent variable t to produce the x values you want so the y values can be computed and compared. It means solving a quadratic equation (which is easy) to determine the right t for each x.

One way to view this is as an optimization problem in 2 variables (i.e. x and y of the control point). There are many optimization approaches (e.g. simplex) that could solve this. The practical approach I've taken is:

1. Choose starting values for control point x & y
2. Calculate the necessary t's (by solving quadratic equation) to produce the x's of the data points
3. Calculate y's and compare (in a least squares sense) to the data points
4. Update the control point x & y based on the result of step 3 and go to step 2

I've done this two different ways. One is using an optimization Excel Add-In I found on a website. Another method was a traditional least squares approach that was quite involved because it required successive iterations of first optimizing the control point y, then x until a converged solution was found.

 

[temp]

thanx for your reply
but i have problem yet (i can't understand your method correctly).
its great that if you could explain your method with a sample (practical)

 

[hotvette]

OK, I was able to create a relatively simple example, all done with Excel. First, some preliminaries. The standard form of a quadratic Bezier is: B(t) = (1-t)²P₀ + 2t(1-t)P₁ + t²P₂……….0 ≤ t ≤ 1

Expanding and collecting terms, the equation can be put in classic polynomial form: B(t) = at² + bt + c, where:

a = P₀ – 2 P₁ + P₂
b = 2P₀ + 2 P₁
c = P₀

The above expressions really represent two equations, one for x and the other for y:

x(t) = a_xt² + b_xt + c_x
y(t) = a_yt² + b_yt + c_y

Calling the control points P₀ = (p_0x, p_0y), P₁ = (p_1x, p_1y), P₂ = (p_2x, p_2y)

a_x = p_0x – 2 p_1x + p_2x
a_y = p_0y – 2 p_1y + p_2y
b_x = 2p_0x + 2 p_1x
b_y = 2p_0y + 2 p_1y
c_x = p_0x
c_y = p_0y

Thus, we’ve established a relationship between the Bezier control points the polynomial coefficients.

Least Squares analysis involves fitting a desired function f to a set of points p = [p₁, p₂, ..p_n] = [(x₁, y₁), (x₂, y₂), … (x_n, y_n)]. A standard means of determining ‘quality of fit’ is to sum the squares of the differences in vertical distance between the data points and the points generated by the function:

sum of squares = (f(x₁) - y₁)² + (f(x₂) - y₂)² … + (f(x_n) – y_n)²

The idea is to make the sum of squares as small as possible. The key is that the same value of x must be used for each point, so only vertical distance is being used). This is a challenge when using parametric curves because x is a function of the independent variable t. Thus, for each data point, the proper t needs to be determined such that the resulting x is identical to the x of the data point.

Here is a specific example. Suppose we wish to fit a quadratic Bezier to the following data points:

[(x₁, y₁), (x₂, y₂), (x₃, y₃), (x₄, y₄), (x₅, y₅)] = [(0, 0), (0.2, 0.01), (0.7, 0.4), (0.9, 0.8), (1, 1)]

Here is the simple approach I used:

1. Make an initial guess at control point P₁ (P₀ = (0, 0) and P₂ = (1, 1) are given). I used P₁ = (0.7, 0) as an initial guess.

2. Calculate the polynomial coefficients:

a_x = p_0x – 2 p_1x + p_2x = 0 – 2(0.7) + 1 = -0.4
b_x = 2p_0x + 2 p_1x = 2(0) + 2(0.7) = 1.4
c_x = p_0x = 0

3. Generate x, y points for t = 0 to 1 and plot the Bezier curve. Plot the original data points and see how close the fit is. (It is instructive to play around with various values for p_1x and p_1y and see how the shape of the curve changes in relation to the data points).

4. Calculate the sum of squares. Here’s the tricky part. To calculate (f-y)², you need to find t that results in the same x as the data point. For example, x₂ = a_xt₂² + b_xt₂ + c_x. To find the t₂ that produces x₂, a quadratic equation needs to be solved (i.e.[ –b ± sqrt(b²-4ac)]/2a). This needs to be done for all interior points (the end points are already known). Thus, for the initial control points used:

t₁ = 0...==> x₁ = 0, y₁ = 0
t₂ = 0.149...==> x₂ = 0.2, y₂ = 0.022
t₃ = 0.604...==> x₃ = 0.7, y₃ = 0.365
t₄ = 0.849……….==> x₄ = 0.9, y₄ = 0.72
t₅ = 1……….==> x₅ = 1, y₅ = 1

Now we can calculate the sum of squares = (0 – 0)² + (0.022 – 0.01)² + (0.365 – 0.04)² + (0.72 – 0.8)2 + (1 – 1)² = 0.008

5. Try new values of P₁ until the sum of squares is minimized. Each time that p_1x is changed, three sets of quadratic equations must be solved to find t associated with each x. As an example, suppose we try P₁ = (0.6, 0). Then:

a_x = p_0x – 2 p_1x + p_2x = 0 – 2(0.6) + 1 = -0.2
b_x = 2p_0x + 2 p_1x = 2(0) + 2(0.6) = 1.2
c_x = p_0x = 0

t₁ = 0...==> x₁ = 0, y₁ = 0
t₂ = 0.172...==> x₂ = 0.2, y₂ = 0.029
t₃ = 0.655...==> x₃ = 0.7, y₃ = 0.429
t₄ = 0.879……….==> x₄ = 0.9, y₄ = 0.772
t₅ = 1……….==> x₅ = 1, y₅ = 1

sum of squares = (0 – 0)² + (0.029 – 0.01)² + (0.429 – 0.04)² + (0.772 – 0.8)2 + (1 – 1)² = 0.002

If Excel is used and the formulas are set up correctly, the quadratic equations will be automatically solved each time P₁ is changed.

For this example, I just used the Excel built-in solver function to minimize the cell containing the sum of squares and allowing p₁ (i.e. p_1x and p_1y) to be changed. The net result:
P₁ = (0.543, -0.108)
(a_x, a_y) = (-0.087, 1.216)
(b_x, b_y) = (1.087, -0.216)
(c_x, c_y) = (0, 0)
sum of squares = 0.001

It should be noted that forcing the end points of the Bezier curve to be coincident with the first and last data points is an artificial restriction that limits the quality of fit. If p_0y and p_2y are also allowed to be adjusted, a better fit can be achieved. Also, since parametric curves are so flexible, it is relatively easy to get into a situation where the best fit curve has a loop somewhere in the middle or the curve otherwise takes on a completely unexpected and undesirable shape. Such are the caveats of least squares fitting with parametric curves.
.

 

[schwa]

I believe the b term in the quadratic should be -2P0 + 2P1.